04-stacks-and-queues.md

Module 04: Stacks & Queues — Monotonic Structures & Buffers

Goal: Master LIFO and FIFO primitives, circular ring buffers, deque block architectures, monotonic stack/queue patterns for $O(N)$ range optimizations, and stack-based parsing.
Language: C++ (C++17/C++20)
Prerequisites: Modules 01, 02, and 03.

📑 Table of Contents

  1. Under the Hood: Stack & Queue Architecture
  2. C++ std::deque Internal Block Architecture
  3. Circular Queue / Ring Buffer Implementation
  4. Pattern 1: Monotonic Stack (Next Greater / Smaller Elements)
  5. Pattern 2: Min Stack with $O(1)$ Auxiliary Space
  6. Pattern 3: Monotonic Deque & Sliding Window Maximum
  7. Pattern 4: Queue via Stacks (Amortized Analysis)
  8. 5 Practice Problems with Detailed Solutions
  9. Top 10 FAANG Interview Questions

1. Under the Hood: Stack & Queue Architecture

1.1 Stack (LIFO: Last In, First Out)

  • Operations: push(x) $O(1)$, pop() $O(1)$, top() $O(1)$.
  • Can be implemented via Dynamic Array (std::vector) or Linked List.

1.2 Queue (FIFO: First In, First Out)

  • Operations: push(x) / enqueue(x) $O(1)$, pop() / dequeue() $O(1)$, front() $O(1)$.
STACK (LIFO): QUEUE (FIFO): ┌─────────────┐ Enqueue ──► [ 10 | 20 | 30 | 40 ] ──► Dequeue │ Element C │ Top Rear Front ├─────────────┤ │ Element B │ ├─────────────┤ │ Element A │ Bottom └─────────────┘

2. C++ std::deque Internal Block Architecture

std::stack and std::queue are container adapters. By default, both use std::deque (Double-Ended Queue) as their underlying container, not std::vector or std::list.

std::deque Memory Layout: Array of Pointers to Fixed-Size Chunks (e.g., 512 bytes) Map Array (Array of pointers): ┌──────────┬──────────┬──────────┬──────────┐ │ Ptr 0 │ Ptr 1 │ Ptr 2 │ Ptr 3 │ └────┬─────┴────┬─────┴────┬─────┴──────────┘ │ │ │ ▼ ▼ ▼ ┌──────┐ ┌──────┐ ┌──────┐ │Chunk0│ │Chunk1│ │Chunk2│ (Each chunk is contiguous memory) └──────┘ └──────┘ └──────┘

Why std::deque over std::vector or std::list?

  1. $O(1)$ push/pop at both front and back without shifting elements.
  2. No massive memory reallocation copies: When growing, it only allocates a new chunk and updates the pointer map.
  3. No iterator invalidation on push (unlike std::vector).
  4. Better cache locality than std::list because each chunk contains multiple contiguous elements.

3. Circular Queue / Ring Buffer Implementation

A Ring Buffer avoids moving array elements when popping from the front by using modulo arithmetic on a fixed-size buffer.

Buffer of Size 5: Index: 0 1 2 3 4 Array: [ 40 | 50 | _ | 20 | 30 ] ▲ ▲ │ │ rear = 1 front = 3
class MyCircularQueue { private: std::vector<int> data; int head; int tail; int size; int capacity; public: MyCircularQueue(int k) : capacity(k), size(0), head(0), tail(0), data(k) {} bool enQueue(int value) { if (isFull()) return false; data[tail] = value; tail = (tail + 1) % capacity; size++; return true; } bool deQueue() { if (isEmpty()) return false; head = (head + 1) % capacity; size--; return true; } int Front() { return isEmpty() ? -1 : data[head]; } int Rear() { return isEmpty() ? -1 : data[(tail - 1 + capacity) % capacity]; } bool isEmpty() { return size == 0; } bool isFull() { return size == capacity; } };

4. Pattern 1: Monotonic Stack (Next Greater / Smaller Elements)

A Monotonic Stack maintains its elements in strictly increasing or strictly decreasing order.

Why is it $O(N)$?

Every element is pushed onto the stack at most once and popped at most once. Across the entire loop, the total number of stack operations is at most $2N = O(N)$.

Problem: Next Greater Element to the Right Array: [ 2, 1, 2, 4, 3 ] Stack stores indices. Maintain stack in DECREASING order of values. Process 2: Stack: [2] Process 1: Stack: [2, 1] Process 2: 2 > 1 -> Pop 1 (NGE of 1 is 2). Push 2. Stack: [2, 2] Process 4: 4 > 2 -> Pop 2 (NGE of 2 is 4). Pop 2 (NGE of 2 is 4). Push 4.
// Template: Next Greater Element (indices stored) std::vector<int> nextGreaterElement(const std::vector<int>& arr) { int n = arr.size(); std::vector<int> nge(n, -1); std::stack<int> st; // Stores indices for (int i = 0; i < n; ++i) { while (!st.empty() && arr[i] > arr[st.top()]) { nge[st.top()] = arr[i]; st.pop(); } st.push(i); } return nge; }

5. Pattern 2: Min Stack with $O(1)$ Auxiliary Space

Standard MinStack uses an auxiliary stack storing pairs $(val, current_min)$, doubling memory.
Optimized Approach: Store encoded difference when a new minimum is pushed.

class MinStackOptimized { private: std::stack<long long> st; long long minVal; public: MinStackOptimized() {} void push(int val) { if (st.empty()) { st.push(val); minVal = val; } else if (val < minVal) { // Encode: 2 * val - minVal is always < val st.push(2LL * val - minVal); minVal = val; } else { st.push(val); } } void pop() { if (st.empty()) return; long long top = st.top(); st.pop(); if (top < minVal) { // Restore previous minimum: 2 * minVal - top minVal = 2 * minVal - top; } } int top() { long long top = st.top(); return (top < minVal) ? (int)minVal : (int)top; } int getMin() { return (int)minVal; } };

6. Pattern 3: Monotonic Deque & Sliding Window Maximum

Maintain a deque of indices where elements are sorted in descending order.

#include <deque> #include <vector> std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) { std::deque<int> dq; // Stores indices std::vector<int> result; for (int i = 0; i < nums.size(); ++i) { // 1. Remove elements outside window [i - k + 1, i] if (!dq.empty() && dq.front() <= i - k) { dq.pop_front(); } // 2. Maintain descending order in deque while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } // 3. Add current index dq.push_back(i); // 4. Record maximum (always at dq.front()) once window reaches size k if (i >= k - 1) { result.push_back(nums[dq.front()]); } } return result; } // Time Complexity: O(N) // Space Complexity: O(K)

7. Pattern 4: Queue via Stacks (Amortized Analysis)

class MyQueue { private: std::stack<int> inStack; std::stack<int> outStack; void transfer() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } } public: void push(int x) { inStack.push(x); // O(1) } int pop() { transfer(); int val = outStack.top(); outStack.pop(); return val; // Amortized O(1) } int peek() { transfer(); return outStack.top(); // Amortized O(1) } bool empty() { return inStack.empty() && outStack.empty(); } };

8. 5 Practice Problems with Detailed Solutions

Problem 1: Largest Rectangle in Histogram (LeetCode #84 - Hard)

Problem: Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

#include <vector> #include <stack> #include <algorithm> int largestRectangleArea(const std::vector<int>& heights) { int n = heights.size(); std::stack<int> st; // Stores indices of increasing heights int maxArea = 0; for (int i = 0; i <= n; ++i) { int currentHeight = (i == n) ? 0 : heights[i]; while (!st.empty() && currentHeight < heights[st.top()]) { int h = heights[st.top()]; st.pop(); // Width is from previous smaller element (st.top()) to current index i int width = st.empty() ? i : (i - st.top() - 1); maxArea = std::max(maxArea, h * width); } st.push(i); } return maxArea; } // Time Complexity: O(N) // Space Complexity: O(N)

Problem 2: Daily Temperatures (LeetCode #739 - Medium)

Problem: Given an array of integers temperatures represents daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the $i$-th day to get a warmer temperature.

#include <vector> #include <stack> std::vector<int> dailyTemperatures(const std::vector<int>& temperatures) { int n = temperatures.size(); std::vector<int> result(n, 0); std::stack<int> st; // Monotonic decreasing stack of indices for (int i = 0; i < n; ++i) { while (!st.empty() && temperatures[i] > temperatures[st.top()]) { int prevIndex = st.top(); st.pop(); result[prevIndex] = i - prevIndex; } st.push(i); } return result; } // Time Complexity: O(N) // Space Complexity: O(N)

Problem 3: Basic Calculator II (LeetCode #227 - Medium)

Problem: Given a string s representing an arithmetic expression containing +, -, *, / and non-negative integers, evaluate the expression without using eval().

#include <string> #include <stack> #include <numeric> int calculate(const std::string& s) { int n = s.length(); std::stack<int> st; int currentNumber = 0; char operation = '+'; for (int i = 0; i < n; ++i) { char c = s[i]; if (isdigit(c)) { currentNumber = currentNumber * 10 + (c - '0'); } if ((!isdigit(c) && !isspace(c)) || i == n - 1) { if (operation == '+') { st.push(currentNumber); } else if (operation == '-') { st.push(-currentNumber); } else if (operation == '*') { int top = st.top(); st.pop(); st.push(top * currentNumber); } else if (operation == '/') { int top = st.top(); st.pop(); st.push(top / currentNumber); } operation = c; currentNumber = 0; } } int result = 0; while (!st.empty()) { result += st.top(); st.pop(); } return result; } // Time Complexity: O(N) // Space Complexity: O(N)

Problem 4: Valid Parentheses (LeetCode #20 - Easy)

#include <string> #include <stack> bool isValid(const std::string& s) { std::stack<char> st; for (char c : s) { if (c == '(') st.push(')'); else if (c == '{') st.push('}'); else if (c == '[') st.push(']'); else { if (st.empty() || st.top() != c) return false; st.pop(); } } return st.empty(); } // Time Complexity: O(N) // Space Complexity: O(N)

Problem 5: Trapping Rain Water using Monotonic Stack (LeetCode #42 - Hard Alternative)

#include <vector> #include <stack> #include <algorithm> int trapStack(const std::vector<int>& height) { std::stack<int> st; // Stores indices of decreasing heights int water = 0; for (int i = 0; i < height.size(); ++i) { while (!st.empty() && height[i] > height[st.top()]) { int bottom = st.top(); st.pop(); if (st.empty()) break; int left = st.top(); int distance = i - left - 1; int boundedHeight = std::min(height[left], height[i]) - height[bottom]; water += distance * boundedHeight; } st.push(i); } return water; } // Time Complexity: O(N) // Space Complexity: O(N)

9. Top 10 FAANG Interview Questions

Q1: Why does std::stack lack a .clear() member function in C++?

Answer: std::stack is intentionally a constrained container adapter enforcing strict LIFO semantics. To clear it, assign an empty stack (st = std::stack<int>();) or loop while (!st.empty()) st.pop();.

Q2: How do you implement a Stack using a single Queue?

Answer: On each push(x):

  1. Enqueue $x$.
  2. Dequeue and re-enqueue the preceding $n-1$ elements:
q.push(x); for (int i = 0; i < q.size() - 1; ++i) { q.push(q.front()); q.pop(); }

push is $O(N)$, pop is $O(1)$.

Q3: What is the difference between Infix, Postfix, and Prefix expressions?

Answer:

  • Infix: Operator between operands ($A + B$). Requires parentheses for precedence rules.
  • Postfix (Reverse Polish Notation): Operator follows operands ($A , B , +$). No parentheses needed, evaluated left-to-right using a stack in $O(N)$.
  • Prefix (Polish Notation): Operator precedes operands ($+ , A , B$). Evaluated right-to-left.

Q4: How does the Shunting-Yard Algorithm convert Infix to Postfix?

Answer: Iterate through tokens:

  • If operand, append to output.
  • If (, push to operator stack.
  • If ), pop operators to output until ( is encountered.
  • If operator $op_1$, pop operators $op_2$ with higher/equal precedence from stack to output, then push $op_1$. At end, flush remaining operators. Runs in $O(N)$ time.

Q5: Why is Monotonic Stack $O(N)$ despite having a while loop inside a for loop?

Answer: By amortized analysis: Each index is pushed into the stack exactly once in the outer for loop and popped from the stack at most once in the inner while loop. Total stack operations across all iterations $\le 2N$, resulting in $\Theta(N)$ total running time.

Q6: How do you design a thread-safe Queue in C++?

Answer: Wrap std::queue with std::mutex and std::condition_variable.

  • push() locks mutex, pushes item, and calls cv.notify_one().
  • pop() locks std::unique_lock, waits on cv.wait(lock, [&]{ return !q.empty(); }), extracts front, pops, and returns.

Q7: What is the maximum number of elements a Monotonic Stack can hold?

Answer: In the worst case (when input array is strictly sorted in the direction that preserves monotonicity), the stack will hold all $N$ elements, requiring $O(N)$ space.

Q8: How can you implement a Max Stack with $O(1)$ push, pop, top, and peekMax, but $O(\log N)$ popMax?

Answer: Use a Doubly Linked List for elements and a std::map<int, std::vector<Node*>> (or balanced BST) mapping values to node pointers.

  • push: Add node to list tail, add pointer to map. $O(\log N)$.
  • peekMax: map.rbegin()->first. $O(1)$.
  • popMax: Extract node from largest key in map, unlink from DLL. $O(\log N)$.

Q9: What is a Lock-Free Queue?

Answer: A concurrent queue implementation using atomic operations (std::atomic, compare_exchange_weak) without mutex locks (e.g. Michael-Scott 2-lock queue or single-producer single-consumer ring buffer using memory barriers).

Q10: How do you find the Next Greater Element in a Circular Array?

Answer: Loop through the array twice using index modulo: for (int i = 0; i < 2 * n; ++i) accessing arr[i % n]. Maintain the monotonic stack of indices. Any remaining elements in stack after $2N$ iterations have no greater element (set to -1).