Discuss stack Organization. Explain the following in details- (i) Register stack (ii) Memory stack

(i) Register stack

Here the stack is a set of CPU registers. Suppose it has 64 words, so SP is a 6-bit register. A word is moved through the data register DR. Two flip-flops, FULL and EMPTY, show the state of the stack.

   +----------+
 63|          |
   |   ...    |
  3|   C      |  <- SP = 3, top is C
  2|   B      |
  1|   A      |
  0|          |
   +----------+

Initially $SP = 0$, $EMPTY = 1$ and $FULL = 0$. The PUSH operation is

$$SP \leftarrow SP + 1$$

$$M[SP] \leftarrow DR$$

$$\text{if } SP = 0 \text{ then } FULL \leftarrow 1,\ EMPTY \leftarrow 0$$

SP becomes 0 again only after the last location (63) is filled, because the 6-bit counter wraps around. The POP operation is

$$DR \leftarrow M[SP]$$

$$SP \leftarrow SP - 1$$

$$\text{if } SP = 0 \text{ then } EMPTY \leftarrow 1,\ FULL \leftarrow 0$$

A push is not allowed when FULL is 1, and a pop is not allowed when EMPTY is 1. A register stack is very fast, but its size is small and fixed.

(ii) Memory stack

Here a part of main memory is used as the stack. Three segments exist in memory: the program, the data and the stack. The program counter points to the program, an address register points to the data, and SP points to the top of the stack. The stack usually grows towards lower addresses. Suppose SP starts at 4001 and the stack uses the addresses 4000 down to 3000. The PUSH operation is

$$SP \leftarrow SP - 1$$

$$M[SP] \leftarrow DR$$

The POP operation is

$$DR \leftarrow M[SP]$$

$$SP \leftarrow SP + 1$$

Here the limits are checked by comparing SP with the two end addresses. The stack can be large and the size can be changed, but every push and pop needs a memory access, so it is slower than a register stack.

Example of memory stack use

Start with $SP = 4001$. Push the values 10 and then 20. After the first push SP is 4000 and M[4000] holds 10. After the second push SP is 3999 and M[3999] holds 20. A pop now returns 20, the last item pushed, and SP goes back to 4000. This shows the LIFO rule.

Difference in short

Both kinds help to evaluate expressions written in reverse Polish notation. Operands are pushed. An operator pops two values and pushes the result. No address field is needed, so the instructions are zero-address instructions.