Stacks & Queues
Practice & Revision
Stack and Queue pattern recognition decision tree, cheat sheet, and Top 15 must-solve stack and queue interview problems.
1. Introduction
This section serves as your comprehensive reference and practice guide for Stacks & Queues. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.
2. Stack & Queue Pattern Decision Tree
Use this guide to identify the correct stack/queue structure based on your algorithm constraints:
3. Revision Cheat Sheet
Common Stack & Queue API Reference
| Action | Stack (LIFO) | Queue (FIFO) | Deque (Double-Ended) |
|---|---|---|---|
| Java | stack.push(x) / pop() | queue.offer(x) / poll() | deque.addFirst(x) / removeLast() |
| Python | stack.append(x) / pop() | dq.append(x) / popleft() | dq.appendleft(x) / pop() |
| C++ | st.push(x) / pop() | q.push(x) / pop() | dq.push_front(x) / pop_back() |
| Time Complexity | O(1) guaranteed | O(1) guaranteed | O(1) guaranteed |
4. Top 15 Must-Solve Stack & Queue Problems
5. Problem-Solving Framework
When coding Stack & Queue problems, follow this checklist:
1. Recognize LIFO vs FIFO:
- If the problem demands matching elements by nested order (e.g. brackets, folder levels, undo actions), use a Stack.
- If the problem processes elements by order of arrival or layers (e.g. BFS traversals, message buffers), use a Queue.
2. Always Check for Empty States:
- Write defensive checks (!stack.isEmpty()) before calling pop() or peek() to avoid runtime crashes.
3. Use Monotonic Structures for Range Bound Lookups:
- If you need to search left or right to locate the "next greater" or "next smaller" element, a Monotonic Stack is your best choice, reducing complexity from O(N²) to O(N) time.
6. Quiz
Question 1: In 'Largest Rectangle in Histogram', how does a Monotonic Increasing stack locate boundaries?
Answer: We maintain indices of bars in strictly increasing order of height. When we encounter a bar shorter than the top of the stack, the popped bar's right boundary is the current index, and its left boundary is the index of the bar below it in the stack. This lets us calculate the area of the popped bar inO(1) time.
Question 2: What is the benefit of amortized O(1) in the 'Queue using Stacks' design?
Answer: Even though dequeuing may occasionally require moving all elements from theinput stack to the output stack taking O(N) operations, each element is pushed, popped, and transferred at most twice overall. Over M operations, the total cost is O(M), leading to an average (amortized) cost of O(1) per operation.
Question 3: In C++, what occurs when you call pop() on an empty std::stack?
Answer: It triggers undefined behavior, which usually leads to immediate memory segmentation faults or program crashes. Always check!st.empty() first.
Question 4: Why is Deque superior to Stack or Queue when implementing a sliding window maximum?
Answer: Because we need to insert and delete elements from both ends. We pop smaller elements from the rear to maintain monotonic order, and we pop expired indices from the front when they fall outside the sliding window.Question 5: What is the space complexity of validating brackets in a string of length N?
Answer:O(N) worst-case space, which occurs when the string consists entirely of opening brackets (e.g. (((((), requiring us to push all elements onto the stack.