Stacks and queues

Many problems ask you to process items in a specific order, and the order alone tells you which structure to reach for. A stack works like a stack of plates: you add and remove from the top. A queue works like a line at a counter: you add at the back and remove from the front.

Stacks: LIFO

A stack stores items in last-in, first-out order. The last item you push is the first one you pop. Reach for a stack whenever you need to undo something, or match pairs that nest inside each other.

A classic example: given a string of brackets, decide whether every bracket is matched and properly nested.

1(())  - valid2()()  - valid3([)]  - invalid, the brackets cross4(()   - invalid, one bracket is never closed

Walk through the string one character at a time. Push every opening bracket. On a closing bracket, pop the stack and check that it holds the matching opener; if the stack is empty, or the popped opener does not match, the string is invalid. If any openers are left on the stack once you reach the end, something was never closed.

The stack is what makes this work. It always hands you the most recently opened bracket first, which is exactly the one a closing bracket has to match if the nesting is valid. That is also why ([)] fails even though it has one of each bracket: the ] arrives while ( is still the top of the stack, and ( does not close with ].

1def matches(s):2    stack = []3    pairs = {'(': ')', '[': ']', '{': '}'}4    for c in s:5        if c in pairs:6            stack.append(c)7        else:8            if not stack or pairs[stack.pop()] != c:9                return False10    return len(stack) == 011
12
13print(matches("(())"))14print(matches("()()"))15print(matches("([)]"))16print(matches("(()"))

True
True
False
False

The pairs dictionary maps each opening bracket to the closer it needs, so the same stack handles (), [] and {} at once. matches("(())") and matches("()()") are both True. matches("([)]") is False: the brackets cross rather than nest. matches("(()") is False: the stack still has an unmatched ( when the string ends.

A stack shows up outside matching problems too. A text editor's undo feature pushes each edit as it happens; pressing undo pops the most recent one and reverses it, which is exactly LIFO order.

Queues: FIFO

A queue stores items in first-in, first-out order. The first item you add is the first one you remove. Reach for a queue whenever items need to be handled in the order they arrived, such as a restaurant serving orders as customers place them.

A Python list can append to its end quickly, but removing from its front is slow: every remaining item has to shift one place left. The collections.deque type does not have that problem. append() adds to the back and popleft() removes from the front, and both run in constant time regardless of how long the queue is.

1from collections import deque2
3orders = ['pizza', 'burger', 'salad', 'pasta']4queue = deque(orders)5
6print("Processing orders in order:")7while queue:8    order = queue.popleft()9    print(f"Served: {order}")

Processing orders in order:
Served: pizza
Served: burger
Served: salad
Served: pasta

The orders come out in the same order they went in, pizza first and pasta last, because popleft() always takes the oldest remaining item.

Choosing the right structure

Matching and nesting problems usually need a stack. Problems about arrival order, scheduling, or breadth-first search usually need a queue.

If every addition and removal happens at the same end, that is a stack, and a plain Python list works fine for it. If additions happen at one end and removals at the other, that is a queue, and you want deque rather than a list.

1from collections import deque2
3queue = deque()4queue.append(1)5queue.append(2)6queue.append(3)7
8print(queue.popleft())9print(queue.popleft())10print(queue.popleft())

1
2
3

A deque is both

collections.deque is not only a queue. Its name is short for "double-ended queue", and it appends and pops in constant time from either end: append()/pop() at the back, appendleft()/popleft() at the front. That means a deque can play the role of a stack too, so once you have imported it for one problem, you rarely need a second import for the other. The bracket-matching example above could use a deque and call append()/pop() on it exactly as it calls those methods on a plain list; the two structures agree on how to add and remove from a single end. The only place a list falls short is removing from the other end, which is precisely why a plain list is fine as a stack but wrong as a queue.

This also explains why the choice between "stack" and "queue" is really a choice about which end of the data you need, not two unrelated tools. A sliding-window problem that needs the smallest or largest value in a moving window, for instance, keeps a deque of candidate indices and removes from both ends: it pops from the back to drop candidates that a new, better one has made useless, and pops from the front to drop candidates that have aged out of the window. That pattern, a monotonic deque, reuses the exact two operations this lesson introduces; a later lesson builds it out in full.

Getting these right

The most common slip is using a list as a queue with pop(0). Each call has to shift every remaining item, so on a queue of 10,000 items, a single pop(0) costs O(n) and processing the whole queue costs O(n²). deque.popleft() does the same job in O(1), so the whole queue drains in O(n) total.

Stack and queue order are also easy to swap in your head. A stack of plates gives you the plate you set down most recently; a line at a counter serves the person who arrived first. If your output looks reversed, check which end you are removing from.

And when brackets come in more than one kind, matching counts is not enough. ( must close with ), [ with ], and { with }. A stack that only tracks how many brackets are open, without tracking which kind, will accept ([)] by mistake. Track the actual bracket, as the pairs dictionary above does, and the type gets checked along with the nesting.