Stack visualization

A stack is a collection that adds and removes elements at one end only, called the top. The element added last is the first one removed, which is why it is called last in, first out (LIFO). Think of a pile of plates: you put a plate on top and you take a plate from the top.

How it works

A stack has three operations. The code here keeps the elements in an array and treats the end of the array as the top.

1. push(x) puts x on top.
2. pop() removes the top element and returns it.
3. peek() returns the top element and leaves it in place.

Each operation reads or writes only the last slot. No other element is looked at or moved.

Time and space complexity

• Time, O(1) for push, pop and peek: each one touches one slot and changes one number, the length. The work does not depend on how many elements the stack holds.
• Space, O(n): the stack stores its n elements. Each operation needs only a constant amount of extra memory.

A worked example

Push 4, 8, 1, 6 and 3 in that order, with one pop after every second push, as the lesson's run does. Then peek, pop everything that is left, and pop once more on the empty stack. The table shows the stack from bottom to top after each operation.

The values went in as 4, 8, 1, 6, 3 and came out as 8, 6, 3, 1, 4. Each pop returned the newest push that was still on the stack, and peek changed nothing. The last pop is an underflow: it returns undefined and the stack stays empty. The run counts 10 writes (five pushes and five removals) and 6 comparisons, one emptiness check for each of the six pops.

Pseudocode

This is the lesson's code in textbook form. S.length is the number of elements, the top is index S.length - 1, and NIL stands for the undefined that the code returns.

PUSH(S, x)
    S[S.length] = x

POP(S)
    if S.length == 0
        return NIL            // underflow
    x = S[S.length - 1]
    S.length = S.length - 1
    return x

PEEK(S)
    if S.length == 0
        return NIL
    return S[S.length - 1]

Every line is a constant number of operations, with no loop, which is why all three operations are O(1).

When to use it, and when not to

Use a stack whenever the most recent item must be dealt with first:

• Undo: the last action you made is the first one undone.
• The call stack: a function that is called last returns first.
• Matching brackets and evaluating expressions: an opening bracket waits until its closing one arrives.
• Backtracking and depth-first search: follow a path, and step back to the most recent choice when it ends.

Do not use it when the oldest item must go first. That is a queue. A stack also cannot find a value without removing the elements above it.

Where it is used

• The call stack. Each function call pushes a frame with its parameters, local variables and the place to return to. A return pops the frame. The newest call always finishes first, so nested and recursive calls unwind in the right order. A recursion that never stops fills the fixed memory set aside for this stack, which is a stack overflow.
• Undo and redo. An editor pushes every change onto an undo stack. Undo pops the newest change and pushes it onto a redo stack, and redo moves it back. Two stacks give both directions at O(1) per action.
• Evaluating expressions. To evaluate the postfix expression 3 4 + 2 *, push each number. When an operator arrives, pop two numbers, apply it and push the result: the stack holds 3, 4, then 7, then 7, 2, then 14. Parsers match brackets the same way, pushing at ( and popping at ).

Common mistake and edge cases

Variations and related ideas

A deque (double-ended queue) allows adding and removing at both ends, so it can act as a stack or as a queue. A stack can also be built on a linked list: push and pop then change only the head, and there is no array to outgrow. If the oldest item must come out first, use a queue. Depth-first search keeps its path on a stack, either the call stack through recursion or one it manages itself.