# Stacks

> LIFO — last in, first out. Push to top, pop from top. O(1) for everything.

- **Category**: Data Structures
- **Subcategory**: LIFO
- **Canonical URL**: https://designpattern.fyi/patterns/stacks/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
Balanced brackets validator — push opening brackets, pop and match on closing brackets. Call stack — every function call pushes a frame, return pops it. Browser history — navigate pushes URLs, back button pops. DFS graph traversal — push neighbors, pop to visit.



## Implementation Example

```javascript
// ─── Stack backed by a JS array ──────────────────────────────
class Stack {
  #items = [];

  push(value) { this.#items.push(value); }     // O(1) amortized
  pop()       { return this.#items.pop(); }     // O(1)
  peek()      { return this.#items.at(-1); }    // O(1) — read top without removing
  isEmpty()   { return this.#items.length === 0; }
  get size()  { return this.#items.length; }
}

// ─── Classic use case: Balanced brackets ─────────────────────
function isBalanced(str) {
  const stack = new Stack();
  const pairs = { ')': '(', ']': '[', '}': '{' };
  for (const ch of str) {
    if ('([{'.includes(ch)) {
      stack.push(ch);            // Push opening bracket
    } else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false; // Mismatch
    }
  }
  return stack.isEmpty();        // Valid only if nothing left unmatched
}

// ─── Min Stack — O(1) getMin at all times ────────────────────
class MinStack {
  #stack = [];
  #minStack = []; // Parallel stack tracking minimums

  push(val) {
    this.#stack.push(val);
    const currentMin = this.#minStack.at(-1) ?? Infinity;
    this.#minStack.push(Math.min(val, currentMin)); // Track running min
  }
  pop() {
    this.#minStack.pop();
    return this.#stack.pop();
  }
  peek()   { return this.#stack.at(-1); }
  getMin() { return this.#minStack.at(-1); } // O(1) — no scan needed
}

// ─── Iterative DFS using explicit stack (avoids call stack overflow) ─
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = new Stack();
  stack.push(start);
  while (!stack.isEmpty()) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    for (const neighbor of graph[node] ?? []) stack.push(neighbor);
  }
  return visited;
}

```



## Trade-offs


### Advantages

- O(1) push, pop, and peek — all operations constant time

- Simple mental model — only one access point, impossible to accidentally touch wrong elements

- Naturally models recursive algorithms iteratively (DFS, expression parsing)

- No wasted capacity if backed by a linked list; minimal waste with a dynamic array




### Considerations & Drawbacks

- No random access — you can only see the top element without popping

- Unbounded stack growth can cause stack overflow (call stacks have OS-imposed limits)

- Not the right structure for any operation that needs middle-element access

- Array-backed stacks have the same resize spike as dynamic arrays







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)