All Roadmaps›🧠 Data Structures & Algorithms›Phase 2›Stacks — Implementation & Applications

Stacks — Implementation & Applications

0/14 in this phase0/57 across the roadmap

📖 Concept

A stack is a LIFO (Last In, First Out) data structure. Think of a stack of plates — you add and remove from the top only.

Operations — ALL O(1):

  • push(item) — Add to top
  • pop() — Remove and return top
  • peek()/top() — View top without removing
  • isEmpty() — Check if stack is empty

Where stacks appear in the real world:

  • Call stack — function execution tracking
  • Undo/Redo — text editors, Ctrl+Z
  • Browser back button — history of visited pages
  • Expression evaluation — parentheses matching, postfix notation
  • DFS traversal — iterative DFS uses an explicit stack

Classic interview patterns using stacks:

  1. Valid parentheses — push opening, pop on closing, check match
  2. Next greater element — monotonic stack
  3. Min stack — O(1) getMin using auxiliary stack
  4. Evaluate postfix expression — push numbers, pop on operators
  5. Daily temperatures — monotonic decreasing stack

🏠 Real-world analogy: A Pringles can — you can only access the chip on top. To get to the bottom chip, you must remove all above it.

💻 Code Example

codeTap to expand ⛶
1// STACK — Array-based implementation
2class Stack {
3  constructor() {
4    this.items = [];
5  }
6  push(item) { this.items.push(item); }
7  pop() { return this.items.pop(); }
8  peek() { return this.items[this.items.length - 1]; }
9  isEmpty() { return this.items.length === 0; }
10  size() { return this.items.length; }
11}
12

13// VALID PARENTHESES — Classic stack problem
14function isValid(s: string): boolean {
15  const stack: string[] = [];
16  const map: Record<string, string> = { ')': '(', '}': '{', ']': '[' };
17

18  for (const char of s) {
19    if ('({['.includes(char)) {
20      stack.push(char);
21    } else {
22      if (stack.pop() !== map[char]) return false;
23    }
24  }
25  return stack.length === 0;
26}
27

28// MIN STACK — O(1) push, pop, getMin
29class MinStack {
30  private stack: number[] = [];
31  private minStack: number[] = [];
32

33  push(val: number): void {
34    this.stack.push(val);
35    const min = this.minStack.length === 0
36      ? val
37      : Math.min(val, this.minStack[this.minStack.length - 1]);
38    this.minStack.push(min);
39  }
40

41  pop(): void {
42    this.stack.pop();
43    this.minStack.pop();
44  }
45

46  top(): number { return this.stack[this.stack.length - 1]; }
47  getMin(): number { return this.minStack[this.minStack.length - 1]; }
48}
49

50// NEXT GREATER ELEMENT — Monotonic stack
51function nextGreater(arr: number[]): number[] {
52  const result = new Array(arr.length).fill(-1);
53  const stack: number[] = []; // Stack of indices
54

55  for (let i = 0; i < arr.length; i++) {
56    while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
57      result[stack.pop()!] = arr[i];
58    }
59    stack.push(i);
60  }
61  return result;
62}
63// [4,5,2,10,8] → [5,10,10,-1,-1]
64

65// EVALUATE POSTFIX — "3 4 + 2 *" = (3+4)*2 = 14
66function evalPostfix(tokens: string[]): number {
67  const stack: number[] = [];
68  for (const token of tokens) {
69    if ('+-*/'.includes(token)) {
70      const b = stack.pop()!, a = stack.pop()!;
71      if (token === '+') stack.push(a + b);
72      if (token === '-') stack.push(a - b);
73      if (token === '*') stack.push(a * b);
74      if (token === '/') stack.push(Math.trunc(a / b));
75    } else {
76      stack.push(Number(token));
77    }
78  }
79  return stack[0];
80}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Implement a stack using an array (push, pop, peek, isEmpty)
  2. Check if parentheses are balanced: "({[]})" → true, "({)}" → false
  3. Reverse a string using a stack
  4. Implement a Min Stack with O(1) getMin
  5. Evaluate a postfix expression
  6. Convert infix to postfix expression
  7. Next greater element for each element in an array
  8. Daily temperatures: for each day, how many days until warmer?
  9. Implement a stack using two queues
  10. Largest rectangle in histogram (monotonic stack)

⚠️ Common Mistakes

  • Using shift/unshift for stack operations — stack should use push/pop (end of array) for O(1)

  • Not checking isEmpty before pop/peek — causes undefined errors

  • Forgetting to check stack is empty after processing — leftover elements mean invalid input

  • Using a stack when a simple variable/counter would suffice (e.g., just counting parentheses depth)

  • Not recognizing monotonic stack patterns — these are very common in interviews

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Stacks — Implementation & Applications

← PreviousDoubly Linked Lists & Circular ListsNext →Queues, Deques & Circular Queues