Stacks & Queues

What you'll learn

• Part 1: The Stack

• LIFO Principle

  A stack follows Last-In, First-Out (LIFO). The most recently added element is the first one removed -- like a stack of plates.

• Stack Operations

  | Operation | Description | Time | |-----------|------------|------| | push(x) | Add element to top | O(1) | | pop() | Remove and return top element | O(1) | | peek() / top() | View top element without removing | O(1) | | isEmpty() | Che…

• Array-Based Implementation

  Pros: Cache-friendly, no pointer overhead, random access possible. Cons: Fixed size (unless using dynamic array with occasional O(n) resize).

• Linked-List-Based Implementation

  Pros: No size limit, no wasted space, always O(1) push/pop. Cons: Extra memory per node (pointer), not cache-friendly. ---

• Part 2: Stack Patterns for Interviews

• Pattern 1: Balanced Parentheses

  Problem: Given a string containing ()[]{}, determine if it is valid. Sample Input / Output Input: "{[()]}" Output: true (balanced) Input: "{[(])}" Output: false (bracket mismatch) Input: "" Output: true — edge case (empty string is balan…

• Pattern 2: Min Stack (O(1) getMin)

  Problem: Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1). Sample Input / Output Input: push(4), push(1), push(5), getMin(), pop(), getMin() Output: 1, 1 (min is 1 after push sequence, still 1…

• Pattern 2b: Min Stack Without Extra Space

  Problem: Same as Min Stack but without using a supporting stack (O(1) extra space). Sample Input / Output Input: push(7), push(5), push(3), getMin(), pop(), getMin() Output: 3, 5 (min is 3, then 5 after popping) Input: push(2), push(2),…

• Pattern 6b: Maximal Rectangle in Binary Matrix

  Problem: Given a binary matrix of 0s and 1s, find the largest rectangle containing only 1s. Sample Input / Output Input: Output: 6 — the 2×3 rectangle of 1s at rows 1..2, columns 2..4. Input: Output: 12 (3 rows × 4 cols, all 1s) Input: O…

• Pattern 7: Rain Water Trapping

  Problem: Given elevation map, compute trapped water. Sample Input / Output Input: heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 — total units of water trapped between the bars. Input: heights = [3, 0, 2, 0, 4] Output: 7 (water…

• Part 3: The Queue

• FIFO Principle

  A queue follows First-In, First-Out (FIFO). The first element added is the first one removed -- like a line at a ticket counter.

• Queue Operations

  | Operation | Description | Time | |-----------|------------|------| | enqueue(x) | Add element to rear | O(1) | | dequeue() | Remove element from front | O(1) | | front() / peek() | View front element | O(1) | | isEmpty() | Check if que…

• Array-Based Queue Problem

  With a naive array implementation, dequeue leaves wasted space at the front: This leads us to the circular queue. ---

• Part 4: Circular Queue

• Why It Exists

  A circular queue solves the wasted-space problem by wrapping around. When the rear reaches the end of the array, it wraps to index 0 (if space is available).

• Implementation Key Points

  - Front pointer: index of first element - Rear pointer: index of next empty slot (or last element, varies by implementation) - Wrap: use modulo arithmetic: rear = (rear + 1) % capacity - Full condition: (rear + 1) % capacity == front (sa…

• Part 5: Deque (Double-Ended Queue)

  A deque (pronounced "deck") allows insertion and removal at both ends in O(1).

• Operations (All O(1))

  | Operation | Description | |-----------|------------| | pushFront(x) | Add to front | | pushBack(x) | Add to rear | | popFront() | Remove from front | | popBack() | Remove from rear | | peekFront() | View front | | peekBack() | View rear |

• When to Use Deque

  - Sliding window maximum (most important interview use) - Palindrome checking - Work-stealing algorithms - Implementing both stack and queue with one structure ---

• Part 6: Priority Queue

  A priority queue dequeues elements by priority rather than insertion order. | Operation | Typical Implementation (Binary Heap) | |-----------|--------------------------------------| | insert(x) | O(log n) | | extractMax() / extractMin()…

• Part 7: Queue-Based Interview Patterns

• Pattern 1: Queue Using Two Stacks

  Sample Input / Output Input: operations enqueue(1), enqueue(2), enqueue(3), dequeue(), enqueue(4), dequeue() Output: dequeue calls emit 1 then 2 (FIFO order preserved using LIFO stacks) Input: operations enqueue(5), dequeue() Output: deq…

• Pattern 2: Stack Using Two Queues

  Sample Input / Output Input: operations push(1), push(2), push(3), pop(), push(4), pop() Output: pop calls emit 3 then 4 (LIFO order preserved using FIFO queues) Input: operations push(7), pop() Output: pop emits 7 (single element) Input…

• Pattern 3: Sliding Window Maximum

  Problem: Given array and window size k, find maximum in each window. Sample Input / Output Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 Output: [3, 3, 5, 5, 6, 7] — one max per window of size 3. Input: nums = [9, 8, 7, 6, 5], k = 2 Ou…

• Part 8: When to Use What

• Use a Stack When:

  - Matching/nesting: parentheses, HTML tags, expression parsing - Reversal: reverse a string, reverse a linked list iteratively - Undo operations: text editors, browser back button - DFS (Depth-First Search): explicit stack or recursion c…

• Use a Queue When:

  - BFS (Breadth-First Search): level-order traversal of trees/graphs - Scheduling: CPU task scheduling, print queue - Buffering: data stream processing, message queues - Order preservation: processing items in arrival order - Rate limitin…

• Use a Deque When:

  - Sliding window: maximum/minimum in a window - Palindrome checking: compare from both ends - Both stack and queue needed: flexible structure ---

• Part 9: Complexity Summary

  | Structure | Push/Enqueue | Pop/Dequeue | Peek | Space | |-----------|:---:|:---:|:---:|:---:| | Stack (array) | O(1) | O(1) | O(1) | O(n) | | Stack (linked list) | O(1) | O(1) | O(1) | O(n) | | Queue (linked list) | O(1) | O(1) | O(1)…

• Part 10: Expression Evaluation with Stacks

  Stacks are the engine behind how compilers and calculators evaluate mathematical expressions.

• Infix to Postfix Conversion

  Complexity: Time O(n), Space O(n). Each token is processed once. Operators are pushed and popped from the stack at most once. The output postfix string requires O(n) space.

• Postfix Evaluation

  Complexity: Time O(n), Space O(n). Each token is processed once. Operands are pushed; operators pop two values, compute, and push the result — all O(1) per token. The stack holds at most O(n) operands in the worst case. ---

• Part 11: Common Mistakes in Interviews

  1. Forgetting to check empty stack/queue before pop/dequeue -- always guard! 2. Off-by-one in circular queue -- test with capacity 1 and full conditions. 3. Confusing amortized vs worst-case -- "queue with two stacks" is amortized O(1),…

• Key Takeaways

  - Stack = LIFO, Queue = FIFO. This single distinction drives all their applications. - Monotonic stacks turn O(n^2) brute-force "next greater/smaller" problems into O(n). - Circular queues avoid wasted space in array-based queues with mo…