Stacks and queues: work at the ends

You press undo, and the last thing you typed disappears, then the thing before it. A printer works the other way round: the job sent first prints first, however many arrive after it.

Those are the two simplest rules for what comes back out of a collection. A stack hands back the newest item and a queue the oldest. Both only ever touch their ends, so both can sit on an array without the shifting that makes an array's front expensive. For the queue that takes one trick: letting the array wrap around into a ring.

stack (LIFO)

Last in, first out. Push puts a value on top, pop takes the top one off, and peek reads it without removing it.

queue (FIFO)

First in, first out. Enqueue adds a value at the back and dequeue removes the one at the front.

top, head and tail

Indices that mark the ends. A stack's top points at its newest value. A queue's head points at its front value, and its tail at the free slot where the next value joins.

ring buffer

An array whose last slot is followed by slot 0 again. An index that steps past the end wraps around: next = (i + 1) mod capacity.

deque

A double-ended queue, said "deck": values go in and come out at both the front and the back.

This stack holds 7, 23 and 42 in an array of 8 slots. Slot 0 is the bottom, and the index top marks the newest value, so 42 is on top.

Push moves top up one and writes one slot; pop reads one slot and moves top down. Nothing below the top is touched, so both are O(1) whether the stack holds 3 values or 3 million. A stack only uses the end of its array, which is the cheap end, so a Python list or a JavaScript array is already a good stack: append and pop work on the last element.

A queue is harder. Values join at the back and leave from the front, and the front is an array's expensive end: removing index 0 shifts every remaining value one cell left, so each dequeue would be O(n). A queue avoids that by moving the front instead of the values. An index, head, marks the front value, and dequeue reads that slot and steps head forward.

As head steps forward it leaves free slots behind it, at the start of the array, while tail runs on towards the end. When tail steps past the last slot it wraps around to slot 0 and reuses them, so the array behaves like a ring. Both indices step with (i + 1) mod capacity, and the next free slot is always tail = (head + count) mod capacity.

Before each step, predict which value comes out and where head or tail points next. Enqueue until tail wraps, then dequeue a few times and watch head follow it round.

A stack fits whenever the most recent thing must be dealt with first. Matching brackets is the classic case: in {[()]} every closing bracket must match the most recently opened bracket that is still open, and in ([)] the ) comes too early. So push each opening bracket, and at each closing bracket pop one and check that the two match.

def balanced(text):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in text:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(balanced('{[()]}'))
print(balanced('([)]'))

The same shape turns up everywhere. A program's call stack pushes a frame for each call and pops it on return, so the most recent call always finishes first (the recursion lesson shows it frame by frame). An editor's undo history is a stack, and so is the list of places a depth-first search still has to go back to.

A queue fits whenever work must be handled in the order it arrived: print jobs, requests waiting for a server, messages passed between programs. A breadth-first search keeps the nodes it has found but not yet explored in a queue, and that is what makes it visit a graph level by level: the nodes found first are explored first. The queueing lesson follows requests through the queue in front of a busy server.

The trap is building a queue on a plain list. Appending at the back is cheap, but taking from the front is not.

A deque lets values in and out at both ends. In a ring it is a queue with two more moves: push front steps head back one slot, wrapping from slot 0 to the last slot, and pop back steps tail back one slot.

The ring raises one more question: how does a queue know it is full? An empty queue has tail = head. Enqueue until all 8 slots are used and tail comes all the way round to head again. The two indices alone can't tell an empty ring from a full one, so the queue also keeps count. (Another common fix is to leave one slot always empty.)

• A stack is last in, first out. Push and pop only touch the top, which on an array is an index, so both are O(1).
• A queue is first in, first out: enqueue at the back, dequeue at the front. Removing index 0 of a plain array shifts everything, so a list with pop(0) is an O(n) queue.
• A ring buffer moves head and tail instead of the values, wrapping with (i + 1) mod capacity, so enqueue and dequeue are O(1). It is full when count reaches the capacity, not when tail wraps to 0.
• A deque is O(1) at both ends, so it can be a stack or a queue. Stacks run the call stack, undo and bracket matching; queues run breadth-first search, print jobs and request queues.
• Next: linked lists, another way to get cheap ends, and breadth-first search, which explores a graph with a queue. Practise with Valid Brackets and Stack with Minimum, or open the stack, queue and deque visualisers to try more operations.