Stack Visualizer

How it works

1. Store the elements in an array A with a fixed capacity and keep top, the index of the newest element. top = -1 means the stack is empty.
2. push(x): if top == capacity - 1 the stack is full (overflow). Otherwise increment top and write A[top] = x.
3. pop(): if top == -1 the stack is empty (underflow). Otherwise read x = A[top], decrement top and return x.
4. peek(): return A[top] without changing top.
5. isEmpty() is top == -1, isFull() is top == capacity - 1, and the size is top + 1.

Worked example: push 5, push 9, pop, push 2

Start with an empty stack of capacity 5 (top = -1):

• push(5): top becomes 0 and A[0] = 5. Stack: [5].
• push(9): top becomes 1 and A[1] = 9. Stack: [5, 9].
• pop(): reads A[1] = 9, top drops to 0, and 9 is returned. Stack: [5].
• push(2): top becomes 1 again and A[1] = 2 overwrites the old 9. Stack: [5, 2].

Notice that pop never erased the 9 — it only moved top. The old value stayed in the array as garbage until the next push overwrote it. That is why pop, and even clear() (just top = -1), are O(1): no element other than the top is touched. In a garbage-collected language that stores object references, set the freed slot to None or null so the object can be reclaimed — still O(1) per pop, though a clear() that releases every reference must null each slot and becomes O(n).

Overflow, underflow and growable stacks

A fixed-size array stack can fail in two ways. Overflow is pushing onto a full stack — there is no A[capacity]. Underflow is popping or peeking an empty stack — there is no A[-1]. Check isFull() and isEmpty() first, or raise an error as the code below does.

Most real stacks avoid overflow by growing: when the array fills up, allocate a larger one (typically twice the size) and copy the elements across. A single resize costs O(n), but growing by a constant factor makes resizes so rare that push is amortized O(1). Python's list, Java's ArrayDeque and C++'s std::vector all grow this way.

The famous *stack overflow* error is the same idea applied to the call stack: every function call pushes a frame, and infinite or very deep recursion runs out of the memory reserved for it.

Array stack vs linked-list stack

• Array: elements sit next to each other in memory, so it is cache-friendly and has no per-element pointer overhead. A growable array pays for an occasional O(n) resize.
• Linked list: push and pop at the head are O(1) in the worst case and it never needs resizing, but every node carries a pointer and lives somewhere else in memory.

Both give exactly the same LIFO behaviour. In practice array-backed stacks are usually faster; a linked list is the natural choice when you are already working with nodes.

Where stacks are used

• Function calls: the call stack stores return addresses and local variables, which is why recursion unwinds in reverse order.
• Undo and redo in editors, and the back button in a browser.
• Parsing: matching brackets, converting infix expressions to postfix and evaluating them.
• Depth-first search and backtracking — mazes, Sudoku, permutations — where an explicit stack replaces recursion.
• Monotonic stacks for next greater element, stock span and the largest rectangle in a histogram.

Common mistakes

• Popping or peeking without checking that the stack is non-empty.
• Mixing up pop (removes the top) and peek (only reads it).
• Off-by-one errors between the top index and the size: the size is top + 1.
• Using list.pop(0) or list.insert(0, x) in Python — that works on the bottom of the list and costs O(n). A stack uses the end.
• In Java, reaching for the legacy Stack class (synchronized, extends Vector) instead of ArrayDeque.

Interview questions on stacks

• Valid parentheses: push openers, match each closer against the top.
• Min stack: keep a second stack of running minimums so getMin() is O(1).
• Queue using two stacks: amortized O(1) per operation.
• Evaluate reverse Polish notation, daily temperatures, decode string and largest rectangle in histogram are all one-stack solutions.

The visualizer above lets you rehearse the basics: fill the stack to overflow, pop it to underflow, and use *Quiz me* to predict what the next pop returns.

Time and space complexity

Stack in Python

class Stack:
    """Array-backed stack with a fixed capacity (LIFO)."""

    def __init__(self, capacity):
        self.A = [None] * capacity
        self.capacity = capacity
        self.top = -1  # index of the top; -1 = empty

    def push(self, x):
        if self.top == self.capacity - 1:
            raise IndexError("Stack Overflow")
        self.top = self.top + 1
        self.A[self.top] = x

    def pop(self):
        if self.top == -1:
            raise IndexError("Stack Underflow")
        x = self.A[self.top]
        self.top = self.top - 1  # A[top + 1] stays behind as garbage
        return x

    def peek(self):
        if self.top == -1:
            raise IndexError("Stack is empty")
        return self.A[self.top]  # top unchanged

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == self.capacity - 1

    def clear(self):
        self.top = -1  # O(1): the old values are now garbage


# s = Stack(5); s.push(5); s.push(9); s.pop()  -> 9

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Stack & Queue VisualizerStack and queue visualizer: animate push, pop, enqueue and dequeue, compare LIFO with FIFO, and step through circular queues, deques and stack applications.
• Queue VisualizerInteractive queue visualizer: watch enqueue and dequeue move the front and rear of an array queue, and see the wasted-space problem that circular queues fix.
• Balanced Parentheses CheckerCheck if parentheses are balanced and watch the stack algorithm step by step: push each opener, match each closer, catch crossed or unclosed brackets in O(n).
• Infix to Postfix ConverterConvert infix to postfix step by step with the shunting-yard algorithm: see the operator stack, precedence and associativity, and the output after every token.
• Next Greater Element VisualizerFind the next greater element of every array value with a monotonic stack in O(n). Watch each index wait on the stack until a larger value resolves it.
• Linked List VisualizerInteractive linked list visualizer: watch every pointer change as you insert, delete, search and reverse singly, doubly and circular lists, with code and costs.