Stack
A stack is a storage device that stores information such that the item stored last is the first retrieved — LIFO (Last In, First Out).
Two operations only:
PUSH : insert an item at the top
POP : remove the item from the top
One pointer:
SP (Stack Pointer) : always holds the address of the TOP of the stack1. Register Stack
A stack implemented as a finite set of registers with a hardware stack pointer.
64-word register stack: SP is a 6-bit register (2^6 = 64)
Words are 16 bits wide; DR is the data register.
FULL and EMTY are 1-bit flags.PUSH micro-operations
SP <- SP + 1 increment the stack pointer
M[SP] <- DR write the item to the new top
if (SP = 0) then (FULL <- 1) SP wrapped around -> stack is full
EMTY <- 0 the stack is definitely not empty nowPOP micro-operations
DR <- M[SP] read the current top
SP <- SP - 1 decrement the pointer
if (SP = 0) then (EMTY <- 1) the stack is now empty
FULL <- 0 it is definitely not full now Why "if SP = 0 then FULL":
SP is 6 bits, so after 63 it wraps to 0. Reaching 0 by INCREMENT
means all 64 locations are occupied.
Reaching 0 by DECREMENT means the last item has just been removed.Initial condition: SP = 0, EMTY = 1, FULL = 0.
2. Memory Stack
More common: a portion of main memory is used as the stack, with SP being an ordinary CPU register.
Typical memory partition:
Address
0000 +---------------------+
| PROGRAM | (instructions)
1000 +---------------------+
| DATA | (operands)
2000 +---------------------+
| |
| STACK | grows DOWNWARD
3000 +---------------------+ <- SP starts here
4000 (memory limit)PUSH and POP for a downward-growing stack
PUSH: SP <- SP - 1
M[SP] <- DR
POP: DR <- M[SP]
SP <- SP + 1Note the reversal: a register stack grows upward (SP increments on push); a memory stack conventionally grows downward (SP decrements on push), so that the stack and the data area grow toward each other and use free memory efficiently.
Stack limits
Two bound registers hold the lower and upper limits.
After every push: compare SP with the LOWER limit -> stack overflow
After every pop : compare SP with the UPPER limit -> stack underflow3. Uses of the Stack
| Use | How |
|---|---|
| Subroutine call/return | The return address is pushed on call, popped on return |
| Nested/recursive calls | Each level gets its own stack frame automatically |
| Parameter passing | Arguments are pushed before the call |
| Local variables | Allocated in the stack frame, freed on return |
| Interrupt handling | PC and flags are pushed before the ISR runs |
| Expression evaluation | The core of the zero-address machine (below) |
| Register saving | PUSH/POP the register set around a call |
4. Reverse Polish Notation (RPN)
Stacks evaluate postfix expressions with no parentheses and no precedence rules.
| Notation | Form | Example for A + B |
|---|---|---|
| Infix | A op B | A + B |
| Prefix (Polish) | op A B | + A B |
| Postfix (Reverse Polish) | A B op | A B + |
Converting infix to postfix
(A + B) * (C + D)
Step 1: innermost first -> (AB+) * (CD+)
Step 2: apply the outer operator -> AB+ CD+ *
Answer: A B + C D + * A * B + C * D -> A B * C D * +
(A + B) * C - D -> A B + C * D -
A + B * C - D / E -> A B C * + D E / -
((A + B) * C) / (D - E) -> A B + C * D E - /Evaluating a postfix expression on a stack
Evaluate 3 4 * 5 6 * + (i.e. 3*4 + 5*6 = 42)
Token | Action | Stack after
------+---------------------------------+-------------
3 | push 3 | 3
4 | push 4 | 3, 4
* | pop 4, pop 3, push 3*4 = 12 | 12
5 | push 5 | 12, 5
6 | push 6 | 12, 5, 6
* | pop 6, pop 5, push 30 | 12, 30
+ | pop 30, pop 12, push 42 | 42
Result = 42 ✓ Rule: an OPERAND is pushed;
an OPERATOR pops the top TWO items, applies itself, pushes the result.
At the end, exactly one value remains — the answer.5. Zero-Address Instructions
A stack machine needs no address field for arithmetic — the operands are implicitly on the stack.
Evaluate X = (A + B) * (C + D) on a stack machine:
PUSH A ; stack: A
PUSH B ; stack: A, B
ADD ; stack: (A+B)
PUSH C ; stack: (A+B), C
PUSH D ; stack: (A+B), C, D
ADD ; stack: (A+B), (C+D)
MUL ; stack: (A+B)*(C+D)
POP X ; store the resultOnly PUSH and POP carry an address; ADD and MUL are pure zero-address instructions.
6. Hardware Support for Procedure Calls
CALL instruction:
SP <- SP - 1
M[SP] <- PC (save the return address)
PC <- effective address of the subroutine
RETURN instruction:
PC <- M[SP] (restore the return address)
SP <- SP + 1
Because the return addresses stack up, RECURSION works automatically —
which is exactly why the BSA instruction of the basic computer
(which stores the return address in a fixed memory word) CANNOT
support recursion.Stack frame of a procedure call
Higher addresses
+--------------------+
| Parameters | pushed by the caller
+--------------------+
| Return address | pushed by CALL
+--------------------+
| Saved frame pointer|
+--------------------+
| Local variables | allocated by the callee
+--------------------+ <- SP (top of stack)
Lower addresses7. Register Stack vs Memory Stack
| Basis | Register stack | Memory stack |
|---|---|---|
| Location | Dedicated CPU registers | A region of main memory |
| Size | Small and fixed | Large, limited only by memory |
| Speed | Very fast | Slower (memory access) |
| Overflow detection | FULL / EMTY flags | Compare SP against bound registers |
| Growth direction | Usually upward | Usually downward |
| Cost | High (registers are expensive) | Low |
| Used in | Small/embedded processors | All general-purpose CPUs |
Summary
Stack : LIFO, one pointer (SP), two operations (PUSH, POP)
Register stack : PUSH = SP+1 then M[SP]<-DR; POP = DR<-M[SP] then SP-1
Memory stack : PUSH = SP-1 then M[SP]<-DR; POP = DR<-M[SP] then SP+1
RPN : postfix; operands push, operators pop two and push one
Zero-address : arithmetic instructions need no address fieldThe next lesson generalises this into the full taxonomy of instruction formats.