Stack Organization
In the previous articles, we studied two CPU organizations:
Single Accumulator Organization
General Register Organization
Both approaches explicitly or implicitly use registers to hold operands.
Now let's look at a different approach:
Stack Organization.
Instead of explicitly specifying operands in every arithmetic instruction, a stack-based CPU obtains operands from the top of the stack.
This makes stack-based instructions particularly simple.
What Is a Stack?
A stack is a data structure that follows the principle:
LIFO — Last In, First Out
The last value pushed onto the stack is the first value removed.
For example:
┌───────┐
Top → │ 30 │ ← Last pushed ├───────┤ │ 20 │ ├───────┤ │ 10 │ └───────┘
If we perform POP, the value 30 is removed first.
The Stack Pointer
The CPU needs to know where the top of the stack is.
This is commonly handled by a Stack Pointer (SP).
Conceptually:
Stack
│
▼
┌────────┐
│ 30 │ ← SP / Top
├────────┤
│ 20 │
├────────┤
│ 10 │
└────────┘
The exact behavior of the Stack Pointer and the direction in which the stack grows depend on the processor architecture.
PUSH Operation
PUSH adds a value to the top of the stack.
Suppose the stack contains:
Top → 20 10
Now:
PUSH 30
The stack becomes:
Top → 30 20 10
Conceptually:
Value → Stack
POP Operation
POP removes the value at the top of the stack.
Suppose:
Top → 30 20 10
After:
POP
the value 30 is removed:
Top → 20 10
The removed value can be transferred to a register, memory location, or another destination depending on the instruction set.
Stack-Based Arithmetic
The most interesting part of stack organization is how arithmetic instructions work.
Suppose:
A = 10 B = 5
A stack-based sequence could be:
PUSH A PUSH B ADD
After:
PUSH A
the stack contains:
Top → 10
After:
PUSH B
the stack becomes:
Top → 5 10
Now execute:
ADD
The CPU takes the required operands from the top of the stack, performs the addition, and places the result back on the stack.
Result:
Top → 15
Conceptually:
5 + 10 → 15
Why Are Stack Instructions Called Zero-Address Instructions?
This is an important connection to our previous article on instruction format.
Consider:
ADD
There are no explicit register or memory addresses in the instruction.
Why?
Because the CPU already knows where the operands are:
The top of the stack.
Therefore, stack arithmetic instructions are commonly described as zero-address instructions.
Compare:
Accumulator: ADD X
General Register: ADD R1, R2
Stack: ADD
The stack itself provides the operands.
Stack Evaluation of an Expression
Stack organization is particularly useful for evaluating arithmetic expressions.
Consider:
(A + B) × C
A stack machine could use:
PUSH A PUSH B ADD PUSH C MUL
Let's follow the stack.
Step 1
PUSH A
Top → A
Step 2
PUSH B
Top → B A
Step 3
ADD
Top → A + B
Step 4
PUSH C
Top → C A + B
Step 5
MUL
Top → (A + B) × C
The expression can therefore be evaluated without explicitly naming registers for every operation.
Stack Organization and the ALU
The ALU still performs the actual arithmetic or logical operation.
The difference is where the operands come from.
A simplified flow is:
Stack
/ \
Operand A Operand B \ / \ / ALU │ ▼ Stack
For example:
Top → B A
The CPU sends these operands to the ALU.
After the operation:
Top → A + B
Stack and the CPU Datapath
A simplified stack-based datapath might look like:
┌──────────────┐
│ Control Unit │
└──────┬───────┘
│
▼
Stack
│
▼
ALU
│
▼
Stack
The Control Unit determines which operation should occur.
The stack provides operands.
The ALU performs the operation.
The result returns to the stack.
Advantages of Stack Organization
- Simple Instructions
Instructions don't need to specify operand addresses for many operations.
For example:
ADD SUB MUL
can operate directly on stack operands.
- Compact Instruction Format
Because operands are implicit, instructions can be smaller.
This can reduce the amount of information that needs to be encoded in each arithmetic instruction.
- Simple Expression Evaluation
Expressions can be evaluated naturally using push, pop, and arithmetic operations.
For example:
(A + B) × C
can be converted into a sequence of stack operations.
- Useful for Function Execution
Stacks are also heavily used for:
Function calls
Local variables
Return information
Temporary values
This is one reason the concept of a stack is extremely important when you later study operating systems and assembly language.
Disadvantages of Stack Organization
- Limited Random Access
The stack is optimized for accessing the top.
If you need a value deep inside the stack, accessing it directly can be inconvenient.
- More Stack Operations
Complex calculations may require many PUSH and POP operations.
- Stack Management
The processor must carefully manage the Stack Pointer and stack contents.
Incorrect stack management can lead to incorrect results or program failures.
Stack Organization vs General Register Organization
Feature
Stack Organization
General Register
Operand location
Stack top
Registers
Typical instruction
Zero-address
Two/three-address
Operand naming
Usually implicit
Explicit
Random operand access
Less convenient
Convenient
Expression evaluation
Natural
Requires explicit registers
Register requirements
Fewer explicit operand registers
More registers
The key difference is:
Stack CPU → operands are implied by their position on the stack.
General-register CPU → operands are explicitly identified by registers.
Stack Organization vs Accumulator Organization
These two designs also differ significantly.
Accumulator
ADD X
Conceptually:
AC ← AC + M[X]
One operand is implicitly in the accumulator.
Stack
ADD
Both operands are implicitly taken from the stack.
So:
Accumulator → One implicit operand
Stack → Operands are obtained from stack position
Stack Organization and Postfix Expressions
Stack machines are closely related to postfix notation, also called Reverse Polish Notation (RPN).
For example:
(A + B) × C
can be represented as:
A B + C ×
The stack can then evaluate the expression naturally:
PUSH A PUSH B ADD PUSH C MUL
This is one reason stack-based architectures are useful for understanding how expressions can be evaluated mechanically.
Register Stack vs Memory Stack
A stack can be implemented using different kinds of storage.
Register Stack
The stack is primarily maintained using CPU registers.
CPU └── Register Stack
This can provide very fast access but has limited capacity.
Memory Stack
The stack is primarily stored in main memory.
CPU │ ▼ Main Memory └── Stack
This provides much more storage but generally involves memory accesses.
We'll examine these two approaches separately.
Stack Overflow and Underflow
Stacks also have important limitations.
Stack Overflow
Occurs when a program attempts to push more data than the available stack capacity can accommodate.
Conceptually:
Stack Full ↓ PUSH ↓ Overflow
Stack Underflow
Occurs when a program attempts to remove data from an empty stack.
Stack Empty ↓ POP ↓ Underflow
The exact behavior depends on the implementation and architecture.
Why Stack Organization Matters
Even if you never design a stack-based CPU, understanding this organization is valuable.
Stacks appear throughout computing:
CPU architecture
Assembly language
Function calls
Operating systems
Compilers
Programming languages
Interrupt handling
Embedded systems
When you later study how function calls work at the machine level, the stack will become especially important.
Final Thoughts
Stack organization uses the top of a stack as the primary source of operands.
Its central idea is:
PUSH operands ↓ ALU operation ↓ Result pushed back
Because operands are implicitly determined by their position on the stack, arithmetic instructions can use a zero-address format.
For example:
PUSH A PUSH B ADD
instead of explicitly writing:
ADD R1, R2
The trade-off is that stack machines can require more stack manipulation and provide less convenient random access to operands.
We've now covered the basic idea of stack-based CPU organization.
Next, we'll go deeper into how a stack can be implemented using CPU registers.
Next: Register Stack Organization.