Stacks and queues: why undo takes the newest item and a printer takes the oldest

Open a text editor, type three words, and press undo. The last thing you typed disappears first. Now think about a printer shared by an office: the first document sent is the first one printed. Both are lists of items waiting their turn, and the only difference is which item comes out next. That one difference has names: a stack and a queue.

Two lists, one rule each

A data structure is just a way of arranging items so that certain jobs are easy. A stack and a queue both hold items in order, and both allow only two basic moves: put an item in, and take an item out. They differ in the rule for taking.

A stack is last in, first out, often shortened to LIFO. Think of plates in a cafeteria: you add a plate on top and you take a plate from the top. Putting an item in is called push and taking it out is called pop.

A queue is first in, first out, or FIFO. It works like a line at a shop: people join at the back and the person at the front is served first. Joining is often called enqueue and leaving the front is dequeue.

Try it: same items, different order

Press Add item a few times. Each new item goes into both containers. Then press Take one and watch which item each container gives back.

If you added A, B and C and then took one, the stack gave you C and the queue gave you A. Nothing else changed. The items, their order of arrival and the number of moves are identical; only the rule for which one leaves is different.

Where stacks show up

Anything that needs to undo the most recent thing first is a stack. Undo in an editor keeps your changes in a stack. The Back button in a browser works the same way: each page you visit is pushed, and Back pops the latest one. Even your program's own record of unfinished function calls is called the call stack, because the function that started most recently must finish first.

Stacks are also how a program checks that brackets match. Read the text from left to right. Push every opening bracket. When you meet a closing bracket, pop the top and see whether it is the matching opener. Here is that idea in Python:

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)          # push
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False          # nothing to match, or wrong kind
    return not stack                  # anything left over is unmatched

print(balanced("(a[b]{c})"))   # True
print(balanced("(a[b)]"))      # False
print(balanced("(("))          # False

I ran this code and it printed exactly True, False, False. In the second example the ) arrives while [ is on top, so the match fails. A stack catches that mistake because the most recent opener must be closed first.

Where queues show up

Anything that should be handled fairly, in arrival order is a queue: print jobs, customers waiting for support, tasks waiting for a worker program to pick them up. The breadth-first search that finds a short path through a maze also uses a queue, so that nearby squares are explored before far-away ones.

Using them in Python

A Python list makes a good stack, because append and pop() both work at the end of the list:

stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack.pop())   # c
print(stack)         # ['a', 'b']

For a queue, Python provides collections.deque (pronounced "deck", short for double-ended queue). It lets you add at one end and remove from the other quickly:

from collections import deque

queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft())  # a
print(queue)            # deque(['b', 'c'])

You could use a list as a queue with pop(0), and it works, but it is slower for long queues. Removing the first item of a list makes Python shift every remaining item one place to the left. I timed 2,000 remove-then-add rounds on this machine: with 10,000 items a list took about 3 milliseconds and a deque about 0.2. With 100,000 items the list took about 36 milliseconds, roughly ten times longer, while the deque stayed at about 0.2. Exact numbers will differ on your computer, but the pattern holds: the list gets slower as it grows, the deque does not.

So what for your code?

When you need to hold things for later, ask one question first: which item should come out next? If the answer is "the newest one", reach for a stack. If it is "the one that has waited longest", use a queue. Picking the right one often removes the need for any clever sorting or searching, because the order you want is built into the structure.

Many languages have these ready to use: JavaScript arrays have push and pop for stacks, and Python offers the two shown above. Next time you press undo or watch a progress bar line up jobs, you will know which of the two is doing the work.