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.

frontbackqueue

A stack built from one queue, drawn front on the left and back on the right. A queue only removes from the front, so the trick is to keep the newest item there: after every push, rotate the queue by moving the front to the back until the new item comes round to the front. Pop is then a plain dequeue.

Check your understanding

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

  1. 3 is at the back of 2 items. How many front-to-back moves bring it to the front?

    • 1
    • 2
    • 3

    Answer: 1. Every item except the new one moves once: size minus one rotations.

  2. 9 is at the back of 3 items. How many front-to-back moves bring it to the front?

    • 2
    • 3
    • 4

    Answer: 2. Every item except the new one moves once: size minus one rotations.

  3. pop: which value comes off?

    • 9, the front
    • 5, the back
    • 3, second from the front

    Answer: 9, the front. The rotations keep the newest item at the front, so pop is a plain dequeue.

  4. 7 is at the back of 3 items. How many front-to-back moves bring it to the front?

    • 2
    • 3
    • 4

    Answer: 2. Every item except the new one moves once: size minus one rotations.

  5. peek: which value is the top of the stack?

    • 7, the front
    • 5, the back
    • 3, second from the front

    Answer: 7, the front. The rotations keep the newest item at the front, so the front is the top.

  6. pop: which value comes off?

    • 7, the front
    • 5, the back
    • 3, second from the front

    Answer: 7, the front. The rotations keep the newest item at the front, so pop is a plain dequeue.

  7. pop: which value comes off?

    • 3, the front
    • 5, the back

    Answer: 3, the front. The rotations keep the newest item at the front, so pop is a plain dequeue.

How it runs, step by step

  1. A stack built from one queue, drawn front on the left and back on the right. A queue only removes from the front, so the trick is to keep the newest item there: after every push, rotate the queue by moving the front to the back until the new item comes round to the front. Pop is then a plain dequeue.

    Stack from one queue, empty.

  2. push 5: enqueue it, which puts it at the back. A stack needs it at the front, where the next pop happens.

    Enqueued 5 at the back.

  3. push 3: enqueue it, which puts it at the back. A stack needs it at the front, where the next pop happens.

    Enqueued 3 at the back.

  4. 3 is behind 1 older item. Each rotation dequeues the front and enqueues it at the back, so after 1 rotations every older item has gone round once and 3 is at the front.

    1 rotations needed.

  5. Rotation 1 of 1: 5 leaves the front and joins the back. 3 is now at the front.

    5 moved to the back.

  6. push 9: enqueue it, which puts it at the back. A stack needs it at the front, where the next pop happens.

    Enqueued 9 at the back.

  7. 9 is behind 2 older items. Each rotation dequeues the front and enqueues it at the back, so after 2 rotations every older item has gone round once and 9 is at the front.

    2 rotations needed.

  8. Rotation 1 of 2: 3 leaves the front and joins the back.

    3 moved to the back.

  9. Rotation 2 of 2: 5 leaves the front and joins the back. 9 is now at the front.

    5 moved to the back.

  10. pop: dequeue the front, 9, which is the most recent push. The remaining items are already in stack order, so nothing rotates.

    Popped 9.

  11. push 7: enqueue it, which puts it at the back. A stack needs it at the front, where the next pop happens.

    Enqueued 7 at the back.

  12. 7 is behind 2 older items. Each rotation dequeues the front and enqueues it at the back, so after 2 rotations every older item has gone round once and 7 is at the front.

    2 rotations needed.

  13. Rotation 1 of 2: 3 leaves the front and joins the back.

    3 moved to the back.

  14. Rotation 2 of 2: 5 leaves the front and joins the back. 7 is now at the front.

    5 moved to the back.

  15. peek: the front of the queue is 7, the most recent push. Nothing moves.

    Top is 7.

  16. pop: dequeue the front, 7, which is the most recent push. The remaining items are already in stack order, so nothing rotates.

    Popped 7.

  17. pop: dequeue the front, 3, which is the most recent push. The remaining items are already in stack order, so nothing rotates.

    Popped 3.

  18. 4 pushes cost 5 rotations in total, 3 pops cost one dequeue each. That is the trade: push is O(n), pop and peek O(1). The mirror-image design, rotate on pop instead of push, gives O(1) push and O(n) pop. Either way one queue is enough; the queue-from-two-stacks trick needs two because a stack cannot be rotated.

    4 pushes, 5 rotations, 3 pops.

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