Stacks and Queues

A stack is the spring-loaded plate dispenser at the cafeteria. A dishwasher walks by with a clean plate and sets it on top. The plate already there gets pushed down an inch by the spring. The next student walks up and takes a plate — but only the top one, because that is the only plate the dispenser hands out. The last plate the dishwasher put on is the first plate the student takes off. Every other plate has to wait its turn from the top. That is the whole rule of a stack — last in, first out.

The cafeteria did not invent this idea. A German computer scientist named Friedrich Bauer did, in 1955, while working out how a compiler should evaluate an arithmetic expression. He needed a place to put numbers he was not done with yet — read 3, set it aside, read +, read 4, set it aside, hit the =, grab the two numbers back in the reverse order he put them down, add them. Bauer called the structure a Keller — German for "cellar" — because the newest item always sat right at the top of the stairs and the older items were buried below. The English-speaking world translated it to "stack" and the name stuck. Every CPU in your house uses a stack the same way Bauer did, for function calls — push a return address when you enter a function, pop it when you leave.

A stack in Rust is just a Vec<T> with three of its methods renamed to match how Bauer would have said them. push puts a plate on top, pop takes a plate off the top and hands it back, peek lets the student see the top plate without grabbing it. The Vec already does all the hard work — growing the underlying memory, freeing it when the stack is dropped. The wrapper is there to refuse any move that is not push, pop, or peek, so nobody on your team can reach into the middle and grab plate number 3.

struct Stack<T> {
    items: Vec<T>,
}

impl<T: Debug> Stack<T> {
    fn new() -> Self {
        Stack { items: Vec::new() }
    }

    fn push(&mut self, value: T) {
        self.items.push(value);
    }

    fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    fn peek(&self) -> Option<&T> {
        self.items.last()
    }

    fn len(&self) -> usize {
        self.items.len()
    }
}

The Vec<T> lives inside items. Every method is one line because every method already exists on Vec — push is Vec::push, pop is Vec::pop, peek is Vec::last. The point of the wrapper is the closed door. A Stack<T> does not expose items, so a caller cannot index in or insert in the middle. The only way to touch a plate is from the top. That restriction is the contract that lets you reason about the order things come out.

The cafeteria has a second line, and it follows the opposite rule. The coffee counter has a velvet rope. Students walk in at the back, shuffle forward one step at a time as the barista hands out cups at the front, and leave when their turn comes. The first student in line is the first student served. The last student to walk in is the last student served. Nobody cuts. That is the rule of a queue — first in, first out.

You could build a queue out of Vec<T> the same way you built the stack, but it would be slow. Adding a student to the back of the line is easy — push on a Vec is fast. Serving the front student is the problem. Vec stores everything in one block of memory with the first element at the start, so removing the front means shifting every other element one slot to the left. With 500 students in line, every coffee served costs 500 shuffles. The fix is a structure called VecDeque — a "double-ended queue." Internally it is a circular buffer, which means the front of the line is just an index into the block, not the start of it. When you serve a student, you bump the front index forward by one. No shifting. Both ends are cheap. Rust's std::collections::VecDeque<T> is the same idea Donald Knuth wrote up in 1968 in The Art of Computer Programming, volume 1 — a ring of slots with two pointers walking around it.

A Queue<T> is a thin wrapper around VecDeque the same way Stack<T> was a thin wrapper around Vec. Two methods: enqueue to send a student to the back, dequeue to serve the student at the front. A front method to peek without serving. The shape mirrors the stack on purpose — same hidden field, same closed door, same three or four entry points.

struct Queue<T> {
    items: VecDeque<T>,
}

impl<T: Debug> Queue<T> {
    fn new() -> Self {
        Queue {
            items: VecDeque::new(),
        }
    }

    fn enqueue(&mut self, value: T) {
        self.items.push_back(value);
    }

    fn dequeue(&mut self) -> Option<T> {
        self.items.pop_front()
    }

    fn front(&self) -> Option<&T> {
        self.items.front()
    }

    fn len(&self) -> usize {
        self.items.len()
    }
}

push_back is the VecDeque method that adds a student at the back of the line. pop_front takes the student at the front and hands them a coffee. front returns a borrow of the next-served student without removing them. None of these shift the line. The circular buffer just spins.

The demo runs both structures with the same four-step pattern — push four numbers in, pop them all out, print the state on every operation so you can watch the rule play out.

fn run_stack_demo() {
    let mut plates: Stack<i32> = Stack::new();
    for n in [1, 2, 3, 4] {
        plates.push(n);
        println!("push {n} -> top {:?}, len {}", plates.peek(), plates.len());
    }
    while plates.len() > 0 {
        let top = plates.pop();
        println!("pop  {top:?} -> top {:?}, len {}", plates.peek(), plates.len());
    }
}

fn run_queue_demo() {
    let mut line: Queue<i32> = Queue::new();
    for n in [10, 20, 30, 40] {
        line.enqueue(n);
        println!("enq  {n} -> front {:?}, len {}", line.front(), line.len());
    }
    while line.len() > 0 {
        let served = line.dequeue();
        println!("deq  {served:?} -> front {:?}, len {}", line.front(), line.len());
    }
}

Each line of the output is one operation followed by the structure's state after it. For the stack, watch the top plate. For the queue, watch the front student. The numbers themselves tell the story.

-- stack: last plate on is first plate off --
push 1 -> top Some(1), len 1
push 2 -> top Some(2), len 2
push 3 -> top Some(3), len 3
push 4 -> top Some(4), len 4
pop  Some(4) -> top Some(3), len 3
pop  Some(3) -> top Some(2), len 2
pop  Some(2) -> top Some(1), len 1
pop  Some(1) -> top None, len 0

-- queue: first in line is first served --
enq  10 -> front Some(10), len 1
enq  20 -> front Some(10), len 2
enq  30 -> front Some(10), len 3
enq  40 -> front Some(10), len 4
deq  Some(10) -> front Some(20), len 3
deq  Some(20) -> front Some(30), len 2
deq  Some(30) -> front Some(40), len 1
deq  Some(40) -> front None, len 0

Read the stack block top to bottom. The dishwasher set down plates 1, 2, 3, 4 in that order. The top plate started as 1, then became 2, then 3, then 4 — newest plate on top every time. Then four students walked up. The first one got plate 4 because that was the top. The second got 3. The order came out backwards from the order it went in. Now read the queue block. The barista let students 10, 20, 30, 40 join the line in that order. The front of the line stayed 10 the whole time new students joined, because students join at the back. When the barista started serving, 10 was served first, then 20, then 30, then 40 — same order they walked in.

One question to sit with. Why does a Vec make a good stack but a poor queue? Because both of Vec's fast operations — push at the end, pop from the end — happen at the same end. A stack only ever touches one end, so Vec is a perfect fit. A queue touches both ends, and the front of a Vec is the slowest place to remove an element because every other element has to shift down. VecDeque solves the problem by making both ends cheap, at the cost of slightly more bookkeeping inside.

Both of these structures share a weakness. You can only see the front, or only see the top — never reach into the middle. If a student walks up and asks "is there a chocolate-glazed donut anywhere in the case," the only way to answer is to take every donut out, look at each one, and put them back. The next lesson swaps the velvet rope for a card catalog, where the question is answered in a single lookup no matter how many items are on the shelf.