Stacks (LIFO)
Build a last-in first-out stack with one pointer that refuses bad pushes and pops. Then choose between RAM and a shift register.
You Will Be Able To
- Explain last-in first-out order and where a stack is used.
- Keep a stack with one pointer, and derive full and empty from it.
- Refuse a push to a full stack and a pop from an empty one.
- Compare a stack in RAM with a shift-register stack.
- Lesson
- G8.10
- Time
- 25 min
- Runs on
- Your browser
- Check
- 4 questions
A parser kept nested brackets on a hardware stack. One malformed line closed one bracket too many. From then on the parser lost every word it pushed.
slots shows the slots in use, bit 0 at the right.- Cycle 3
Two pushes and two pops: the stack is empty again.
- Cycle 4
A third pop. Nothing refuses it, so the pointer goes from 0 to 7. The count says 7 and the top is unknown.
- Cycle 5
Push 33. It goes to slot 3, and the pointer wraps from 7 to 0. The stack says it is empty: 33 is lost.
Measured on Icarus Verilog: the example of this lesson as it ships.
Last in, First Out
A stack gives back the newest word first. A push puts a word on top. A pop takes the top word away. The word under it is then the top.
- I/O
- Storage
A filled slot holds a word. The top of the stack is the highest filled slot.
- Cycle 1
Two pushes: 11 in slot 0, then 22 in slot 1. The top is 22, the newest word.
- Cycle 3
Two pops: first 22 leaves, then 11. The stack is empty.
- Cycle 4
A third pop is refused, because the stack is empty. Nothing changes.
- Cycle 8
Four pushes fill all four slots.
fullis 1. - Cycle 9
A fifth push is refused. The top stays 66, and 77 is not stored.
Measured on Icarus Verilog: the example with the pop refused when empty.
A processor keeps return addresses on a stack: the last call made is the first one to return. Parsers keep open brackets on a stack. An undo list is a stack of changes.
One Pointer: Full and Empty
A FIFO needs two pointers, one to write and one to read (lesson G8.2). A stack writes and reads at the same end, so one pointer is enough.
| Operation | Slot used | Pointer after | Refused when |
|---|---|---|---|
| push | mem[sp] | sp + 1 | full: sp = depth |
| pop | mem[sp - 1] leaves | sp - 1 | empty: sp = 0 |
| top | mem[sp - 1] | unchanged | shows 00 when empty |
sp counts the words. It is also the index of the next free slot.
The pointer counts from 0 to the depth, so it needs one bit more than the slot index. For four slots it is 3 bits wide.
Pop always moves the pointer
else if (pop) sp <= sp - 3'd1;
Icarus: count=7 after the extra pop, and 33 is lost.
Pop refused when empty
else if (pop && !empty) sp <= sp - 3'd1;
Icarus: the count stays 0, and 33 lands in slot 0.
In RAM or in a Shift Register
A stack can also be a shift register. A push shifts every word down one place and puts the new word in place 0. A pop shifts every word up. The top is always place 0.
- I/O
- Storage
- Datapath
- Data
- RAM style
The pointer picks one slot to write, and a multiplexer reads the top. Only one word changes per cycle, so any RAM can hold it.
- Shift style
Every place takes its neighbour on each push or pop. No address decoder and no read mux, but every word moves.
Read the diagram as text
- Pushed word: din
- RAM and pointer: one word written per push
- Read mux: top = mem[sp - 1]
- Shift register: every word moves per push
- Place 0: top, no mux
- Pushed word → RAM and pointer: write at sp
- RAM and pointer → Read mux: read at sp - 1
- Pushed word → Shift register: into place 0
- Shift register → Place 0: always place 0
Both need a counter for full and empty.
| Depth | RAM style | Shift style | Flip-flops (both) |
|---|---|---|---|
| 4 | 114 cells | 85 cells | 35 |
| 16 | 436 cells | 295 cells | 133 |
Measured with Yosys on 8-bit stacks built from flip-flops, with full and empty refusals.
From flip-flops, the shift style is smaller here: it needs no decoder and no read mux. But every word toggles on every push and pop, which costs power. In an SRAM only the pointer style is possible.
Asked in interviews
Design a hardware stack.
An array and one pointer that counts the words. A push writes at the pointer and adds one; a pop subtracts one. Full is pointer = depth and empty is pointer = 0. Refuse a push when full and a pop when empty.
Stack or FIFO?
A FIFO returns words in arrival order and needs a read and a write pointer. A stack returns the newest word first and needs one pointer. Calls and nesting want a stack; streams want a FIFO.
Why is the stack pointer one bit wider than the index?
A stack of N slots has N + 1 states, from empty to full. An index of log2 N bits cannot tell an empty stack from a full one, so the pointer needs one more bit.
Try It
The bench pushes 11 and 22, pops three times, then pushes 33, 44, 55, 66 and 77. One line per clock edge.
Line e4 shows the stack empty. Line e5 is the extra pop: count=7 and top=xx. Line e6 pushes 33, and the count wraps to 0 with empty=1.
Fix the pop line: a pop must be refused when empty is 1. Run again.
Line e5 now keeps count=0. 33 becomes the top at e6, the stack is full at e9, and the push of 77 at e10 is refused.
Synthesize the design to measure its cells and inspect the mapped gates.
e1 push=1 pop=0 din=11 count=1 top=11 full=0 empty=0 e2 push=1 pop=0 din=22 count=2 top=22 full=0 empty=0 e3 push=0 pop=1 din=00 count=1 top=11 full=0 empty=0 e4 push=0 pop=1 din=00 count=0 top=00 full=0 empty=1 e5 push=0 pop=1 din=00 count=7 top=xx full=0 empty=0 e6 push=1 pop=0 din=33 count=0 top=00 full=0 empty=1 e7 push=1 pop=0 din=44 count=1 top=44 full=0 empty=0 e8 push=1 pop=0 din=55 count=2 top=55 full=0 empty=0 e9 push=1 pop=0 din=66 count=3 top=66 full=0 empty=0 e10 push=1 pop=0 din=77 count=4 top=77 full=1 empty=0Original design · 113 cells · 35 flip-flops · 0 latches · 6 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv: the bench (read-only). It pushes 11 and 22, pops three times (one too many), pushes 33,
// then pushes until the stack is full. One line per clock edge.
`timescale 1ns/1ps
module tb;
logic clk = 0, rst = 1, push = 0, pop = 0;
logic [7:0] din = 0;
wire [7:0] top;
wire [2:0] count;
wire full, empty;
int n = 0;
stack4 dut (.*);
always #5 clk = ~clk;
task automatic step(input logic do_push, input logic do_pop, input logic [7:0] d);
push = do_push; pop = do_pop; din = d;
@(posedge clk); #1 n++;
$display("e%0d push=%b pop=%b din=%h count=%0d top=%h full=%b empty=%b", n, do_push, do_pop, d, count, top, full, empty);
endtask
initial begin
@(posedge clk); #1 rst = 0;
step(1, 0, 8'h11); step(1, 0, 8'h22);
step(0, 1, 8'h00); step(0, 1, 8'h00); step(0, 1, 8'h00);
step(1, 0, 8'h33); step(1, 0, 8'h44); step(1, 0, 8'h55); step(1, 0, 8'h66); step(1, 0, 8'h77);
$finish(0);
end
endmodule
Check Yourself
Common Mistakes
Wrong Let a pop through when the stack is empty.
The pointer wraps: on Icarus the lab shows count=7 after the extra pop, and the next push is lost.
Fix Refuse a pop when empty is 1, just as a push is refused when full is 1.
else if (pop) sp <= sp - 3'd1;else if (pop && !empty) sp <= sp - 3'd1;Wrong Make the pointer just wide enough to index the slots.
Four slots need 2 index bits, but the count runs from 0 to 4: five values. With 2 bits, a full stack and an empty stack look the same.
Fix Use one more bit than the index needs, and take the slot index from the low bits.
Wrong Read the top from the slot the pointer names.
The pointer names the next free slot. The top word is one below it, so the read is one slot too high.
Fix Read mem[sp - 1], and show a fixed value when the stack is empty.
Wrong Build a deep stack as a shift register inside an SRAM.
A shift moves every word on every push and pop. An SRAM can change only one word per cycle.
Fix Use a pointer for an SRAM stack. Keep shift-register stacks for small stacks built from flip-flops.
Remember
- A stack is last in, first out: push puts a word on top, pop takes it off.
- One pointer counts the words and names the next free slot. The top is one slot below it.
- The pointer needs one bit more than the slot index: empty is 0, full is the depth.
- Refuse a push when full and a pop when empty, or the pointer wraps.
- A shift-register stack needs no decoder, but moves every word; an SRAM stack must use a pointer.