Stack

How a stack works

Three operations, all touching the top:

• Push — add an item to the top.
• Pop — remove and return the top item.
• Peek — return the top item without removing it.

That's it. No random access. No insertion in the middle. The discipline is what makes the stack useful — every operation is O(1) precisely because there's no choice about where in the structure to act.

Internally, a stack is usually a dynamic array with a top index pointing to the next empty slot, or a singly linked list with the head as the top. Both are O(1) for push and pop; the array version uses less memory and is faster in practice (cache locality), the linked-list version avoids occasional resize spikes.

Array-backed vs linked-list-backed

	Array-backed	Linked-list-backed
Push (amortized)	O(1)	O(1)
Push (worst case)	O(n) on resize	O(1)
Memory per element	Value only	Value + 1 pointer
Cache locality	Excellent	Poor
Memory layout	Contiguous	Scattered
Best for	Almost all real workloads	Real-time / no resize spike

Modern standard libraries default to array-backed: Python's list + append/pop, Java's ArrayDeque, C++'s std::stack (which adapts std::deque by default). Java's older Stack class is array-backed but synchronized and avoided in modern code.

When to use a stack

• Function call tracking. Every language runtime uses a stack. When you call f(), the runtime pushes a frame; when f returns, it pops the frame and resumes the caller.
• Expression parsing and evaluation. Shunting-yard converts infix to postfix; postfix is then evaluated with a single operand stack.
• Backtracking. DFS uses an explicit stack (or implicit via recursion) to remember where to back up to. Maze solvers, sudoku solvers, and constraint satisfaction all push state on entry and pop on backtrack.
• Undo histories. Each user action pushes a state snapshot; undo pops the last one.
• Bracket / tag matching. Any matching-pair problem is a stack problem: parentheses, HTML/XML tags, BBCode, function call/return.

Stack vs queue

	Stack (LIFO)	Queue (FIFO)
Insert location	Top	Rear
Remove location	Top	Front
Order out	Reverse of insert	Same as insert
Used for	DFS, parsing, undo, recursion	BFS, scheduling, message buffers
Real-world analogy	Plate stack, browser back button	Line at a coffee shop, print queue
Implementation	Dynamic array, linked list	Circular buffer, two stacks, deque

Pseudo-code

structure Stack:
    items[] = []

    push(x):
        items.append(x)

    pop():
        if items.length == 0: error("underflow")
        return items.removeLast()

    peek():
        if items.length == 0: error("empty")
        return items[items.length - 1]

    isEmpty():
        return items.length == 0

JavaScript implementation

class Stack {
  constructor() { this.items = []; }
  push(x)    { this.items.push(x); }
  pop()      { if (!this.items.length) throw new Error('underflow'); return this.items.pop(); }
  peek()     { if (!this.items.length) throw new Error('empty');     return this.items[this.items.length - 1]; }
  isEmpty()  { return this.items.length === 0; }
  get size() { return this.items.length; }
}

JavaScript arrays are already amortized-O(1) for push/pop on the end, so for most practical purposes a plain array IS a stack — no wrapper class needed.

Python implementation

class Stack:
    def __init__(self):
        self.items = []
    def push(self, x):       self.items.append(x)
    def pop(self):
        if not self.items: raise IndexError('underflow')
        return self.items.pop()
    def peek(self):
        if not self.items: raise IndexError('empty')
        return self.items[-1]
    def is_empty(self):      return not self.items

For real Python code, just use a list with .append() and .pop() — same O(1) behavior, no wrapper needed. collections.deque works too if you also want to access the bottom.

Famous stack problems

Valid Parentheses

Given a string of brackets, return true if every opener has a matching closer in the right order. The textbook stack problem.

function isValid(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);
    else if (stack.pop() !== pairs[ch]) return false;
  }
  return stack.length === 0;
}

Min Stack — O(1) push, pop, peek, AND get-minimum

The trick: maintain a parallel "min so far" stack alongside the main stack. Every push records the running minimum; pop discards both.

class MinStack {
  constructor() { this.s = []; this.mins = []; }
  push(x) {
    this.s.push(x);
    this.mins.push(this.mins.length ? Math.min(x, this.mins[this.mins.length - 1]) : x);
  }
  pop()    { this.mins.pop(); return this.s.pop(); }
  top()    { return this.s[this.s.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

All four operations are O(1). The auxiliary stack costs O(n) extra space but eliminates the O(n) scan you'd need without it.

Common bugs and edge cases

• Pop on empty stack. Either return null/throw — but be consistent. Mixing the two styles in the same codebase is the source of "undefined is not a function" runtime errors.
• Peek on empty stack. Same — pick a behavior and stick with it.
• Stack overflow from recursion. When converting recursion to iteration with an explicit stack, the explicit stack lives on the heap and can hold millions of frames; the call stack typically holds tens of thousands. For deep recursion, the explicit-stack version is what survives.
• Forgetting to handle the empty case at the end. In valid-parentheses, the stack must be EMPTY at the end — non-empty means there's an unmatched opener. Easy to miss.
• Using a stack when you needed a queue. If your "process work items" loop produces results in the reverse order you expected, you grabbed a stack when you wanted a queue. Classic BFS-vs-DFS bug.