COA Notes
HubARM ArchitectureCISC ArchitectureCloud Computing HardwareEmbedded Processor ArchitectureModern CPU DesignRISC Architecturex86 ArchitectureALU DesignBinary AdditionBinary SubtractionCarry Lookahead AdderDivision AlgorithmsFloating Point ArithmeticMultiplication AlgorithmsAddressing TechniquesAssembly InstructionsAssembly Language IntroductionAssembly Program ExamplesLoops in AssemblyProcedure CallsARM Processor Case StudyIntel 8086 ArchitectureModern Intel CPURaspberry Pi ArchitectureSmartphone Processor ArchitectureBasic Computer StructureBus SystemFetch-Decode-Execute CycleInstruction CyclePerformance MetricsSystem ComponentsControl UnitCPU ArchitectureGeneral Purpose RegistersHardwired Control UnitMicroprogrammed Control UnitProcessor RegistersStack OrganizationBinary Arithmetic — Computer Organization & ArchitectureCharacter Encoding — Computer Organization & ArchitectureError Detection CodesFloating Point RepresentationIEEE 754 StandardNumber Systems ReviewSigned Number RepresentationDirect Memory Access (DMA)Interrupt-Driven I/OI/O InterfaceI/O ProcessorsPeripheral DevicesProgrammed I/OUSB and Modern InterfacesAddressing ModesInstruction ExecutionInstruction FormatInstruction TypesMachine Language BasicsRISC vs CISCCache Memory QuestionsCOA CheatsheetComputer Organization Interview QuestionsGATE COA QuestionsPipelining QuestionsComputer Organization vs ArchitectureEvolution of ComputersFunctional Units of ComputerVon Neumann ArchitectureWhat is Computer Organization?Associative MemoryCache Mapping TechniquesCache Memory — Computer Organization & ArchitectureMain MemoryMemory Hierarchy — Computer Organization & ArchitectureMemory PerformanceRAM and ROMVirtual Memory — Computer Organization & ArchitectureDistributed ProcessingGPU ArchitectureMulticore ProcessorsParallel Processing BasicsShared Memory SystemsSuperscalar ArchitectureVector ProcessingControl HazardsData HazardsForwarding TechniquesInstruction PipelinePipeline HazardsPipeline IntroductionPipeline PerformanceALU Design ProjectAssembly Language LabsCache SimulationComputer Architecture ProjectsPipeline SimulationArithmetic Logic Unit (ALU)Arithmetic Micro-operationsLogic Micro-operationsRegister Transfer LanguageRegister Transfer OperationsShift Micro-operationsGlossary of Terms — Computer Organization & ArchitectureImportant Formulas — Computer Organization & ArchitectureQuick Revision Notes — Computer Organization & ArchitectureRecommended Books — Computer Organization & Architecture
Stack-based CPU organization, stack operations, register stack vs memory stack, and stack applications.
Introduction
A stack is a Last-In-First-Out (LIFO) data structure that plays a crucial role in computer organization. Whether it's a hardware register stack inside the CPU or a memory-based stack managed by the stack pointer, stacks are everywhere — handling function calls, evaluating expressions, managing interrupts, and even forming the basis of entire CPU architectures. Understanding stack organization helps you see how programs actually execute at the hardware level.
What is a Stack?
A stack is a linear list where insertions and deletions happen at one end only (the "top"):
- PUSH: Add an item to the top of the stack
- POP: Remove the item from the top of the stack
| PUSH 'A' | [A] (stack has 1 item) |
| PUSH 'B' | [A][B] (stack has 2 items, B on top) |
| PUSH 'C' | [A][B][C] (stack has 3 items, C on top) |
| POP | [A][B] (C removed, B is new top) |
| POP | [A] (B removed, A is new top) |
Register Stack
A register stack is implemented entirely in hardware using a fixed set of registers:
┌─────────┐
│ Empty │ ← SP points here when stack is full+1
├─────────┤
│ Reg[63] │
├─────────┤
│ Reg[62] │
├─────────┤
│ ... │
├─────────┤
│ Reg[2] │
├─────────┤
│ Reg[1] │ ← SP (Stack Pointer) — current top
├─────────┤
│ Reg[0] │
└─────────┘
PUSH Operation
Example
SP ← SP + 1 ; Point to next empty location
Stack[SP] ← Data ; Write data to that location
if (SP = max_size) then FULL ← 1 ; Overflow check
EMPTY ← 0 ; Stack is not empty
POP Operation
Example
Data ← Stack[SP] ; Read data from top
SP ← SP - 1 ; Point to new top
if (SP = 0) then EMPTY ← 1 ; Underflow check
FULL ← 0 ; Stack is not full
Characteristics
- Fixed size (determined at design time)
- Very fast (register access speed)
- Limited capacity (typically 8-64 entries)
- Used for expression evaluation in some architectures
Memory Stack
A memory stack uses a region of main memory, with a register (SP) pointing to the current top:
High addresses ┌─────────────────┐
│ ... │
├─────────────────┤
SP → │ Top of Stack │ (most recently pushed)
├─────────────────┤
│ Previous item │
├─────────────────┤
│ Previous item │
├─────────────────┤
│ ... │
├─────────────────┤
│ Bottom of Stack│ (first item pushed)
Low addresses └─────────────────┘
Convention: Stack Grows Downward
In most architectures (x86, ARM, MIPS), the stack grows toward LOWER addresses:
- PUSH: SP ← SP - 1; M[SP] ← Data (decrement then store)
- POP: Data ← M[SP]; SP ← SP + 1 (read then increment)
Advantages over Register Stack
- Virtually unlimited size (constrained only by available memory)
- Flexible (can grow as needed)
- Supports deep recursion
Disadvantages
- Slower (memory access instead of register access)
- Requires memory bus bandwidth
Stack Applications in CPU Organization
1. Function Calls and Returns
When a function is called:
Code example
CALL function_address:
PUSH PC ; Save return address on stack
PC ← function_address ; Jump to function
RETURN:
POP PC ; Restore return address
; Execution continues after the CALL2. Stack Frame (Activation Record)
Each function call creates a stack frame containing:
┌─────────────────┐ ← Previous SP
│ Arguments │ (parameters passed by caller)
├─────────────────┤
│ Return Address │ (where to continue after return)
├─────────────────┤
│ Saved Registers│ (callee-saved registers)
├─────────────────┤
│ Local Variables│ (function's local data)
├─────────────────┤ ← Current SP
3. Expression Evaluation (Postfix/RPN)
Stack machines evaluate expressions using postfix notation:
Infix: (3 + 4) × (5 - 2) Postfix: 3 4 + 5 2 - ×
Evaluation:
Example
Token Action Stack
3 PUSH 3 [3]
4 PUSH 4 [3, 4]
+ POP 4, POP 3, [7]
PUSH 3+4=7
5 PUSH 5 [7, 5]
2 PUSH 2 [7, 5, 2]
- POP 2, POP 5, [7, 3]
PUSH 5-2=3
× POP 3, POP 7, [21]
PUSH 7×3=21
Result: 21
4. Interrupt Handling
When an interrupt occurs:
Example
PUSH PC ; Save current execution point
PUSH PSW ; Save processor status (flags)
PC ← Interrupt_handler_address
; ... service the interrupt ...
POP PSW ; Restore status
POP PC ; Return to original execution
5. Stack-Based Architectures
Some processors use a stack as the primary computation model:
- Java Virtual Machine (JVM): Operands pushed, operations pop and push results
- Forth language: Designed around explicit stack manipulation
- HP calculators: Used Reverse Polish Notation (RPN) with hardware stack
Stack Operations in Assembly
x86 Stack Instructions
Example
PUSH EAX ; ESP ← ESP-4; M[ESP] ← EAX
POP EBX ; EBX ← M[ESP]; ESP ← ESP+4
CALL function ; PUSH EIP; EIP ← function
RET ; POP EIP
PUSHA ; Push all general registers
POPA ; Pop all general registers
Key Takeaways
- A stack is a LIFO structure accessed only at the top via PUSH and POP
- Register stacks are fast but small (hardware registers); memory stacks are slow but large
- Most architectures grow the stack downward (toward lower addresses)
- Stacks are essential for function calls (saving return addresses and local variables)
- Stack frames organize parameters, return address, saved registers, and locals
- Expression evaluation uses postfix notation with a stack for operands
- Interrupt handling uses the stack to save and restore processor state
- Stack-based architectures (JVM, Forth) use the stack as the primary computation model
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Stack Organization.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Computer Organization & Architecture topic.
Search Terms
computer-organization, computer organization & architecture, computer, organization, cpu, stack, stack organization
Related Computer Organization & Architecture Topics
Continue learning this concept
Cpu OrganizationControl UnitCPU control unit design, functions, control signal generation, and coordination of processor operations.Cpu OrganizationCPU ArchitectureCPU internal architecture, datapath design, register organization, and control flow mechanisms.Cpu OrganizationGeneral Purpose RegistersGeneral purpose register file design, register allocation, and register-based computation models.Cpu OrganizationHardwired Control UnitHardwired control unit design, state machine implementation, advantages and limitations.Cpu OrganizationMicroprogrammed Control UnitMicroprogrammed control unit design, control memory, microinstructions, and microprogram sequencing.Cpu OrganizationProcessor RegistersTypes of CPU registers: general purpose, special purpose, status registers, and their roles.