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.

A Pop from an Empty StackEach column is one clock edge. slots shows the slots in use, bit 0 at the right.
0123456789clkpushpopdin1122003344556677count1210701234top11221100x0044556677slots0001001100010000xxxx00000001001101111111one pop too many
Scroll horizontally ↔
  1. Cycle 3

    Two pushes and two pops: the stack is empty again.

  2. 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.

  3. 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.

Push, Pop and the RefusalsEach column is one clock edge. The filled slots are the words on the stack.
  • I/O
  • Storage
pushpopProducerpush and popStackslot 0 at the bottom0123
push→ Stackpop→ ProducerProducerpush and popStackslot 0 at the bottom0123

A filled slot holds a word. The top of the stack is the highest filled slot.

0123456789clkpushpopdin1122003344556677count12101234top1122110033445566slots00010011000100000001001101111111
Scroll horizontally ↔
  1. Cycle 1

    Two pushes: 11 in slot 0, then 22 in slot 1. The top is 22, the newest word.

  2. Cycle 3

    Two pops: first 22 leaves, then 11. The stack is empty.

  3. Cycle 4

    A third pop is refused, because the stack is empty. Nothing changes.

  4. Cycle 8

    Four pushes fill all four slots. full is 1.

  5. 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.

OperationSlot usedPointer afterRefused when
pushmem[sp]sp + 1full: sp = depth
popmem[sp - 1] leavessp - 1empty: sp = 0
topmem[sp - 1]unchangedshows 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.

Two Ways to Keep a StackArrows show where a pushed word goes in each style.
  • I/O
  • Storage
  • Datapath
  • Data
Two ways to keep a stackArrows show where a pushed word goes in each style. io Pushed word din storage RAM and pointer one word written perpush datapath Read mux top = mem[sp - 1] storage Shift register every word moves perpush storage Place 0 top, no mux write at spread at sp - 1into place 0always place 0
  1. io Pushed worddin
    • write at sp → RAM and pointer
    • into place 0 → Shift register
  2. storage RAM and pointerone word written per push
    • read at sp - 1 → Read mux
  3. datapath Read muxtop = mem[sp - 1]
  4. storage Shift registerevery word moves per push
    • always place 0 → Place 0
  5. storage Place 0top, no mux
  1. 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.

  2. 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.

DepthRAM styleShift styleFlip-flops (both)
4114 cells85 cells35
16436 cells295 cells133

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
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: 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=0

Original 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

Predict the outputThis shift-register stack keeps the top in s[0]. What exact line does the program print?
module tb;
  int s [4];                             // a shift-register stack: s[0] is the top
  task automatic push(input int v);
    for (int i = 3; i > 0; i--) s[i] = s[i - 1];
    s[0] = v;
  endtask
  task automatic pop();
    for (int i = 0; i < 3; i++) s[i] = s[i + 1];
    s[3] = 0;
  endtask
  initial begin
    foreach (s[i]) s[i] = 0;
    push(5); push(6); push(7); pop(); push(8);
    $display("%0d %0d %0d %0d", s[0], s[1], s[2], s[3]);
  end
endmodule
Spot the bugEach option is the full line of the four-slot stack. The bench pushes five words and then pops four. Which option fails?
ConceptWhich structure gives words back in the order they arrived?
ConceptWhat does a processor keep on a stack when it calls a function?

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.

Before
else if (pop) sp <= sp - 3'd1;
After
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.

Practice

Report a problem with this page