AlgoScope

Stack

structurebeginnerTime O(1)Space O(n)

A pile. You can only add to the top or take from the top, so the last thing in is the first thing out. A stack can even be built from a single queue: enqueue the new item, then rotate the queue until it reaches the front, so the only removal a queue offers, the front, always hands back the newest item.

bottom

An empty stack. Only the TOP is ever touched, by both push and pop.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. pop: which value comes off?

    • 9
    • 5
    • 3

    Answer: 9. 9 was pushed most recently, so it is on top and leaves first (LIFO).

  2. pop: which value comes off?

    • 7
    • 5
    • 3

    Answer: 7. 7 was pushed most recently, so it is on top and leaves first (LIFO).

  3. pop: which value comes off?

    • 3
    • 5

    Answer: 3. 3 was pushed most recently, so it is on top and leaves first (LIFO).

How it runs, step by step

  1. An empty stack. Only the TOP is ever touched, by both push and pop.

    Empty stack with capacity 6. Running 8 operations: push 5, push 3, push 9, pop, peek, push 7, pop, pop.

  2. push 5 and it lands on top. Size 1.

    Push 5. 5 is now the top item; the stack has 1 item.

  3. push 3 and it lands on top. Size 2.

    Push 3. 3 is now the top item; the stack has 2 items.

  4. push 9 and it lands on top. Size 3.

    Push 9. 9 is now the top item; the stack has 3 items.

  5. pop returns 9: the most recently pushed item leaves first.

    Pop removes 9, the top item. 2 items remain.

  6. peek shows 3 without removing it.

    Peek shows the top item, 3. Nothing changes.

  7. push 7 and it lands on top. Size 3.

    Push 7. 7 is now the top item; the stack has 3 items.

  8. pop returns 7: the most recently pushed item leaves first.

    Pop removes 7, the top item. 2 items remain.

  9. pop returns 3: the most recently pushed item leaves first.

    Pop removes 3, the top item. 1 item remain.

  10. Done: 4 pushs, 3 pops. 1 item left; top is 5.

    Result: 4 pushes and 3 pops. The stack holds 1 item with 5 on top.

Remember

  • Last in, first out. The most recent push is the next pop.
  • Push, pop and peek are all O(1).
  • Function calls, undo history and bracket matching are stacks; one queue rotated after each push is a stack too, with O(n) push and O(1) pop.

Topics covered

Related

Where this is used

RuntimesThread call stacks

Each thread owns a region of memory and a stack pointer register; a call pushes a frame holding the return address, the arguments and the locals, and the return instruction pops it by moving that one register. LIFO is exactly the right discipline here because a callee always finishes before its caller, so frames die in reverse order of birth and reclaiming one is arithmetic rather than bookkeeping. The region is sized once when the thread is created, which is what the JVM's -Xss flag sets, so runaway recursion trips the overflow check at a known boundary instead of quietly eating the heap.

CompilersStack machines: JVM bytecode and WebAssembly

Neither instruction set names registers for arithmetic: iadd pops two ints and pushes their sum, and Wasm's i32.add does the same. This works because evaluating an expression tree from the bottom up produces operands in exactly LIFO order, so the stack is free scratch space and the compiler emitting bytecode can skip register allocation entirely. It also makes verification cheap, since a validator can walk the instructions tracking only the depth and the types on the stack, which is how a browser rejects malformed Wasm before running any of it.

BrowsersThe HTML parser's stack of open elements

The HTML spec defines a parser structure by exactly that name: a start tag pushes an element, an end tag pops back to it, and any text that arrives becomes a child of whatever is on top. That is what lets the parser build the tree with no lookahead, because the current parent is always one peek away. It is also why every browser mangles mis-nested markup like <b><i></b></i> in the same way: the recovery runs a named algorithm, the adoption agency algorithm, over this stack and a companion list of the formatting elements still in effect, so the result is specified rather than accidental.

Developer toolsgit stash and pushd

git stash keeps saved working trees in LIFO order, so stash@{0} is always the most recent and git stash pop takes that one; the shell's pushd and popd do the same for directories. Both choose a stack because interruptions nest - you drop what you were doing, deal with the newer thing, and want the most recent state back first - which is the same shape as a call stack. It is also why reaching an older entry is the awkward case and has to be named explicitly, as stash@{2}.

Why it works this way

Why top starts at -1

top holds the index of the newest item, and an empty stack has no such index, so it parks one slot below the first one. That is what lets push write with ++top (step up, then store) and pop read with top-- (read, then step down), each a single expression with no branch. The other common convention is a size field that points at the next free slot instead; both work, but mixing them is the classic off-by-one, where peek reads one past the top and hands back whatever an earlier pop left behind.

Building a stack from one queue: something has to pay

The queue hands back its oldest item and the stack must hand back its newest, so the reversal has to happen somewhere and all you choose is where. Rotating after every push, as the code does, puts the whole cost in push. Do it on the way out instead - on each pop, move all but the last item from the front of the same queue round to its back, then remove the front - and the cost flips to O(1) push and O(n) pop. Neither is what you would ship. The point is that two interfaces this opposed can still simulate each other, and that the reversal is never free.

An explicit stack reverses the order you push in

This is the first bug that appears when you rewrite a recursion as a loop with your own stack: pushing a node's children left to right makes the loop visit them right to left, because the last one pushed is the first one popped. Recursive traversal never shows the problem, since each call runs to completion before the next is made. If the visit order matters, push the children in reverse.

A stack that grows still has O(1) push

The fixed array here errors on overflow, while a real stack such as Java's ArrayDeque allocates a larger array and copies. Because the capacity grows by a constant factor rather than creeping up by one - ArrayDeque adds half again once it is past 64 slots - the copying is spread across the many pushes between resizes and the average push stays O(1), but a single unlucky push is O(n), which is why latency-sensitive code sizes the array up front. A linked stack never copies, yet it pays an allocation and a pointer per item and scatters those items across memory, so the array version usually wins anyway.

Read more

Next up