Simple Stack

A simple stack

A stack is a collection that follows the last-in, first-out (LIFO) rule. You can only add an item on top (push) and only remove the item on top (pop), so the item that comes out is always the one that went in most recently. A pile of plates works the same way: you put a plate on top and take a plate from the top, and the plate at the bottom waits until all the others are gone. This page is the smallest possible stack animation. In fact it is the example that the Galles animation framework uses to show how to write a new visualization. It is still a complete, working stack.

What the animation shows

Type a value (up to 4 characters) and press Push. A light-blue square appears at the top left and slides into the row, just right of the previous square. Slot i is drawn at x = 30 + 30i, so the bottom of the stack is on the left and the top is the rightmost square. Pop slides the rightmost square back to the top left and deletes it. Popping an empty stack does nothing. The page does not draw the top index, but it is simply the number of squares. The stack has no size limit, so after about 32 squares the row runs off the right edge of the canvas (on a phone the row wraps to a new line instead).

The idea: an array plus one index

Since items are only added and removed at one end, an array is all we need. Keep the bottom item at index 0 and remember one integer, top, the number of items. That is also the index of the next free slot. Push writes into A[top] and increases top. Pop decreases top and returns A[top]. Nothing is ever shifted. This is exactly what the page's code does with its stackTop variable.

A[0..];  top = 0                 // top = number of items = next free slot

isEmpty():  return top == 0

push(x):
    if top == capacity: grow (or error "stack overflow")
    A[top] = x
    top = top + 1

pop():
    if top == 0: error "stack underflow"
    top = top - 1
    return A[top]

peek():                          // look at the top without removing it
    if top == 0: error "empty"
    return A[top - 1]

A worked example

Try this on the page: push A, B, C, then pop, push D, pop, pop.

operation   slot used   top after   stack (bottom → top)   returns
start                     0         (empty)
push A      A[0], x=30    1         A
push B      A[1], x=60    2         A B
push C      A[2], x=90    3         A B C
pop         A[2]          2         A B                   C
push D      A[2], x=90    3         A B D
pop         A[2]          2         A B                   D
pop         A[1]          1         A                     B

C was pushed last and came out first. D reused slot 2 as soon as C had left it. A, which went in first, is still at the bottom.

Why it is correct

The invariant is: the stack's items, from bottom to top, are A[0], A[1], …, A[top−1], in the order they were pushed. Push writes the new item just above the old top and extends the range by one. Pop shrinks the range by one and returns the item it drops, A[top−1], which is the last item pushed that has not been popped yet. So every pop returns the most recent remaining push, which is LIFO. The value left behind in A[top] after a pop does not matter: it is outside the range, and the next push overwrites it.

Time and space complexity

• push, pop, peek and isEmpty are O(1): one index update and one array access.
• Space is O(n) for n items, plus any unused capacity.
• Growing. A fixed array can overflow. A dynamic array doubles its capacity when full and copies the items over. That push costs O(n), but it happens only after n/2 cheap pushes. Over n pushes the total copying is 1 + 2 + 4 + … < 2n, so push is O(1) amortized. Growing by a constant amount instead (say +10 each time) makes the total O(n²). JavaScript engines grow arrays like the one this page uses geometrically behind the scenes (by a constant factor, not always exactly 2), which gives the same amortized bound.

Common mistakes, edge cases and variants

• Underflow: popping or peeking an empty stack. Always check top == 0 first. This page simply ignores Pop on an empty stack.
• Overflow: pushing into a full fixed-size array. Grow the array or report an error. A too-deep recursion is a "stack overflow" of the program's own call stack.
• Off-by-one on top: decide whether top is the number of items (as here) or the index of the top item (starting at −1), and use that meaning everywhere. Mixing the two reads or writes the wrong slot.
• Memory leaks in garbage-collected languages: after popping an object, set A[top] = null so the old reference does not keep it alive.
• Linked-list stack: push and pop at the head of a linked list, also O(1), with no capacity limit but one pointer per item (see Stack (linked list)). The array version with a visible top index is on the Stack (array) page.
• Stack vs queue: a queue removes the oldest item instead of the newest, so it has to work at both ends. See Queue (circular array) and Queue (linked list). A deque allows both. A priority queue removes the item with the best key (see Heap).

Where it is used

• Function calls: every running program has a call stack. Each call pushes a frame with its local variables and return address, and each return pops it. Recursion is a stack in disguise, and any recursive algorithm can be rewritten with an explicit stack (depth-first search, for example).
• Undo: editors push each action and pop it to undo. The visualizations on this site do the same: each action you perform is pushed onto a history, and Undo pops the last one.
• Matching brackets and parsing: scan the text, push every opening bracket, and on every closing bracket pop and check that the two match. For {[()]()}: push {, [, (; ) pops ( (match); ] pops [; push (; ) pops it; } pops {. The stack ends empty, so the brackets are balanced. For ([)]: push (, [; then ) pops [, which is a mismatch, so the brackets are not balanced.
• Evaluating expressions in postfix notation, converting infix to postfix (the shunting-yard algorithm), backtracking searches such as mazes and puzzles, and the browser's "Back" button.

What the page leaves out

Thread-safe stacks, from a lock around push and pop to the lock-free Treiber stack built on compare-and-swap; and the stacks in language libraries (Java's ArrayDeque, Python's list, C++'s std::stack), which grow automatically and check for underflow.

References

Stack (abstract data type)