Stacks

What is a stack?

A stack is a collection where you can only add or remove at one end, called the top. The last item you put in is the first one you take out: LIFO, last in, first out.

Think of a stack of plates in a canteen. You put clean plates on top, and you take a plate from the top. You never pull one from the middle.

A stack has just a few operations:

• push(x): put x on top.
• pop(): remove and return the top item.
• peek(): look at the top item without removing it.
• is_empty() / size(): check how many items there are.

Every one of them is O(1).

How it works

The easiest way to build a stack is on top of a dynamic array, with the end of the array as the top. Pushing appends to the end and popping removes from the end, and both are O(1) because nothing needs to shift. (Using the front of the array as the top would make every push and pop O(n).)

Operations and their cost

Building one yourself

The class below wraps a dynamic array. Popping or peeking at an empty stack is an error, so it raises one with a clear message instead of failing somewhere later. The program then uses the stack twice: to check brackets, and to implement undo by pushing the text before each change and popping to go back.

class Stack:
    def __init__(self):
        self.items = []  # the top of the stack is the end of the list

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.items:
            raise IndexError("pop from empty stack")
        return self.items.pop()

    def peek(self):
        if not self.items:
            raise IndexError("peek at empty stack")
        return self.items[-1]

    def is_empty(self):
        return not self.items

    def __len__(self):
        return len(self.items)


def yes_no(flag):
    return "true" if flag else "false"


def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = Stack()
    for ch in text:
        if ch in "([{":
            stack.push(ch)
        elif ch in pairs:
            if stack.is_empty() or stack.pop() != pairs[ch]:
                return False
    return stack.is_empty()


s = Stack()
for n in (1, 2, 3):
    s.push(n)
print("after push 1, 2, 3 (bottom to top):", s.items)
print("peek:", s.peek())
print("pop:", s.pop())
print("pop:", s.pop())
print(f"size: {len(s)}, empty: {yes_no(s.is_empty())}")
print("pop:", s.pop())
print("empty:", yes_no(s.is_empty()))
try:
    s.pop()
except IndexError as e:
    print("error:", e)

for text in ("{[()]}", "([)]", "(("):
    print(f'balanced("{text}"): {yes_no(balanced(text))}')

history, text = Stack(), ""
for word in ("Hello", " world", "!"):
    history.push(text)  # remember the state before each change
    text += word
print("typed:", text)
text = history.pop()
print("undo:", text)
text = history.pop()
print("undo:", text)

after push 1, 2, 3 (bottom to top): [1, 2, 3]
peek: 3
pop: 3
pop: 2
size: 1, empty: false
pop: 1
empty: true
error: pop from empty stack
balanced("{[()]}"): true
balanced("([)]"): false
balanced("(("): false
typed: Hello world!
undo: Hello world
undo: Hello

Stacks in the standard libraries

In Java, prefer ArrayDeque over the old java.util.Stack class, which is synchronised and slower. In C++, pop() returns nothing, so read top() first.

Where stacks appear

• The call stack. Every function call pushes a frame holding its local variables; returning pops it. That is why deep recursion can cause a stack overflow.
• Undo and redo in editors: one stack for undo, one for redo.
• Matching brackets, HTML tags, and parsing expressions.
• Evaluating expressions in postfix (reverse Polish) notation. Try Evaluate Reverse Polish Notation in the lab.
• Depth-first search, which uses a stack (or recursion) to remember where to go back to.
• Monotonic stacks, which answer "next greater element" questions in O(n). Try Next Greater Element in the lab.

Common mistakes

• Popping an empty stack. Check is_empty() first, or handle the error. In C++, calling top() on an empty std::stack is undefined behaviour.
• Forgetting the final check. In bracket matching, "((" never fails a match during the loop; it fails because the stack is not empty at the end.
• Using the front of an array as the top, which makes push and pop O(n).

When to use a stack

Use a stack whenever the most recent thing is the first thing you need again: going back, undoing, matching nested pairs, or exploring a path and backtracking. If you need the oldest item first instead, you want a queue.