Stack

What is it?

Some problems naturally need to process things in reverse order of how they arrived — undo history, nested function calls, matching brackets. A stack is a structure built exactly for that: you can only add ("push") or remove ("pop") from one end, called the top, and whatever was added most recently is always the first thing to come back out.

This rule is called LIFO — Last In, First Out.

Explain like I'm 10

A stack is like a stack of plates. You add a new plate on top, and when you need one, you take the top plate off first — you'd never pull one from the bottom without disturbing everything above it.

Examples

Using an array as a stack

const stack = [];

stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]

console.log(stack.pop()); // 3 — removes and returns the top item
console.log(stack);       // [1, 2]

push and pop both operate on the end of the array, which is exactly how a stack behaves — no special data structure is required in JavaScript.

How it works

A stack only exposes two main operations: push (add to the top) and pop (remove from the top) — both O(1), since neither requires touching any other item. There's no direct way to access an item in the middle without first removing everything above it.

push(1)   push(2)   push(3)     pop()
   ↓         ↓         ↓          ↓
  [1]      [1,2]    [1,2,3]    returns 3, leaves [1,2]

Why does it exist?

Many real problems are naturally last-in-first-out: undo/redo history, tracking function calls (the call stack!), and checking that brackets or parentheses are balanced. A stack models that behavior directly and simply.

When to use it

Reach for a stack whenever the most recent thing needs to come out first — undo history, matching brackets or parentheses, or tracking a path while backtracking through a maze or a tree.

When not to use it

If you need to process items in the order they arrived (not the reverse), you want a queue, not a stack. And if you need to inspect or remove an item from the middle regularly, a stack's "only touch the top" rule will fight you.

Common mistakes

• Trying to access the middle of a stack directly instead of popping down to it.

• Popping from an empty stack without checking first, causing errors or undefined.

• Confusing a stack (LIFO) with a queue (FIFO) — they solve different problems.

Practice exercises

1. Easy:

   Implement a Stack class with push, pop, and peek (view the top without removing it) methods.

2. Medium:

   Use a stack to check whether a string of parentheses like "(()())" is balanced.

3. Hard:

   Use a stack to reverse the words in a sentence without using built-in reverse methods.

Interview questions

What does LIFO mean?

Last In, First Out — the most recently added item is always the first one removed.

What is a real-world use of a stack in programming?

The call stack itself, which tracks function calls; also undo/redo features, balanced-bracket checking, and browser back/forward-style history.

What's the time complexity of push and pop?

Both are O(1) — they only ever touch the top item, with no need to shift or scan anything else.

Compare an array-based stack to a linked-list-based one — what are the real tradeoffs?

An array-based stack stores elements contiguously, giving better cache locality, but a dynamic array occasionally needs to resize (an O(n) copy) as it grows. A linked-list-based stack gives a guaranteed O(1) per operation with no resizing, but pays extra memory for a pointer per node and has worse cache locality since nodes may be scattered across memory.

What does 'amortized O(1)' mean for pushing onto a dynamic array-based stack, given that resizing is O(n)?

When the backing array fills up, it's typically resized by doubling its capacity, which costs O(n) to copy existing elements. But doubling means that expensive resize happens exponentially less often as the stack grows — the total cost of all resizes across n pushes works out to O(n), which spreads to O(1) per push on average, even though any single resizing push briefly costs O(n).

What happens if you try to push onto a fixed-capacity array-based stack that's already full?

In a truly fixed-size implementation, it overflows — typically by throwing an error or refusing the push. A dynamic implementation instead detects the full condition and triggers a resize to a larger backing array before completing the push.

Is a call stack overflow the same kind of thing as overflowing a fixed-size custom stack?

Conceptually yes — both mean exceeding the stack's available capacity. The call stack's limit comes from the fixed amount of memory the OS/engine reserves for stack frames (exceeded by recursing too deeply); a custom stack's limit is whatever capacity its backing storage was given.

How would you design a stack that supports `push`, `pop`, and `getMin()` (current minimum) all in O(1)?

Maintain a second, auxiliary stack alongside the main one that tracks the minimum at each point. On every push, also push the smaller of (new value, current auxiliary top) onto the auxiliary stack. On every pop, pop from both stacks together. getMin() just peeks the auxiliary stack's top — no scanning needed.

Trace a min-stack: push 5, push 3, push 7, push 3, pop, pop. What does `getMin()` return after each step?

push 5: main [5], min-stack [5], min=5. push 3: main [5,3], min-stack [5,3], min=3. push 7: main [5,3,7], min-stack [5,3,3] (7 isn't smaller than 3, so 3 repeats), min=3. push 3: main [5,3,7,3], min-stack [5,3,3,3], min=3. pop: removes 3 from both, main [5,3,7], min-stack [5,3,3], min=3. pop: removes 7 from both, main [5,3], min-stack [5,3], min=3. The repeated 3 in the min-stack is exactly what preserves the correct minimum after the top 3 was popped.

How would you evaluate the postfix expression `"3 4 + 2 *"` using a stack?

Scan left to right: push 3, push 4. On seeing +, pop two values (4, then 3), compute 3 + 4 = 7, push 7. On seeing 2, push 2. On seeing *, pop two values (2, then 7), compute 7 * 2 = 14, push 14. At the end, the stack holds only the result, 14.

Why does evaluating postfix notation require a stack instead of computing left to right immediately?

An operator can combine two operands that were themselves the results of earlier computations, not just the raw numbers seen so far. The stack holds every intermediate result until an operator arrives that needs it, so results computed several steps earlier remain available exactly when needed.

How would you check whether a string like `"{[()]}"` has properly balanced brackets, using a stack?

Scan the string; on an opening bracket, push it. On a closing bracket, pop the stack and check that it matches the corresponding opening bracket — if it doesn't match (or the stack is empty), the string is unbalanced. At the end, the string is balanced only if the stack is empty.

Why does checking `"([)]"` for balance require tracking order with a stack, rather than just counting each bracket type?

The counts of (, ), [, and ] all match in "([)]", but the nesting is invalid — the ) closes before the [ that opened after it has been closed. Only an order-sensitive structure like a stack catches this: when ) arrives, the stack's top is [, which doesn't match, correctly flagging it as unbalanced.

How would you implement a queue using two stacks?

Keep an 'in' stack for enqueuing (just push) and an 'out' stack for dequeuing. To dequeue, if the 'out' stack is empty, pop everything off 'in' and push it onto 'out' — this reverses the order so the oldest enqueued item ends up on top of 'out' — then pop from 'out'. If 'out' isn't empty, just pop from it directly.

What's the amortized time complexity of dequeue in the two-stack queue, even though one dequeue can move every element between stacks?

Amortized O(1). Each element is pushed onto 'in' once and moved to 'out' at most once over its entire lifetime in the queue — so across any sequence of n operations, the total number of moves is bounded by roughly 2n, which averages out to O(1) work per operation even though a single dequeue can occasionally cost O(n).

What is the 'next greater element' problem, and how does a stack solve it in O(n) instead of O(n²)?

For each element, find the first element to its right that's larger. The naive approach checks every pair, O(n²). A stack-based approach scans left to right, maintaining a stack of indices whose 'next greater' hasn't been found yet; whenever the current value is bigger than the stack's top, that top index's answer is the current value, so it's popped and resolved. Each index is pushed and popped at most once, making the total work O(n).

How would you reverse a string (or a list's order) using a stack, and what's the space cost?

Push every character (or item) onto a stack, then pop them all off — since a stack reverses insertion order, popping everything back out yields the reverse. This costs O(n) extra space, since every element must be held on the stack simultaneously before any of them come back off.

Why should code check whether a stack is empty before calling `pop()` or `peek()`?

Popping or peeking an empty stack is undefined behavior in the sense that it has no top item to return — depending on the implementation, it may throw, return undefined, or (in a fixed-size array with an index counter) underflow the counter into an invalid state. Checking emptiness first avoids all of these failure modes.

How is the call stack itself an instance of the abstract stack data structure?

Each function call pushes a new stack frame holding that call's local variables, parameters, and a return address. When the function returns, its frame is popped and execution resumes in the caller at the saved return address — exactly LIFO behavior, since the most recently called (and not-yet-returned) function is always the next one to finish.

How would you convert a recursive function into an iterative one using an explicit stack, and why does this always work?

Maintain your own stack of 'pending work' (e.g. the arguments or state each recursive call would have used), and loop: pop a unit of work, process it, and push any further work it generates instead of recursing into it. This works in principle because recursion is itself implemented via the call stack — manually managing an equivalent stack lets you simulate the same call-and-return behavior without relying on the language's own call stack.

How does a browser's back/forward navigation map onto stack operations?

Visiting a new page pushes it onto a 'back' stack (and typically clears the 'forward' stack, since that history branch is no longer valid). Clicking back pops the current page off 'back' and pushes it onto 'forward'. Clicking forward does the reverse — pop from 'forward', push onto 'back'.

Why is peeking at a stack's top O(1), but checking whether a value exists anywhere in the stack O(n)?

Peek only ever reads the top element, a fixed single access regardless of size. Searching for an arbitrary value has no shortcut — since only the top is directly reachable, determining whether a value exists elsewhere requires inspecting (or popping) down through potentially every element.

What's the difference between a stack overflow and a stack underflow?

Overflow means exceeding capacity — pushing past a fixed-size stack's limit, or in the call stack, recursing so deeply that available stack memory runs out. Underflow means the opposite: attempting to pop or peek an already-empty stack, where there's nothing left to remove.

Scenario: you're building undo/redo. Why use two separate stacks instead of one?

Undoing an action needs to pop it off an undo stack, but that action must then be available to redo later — which means pushing it onto a separate redo stack. A single stack can't simultaneously represent 'actions waiting to be undone' and 'actions that were undone and could be reapplied' as two distinct, independently poppable sequences.

How would you sort a stack into ascending order using only one additional stack?

Repeatedly pop from the original stack; for each popped element, pop elements off the auxiliary (sorted) stack back onto the original stack until the auxiliary stack's top is not greater than the current element, then push the current element onto the auxiliary stack. Repeating until the original stack is empty leaves the auxiliary stack sorted, though at O(n²) time since each insertion can require re-shuffling much of the auxiliary stack.

Why is a stack the natural structure for validating that HTML/XML tags are properly nested and closed?

Each opening tag is pushed onto the stack. Each closing tag must match the most recently opened, still-unclosed tag — exactly the stack's top — so popping and comparing on every closing tag directly checks proper nesting, the same way bracket matching does.