Stacks and queues are fundamental linear data structures that appear in countless LeetCode problems, from simple parentheses matching to complex monotonic stack optimizations. While conceptually simple — stacks follow LIFO (Last In First Out) and queues follow FIFO (First In First Out)— their applications span expression evaluation, graph traversal, sliding window optimizations, and priority-based processing. This comprehensive guide walks through stack fundamentals, classic applications (valid parentheses, min stack, RPN evaluation, daily temperatures), advanced monotonic stack techniques (next greater element, largest rectangle), queue-based BFS, priority queues for top-K problems, deque optimizations for sliding windows, and the classic "implement queue using stacks" puzzle. We'll cover time/space complexity analysis, common pitfalls, and practical interview strategies.

📚 LeetCode Algorithm Masterclass Series (10 Parts): 1. Hash Tables (Two Sum, Longest Consecutive, Group Anagrams) 2. Two Pointers Techniques (Collision pointers, fast-slow, sliding window) 3. Linked List Operations (Reverse, cycle detection, merge) 4. Binary Tree Traversal & Recursion (Inorder/Preorder/Postorder, LCA) 5. Dynamic Programming Intro (1D/2D DP, state transition) 6. Backtracking Algorithms (Permutations, combinations, pruning) 7. Binary Search Advanced (Integer/Real binary search, answer binary search) 8. → Stack & Queue (Monotonic stack, priority queue, deque) ← You are here 9. Graph Algorithms (BFS/DFS, topological sort, union-find) 10. Greedy & Bit Manipulation (Greedy strategies, bitwise tricks)

Stack Fundamentals

What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In First Out) principle. Think of it like a stack of plates: you add plates to the top and remove them from the top. The last plate added is the first one removed.

Core Operations

push(x): Add element x to the top of the stack
pop(): Remove and return the top element
peek() or top(): Return the top element without removing it
isEmpty(): Check if the stack is empty
size(): Return the number of elements

Time Complexity

All operations: average and worst-case

Space Complexity

-whereis the number of elements stored

Implementation

Python:

# Using list (append/pop from end)
stack = []
stack.append(1)      # push
top = stack[-1]      # peek
val = stack.pop()    # pop
is_empty = len(stack) == 0

Java:

Stack<Integer> stack = new Stack<>();
stack.push(1);
int top = stack.peek();
int val = stack.pop();
boolean isEmpty = stack.isEmpty();

C++:

#include <stack>
stack<int> st;
st.push(1);
int top = st.top();
st.pop();
bool isEmpty = st.empty();

Queue Fundamentals

What is a Queue?

A queue is a linear data structure that follows the FIFO (First In First Out) principle. Think of it like a line at a store: the first person in line is the first person served.

Core Operations

enqueue(x) or offer(x): Add element x to the rear/back
dequeue() or poll(): Remove and return the front element
peek() or front(): Return the front element without removing it
isEmpty(): Check if the queue is empty
size(): Return the number of elements

Time Complexity

All operations:average and worst-case (with proper implementation)

Space Complexity

-whereis the number of elements stored

Implementation

Python:

from collections import deque
queue = deque()
queue.append(1)         # enqueue
front = queue[0]         # peek
val = queue.popleft()    # dequeue
is_empty = len(queue) == 0

Java:

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
int front = queue.peek();
int val = queue.poll();
boolean isEmpty = queue.isEmpty();

C++:

#include <queue>
queue<int> q;
q.push(1);
int front = q.front();
q.pop();
bool isEmpty = q.empty();

Classic Stack Applications

LeetCode 20: Valid Parentheses

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if: 1. Open brackets must be closed by the same type of brackets 2. Open brackets must be closed in the correct order 3. Every close bracket has a corresponding open bracket of the same type

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Intuition

The key insight is that when we encounter a closing bracket, it must match the most recently opened bracket. This is exactly what a stack provides: we push opening brackets and pop when we see a matching closing bracket.

Algorithm

Initialize an empty stack
Iterate through each character in the string:
- If it's an opening bracket (, [, or {, push it onto the stack
- If it's a closing bracket ), ], or }, check if the stack is empty or if the top doesn't match
- If it matches, pop from the stack; otherwise, return false
After processing all characters, return true only if the stack is empty

Solution

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:  # Closing bracket
            if not stack or stack.pop() != mapping[char]:
                return False
        else:  # Opening bracket
            stack.append(char)
    
    return len(stack) == 0

Algorithm Visualization: The animation below demonstrates how the stack validates bracket matching:

Complexity Analysis

Time Complexity:whereis the length of the string. We traverse the string once.
Space Complexity:in the worst case when all characters are opening brackets.

Edge Cases

Empty string: Should return true
Single character: Should return false
Only opening brackets: Stack won't be empty, return false
Only closing brackets: Stack will be empty when checking, return false

LeetCode 155: Min Stack

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object
void push(int val) pushes the element val onto the stack
void pop() removes the element on the top of the stack
int top() gets the top element of the stack
int getMin() retrieves the minimum element in the stack

Example:

Input:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output:
[null,null,null,null,-3,null,0,-2]

Intuition

The challenge is maintaining the minimum element while allowing normal stack operations. We need to track the minimum at each level of the stack, not just the global minimum.

Approach 1: Two Stacks

Maintain two stacks: one for values and one for minimums.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
    
    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()
    
    def top(self) -> int:
        return self.stack[-1]
    
    def getMin(self) -> int:
        return self.min_stack[-1]

Approach 2: Single Stack with Pairs

Store pairs of (value, min_so_far) in a single stack.

class MinStack:
    def __init__(self):
        self.stack = []
    
    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            self.stack.append((val, min(val, self.stack[-1][1])))
    
    def pop(self) -> None:
        self.stack.pop()
    
    def top(self) -> int:
        return self.stack[-1][0]
    
    def getMin(self) -> int:
        return self.stack[-1][1]

Complexity Analysis

Time Complexity: All operations are
Space Complexity:for both approaches

LeetCode 150: Evaluate Reverse Polish Notation

Problem Statement

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN).

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note: Division between two integers should truncate toward zero.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22

Intuition

RPN (also called postfix notation) eliminates the need for parentheses. The algorithm is straightforward: 1. When we see a number, push it onto the stack 2. When we see an operator, pop the top two numbers, apply the operator, and push the result back

Solution

def evalRPN(tokens: List[str]) -> int:
    stack = []
    
    for token in tokens:
        if token in ['+', '-', '*', '/']:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            else:  # division
                stack.append(int(a / b))  # Truncate toward zero
        else:
            stack.append(int(token))
    
    return stack[0]

Important Note on Division

The problem requires truncation toward zero. In Python, int(a / b) handles this correctly for both positive and negative numbers:

int(13 / 5) = 2
int(-13 / 5) = -2

Complexity Analysis

Time Complexity:whereis the number of tokens
Space Complexity:in the worst case when all tokens are numbers

LeetCode 739: Daily Temperatures

Problem Statement

Given an array of integers temperatures representing the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the-th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

Intuition

For each day, we need to find the next greater element. This is a classic monotonic stack problem. We maintain a stack of indices where temperatures are in decreasing order. When we find a warmer day, we can resolve all previous colder days.

Solution

def dailyTemperatures(temperatures: List[int]) -> List[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # Store indices
    
    for i in range(n):
        # While current temperature is warmer than stack top
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index
        stack.append(i)
    
    return answer

Walkthrough

For temperatures = [73,74,75,71,69,72,76,73]:

i=0, temp=73: Stack [0]
i=1, temp=74: 74 > 73, pop 0, answer[0]=1, Stack [1]
i=2, temp=75: 75 > 74, pop 1, answer[1]=1, Stack [2]
i=3, temp=71: 71 < 75, Stack [2,3]
i=4, temp=69: 69 < 71, Stack [2,3,4]
i=5, temp=72: 72 > 69, pop 4, answer[4]=1; 72 > 71, pop 3, answer[3]=2; Stack [2,5]
i=6, temp=76: 76 > 72, pop 5, answer[5]=1; 76 > 75, pop 2, answer[2]=4; Stack [6]
i=7, temp=73: 73 < 76, Stack [6,7]

Result: [1,1,4,2,1,1,0,0]

Complexity Analysis

Time Complexity:
each element is pushed and popped at most once
Space Complexity:for the stack

Monotonic Stack

A monotonic stack is a stack where elements are in either strictly increasing or strictly decreasing order. It's incredibly powerful for problems involving "next greater/smaller element" patterns.

Key Pattern

Monotonic stacks help solve problems where you need to find:

Next greater element
Next smaller element
Previous greater element
Previous smaller element

LeetCode 496: Next Greater Element I

Problem Statement

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Solution

def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    # Build next greater element map for nums2
    next_greater = {}
    stack = []
    
    for num in nums2:
        while stack and num > stack[-1]:
            next_greater[stack.pop()] = num
        stack.append(num)
    
    # Build result for nums1
    return [next_greater.get(num, -1) for num in nums1]

Complexity Analysis

Time Complexity:whereis nums1.length andis nums2.length
Space Complexity:for the stack and map

LeetCode 84: Largest Rectangle in Histogram

Problem Statement

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.

Example:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The largest rectangle is formed by bars at indices 2 and 3 (heights 5 and 6), area =

Intuition

For each bar, the largest rectangle that includes it extends as far left and right as possible while maintaining heightthe bar's height. We need to find:

Left boundary: first bar to the left that's shorter
Right boundary: first bar to the right that's shorter

A monotonic stack helps us find these boundaries efficiently.

Solution

def largestRectangleArea(heights: List[int]) -> int:
    stack = []  # Store indices
    max_area = 0
    n = len(heights)
    
    for i in range(n):
        # Pop while current height is less than stack top
        while stack and heights[i] < heights[stack[-1]]:
            height = heights[stack.pop()]
            # Width extends from previous smaller to current smaller
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    
    # Process remaining bars
    while stack:
        height = heights[stack.pop()]
        width = n if not stack else n - stack[-1] - 1
        max_area = max(max_area, height * width)
    
    return max_area

Walkthrough

For heights = [2,1,5,6,2,3]:

i=0, h=2: Stack [0]
i=1, h=1: 1 < 2, pop 0, width=1-0=1, area=2*1=2, Stack [1]
i=2, h=5: Stack [1,2]
i=3, h=6: Stack [1,2,3]
i=4, h=2: 2 < 6, pop 3, width=4-2-1=1, area=6*1=6; 2 < 5, pop 2, width=4-1-1=2, area=5*2=10; Stack [1,4]
i=5, h=3: Stack [1,4,5]
Process remaining: pop 5, width=6-4-1=1, area=3*1=3; pop 4, width=6-1-1=4, area=2*4=8; pop 1, width=6, area=1*6=6

Maximum: 10

Complexity Analysis

Time Complexity:
each bar is pushed and popped once
Space Complexity:for the stack

Queue and BFS

Queues are essential for Breadth-First Search (BFS) algorithms, which explore nodes level by level.

BFS Pattern

from collections import deque

def bfs(start):
    queue = deque([start])
    visited = set([start])
    
    while queue:
        node = queue.popleft()
        # Process node
        
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

LeetCode 102: Binary Tree Level Order Traversal

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).

Example:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Solution

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

Complexity Analysis

Time Complexity:whereis the number of nodes
Space Complexity:for the queue

Priority Queue and Heap

A priority queue is an abstract data type where elements are served based on priority. In LeetCode, it's typically implemented using a heap.

Heap Operations

Insert:
Extract min/max:
Peek:

LeetCode 347: Top K Frequent Elements

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Approach 1: Min Heap (Size K)

Maintain a min-heap of size k containing the most frequent elements.

import heapq
from collections import Counter

def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    
    # Min heap of size k: (frequency, element)
    heap = []
    
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)  # Remove least frequent
    
    return [num for freq, num in heap]

Approach 2: Max Heap (All Elements)

Use a max-heap and pop k times.

def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    
    # Max heap: (-frequency, element) for max heap behavior
    heap = [(-freq, num) for num, freq in count.items()]
    heapq.heapify(heap)
    
    result = []
    for _ in range(k):
        result.append(heapq.heappop(heap)[1])
    
    return result

Approach 3: Bucket Sort

Since frequencies are bounded by array length, we can use bucket sort forsolution.

def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    n = len(nums)
    
    # buckets[i] = list of elements with frequency i
    buckets = [[] for _ in range(n + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    
    result = []
    for i in range(n, 0, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            break
    
    return result[:k]

Complexity Analysis

Approach 1:time,space
Approach 2:time,space
Approach 3:time,space

Deque (Double-Ended Queue)

A deque allows insertion and deletion from both ends intime. It's perfect for sliding window problems.

LeetCode 239: Sliding Window Maximum

Problem Statement

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the maximum element in each window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
- Window position: [1 3 -1] -3 5 3 6 7, max = 3
- Window position: 1 [3 -1 -3] 5 3 6 7, max = 3
- Window position: 1 3 [-1 -3 5] 3 6 7, max = 5
- Window position: 1 3 -1 [-3 5 3] 6 7, max = 5
- Window position: 1 3 -1 -3 [5 3 6] 7, max = 6
- Window position: 1 3 -1 -3 5 [3 6 7], max = 7

Intuition

We maintain a deque that stores indices in decreasing order of their values. The front always contains the index of the maximum element in the current window.

Solution

from collections import deque

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    dq = deque()  # Store indices
    result = []
    
    for i in range(len(nums)):
        # Remove indices outside current window
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Remove indices whose values are smaller than current
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Add to result when window is complete
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

Walkthrough

For nums = [1,3,-1,-3,5,3,6,7], k = 3:

i=0, val=1: DQ [0]
i=1, val=3: Remove 0 (3 > 1), DQ [1]
i=2, val=-1: DQ [1,2], result [3] (window complete)
i=3, val=-3: DQ [1,2,3], result [3,3]
i=4, val=5: Remove 3,2,1 (5 > all), DQ [4], result [3,3,5]
i=5, val=3: DQ [4,5], result [3,3,5,5]
i=6, val=6: Remove 5 (6 > 3), DQ [4,6], but 4 is out of window, remove it, DQ [6], result [3,3,5,5,6]
i=7, val=7: Remove 6 (7 > 6), DQ [7], result [3,3,5,5,6,7]

Complexity Analysis

Time Complexity:
each element is added and removed at most once
Space Complexity:for the deque

LeetCode 232: Implement Queue using Stacks

Problem Statement

Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Solution: Two Stacks Approach

Use one stack for input and one for output. When output is empty, transfer all elements from input to output.

class MyQueue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []
    
    def push(self, x: int) -> None:
        self.input_stack.append(x)
    
    def pop(self) -> int:
        self._move_input_to_output()
        return self.output_stack.pop()
    
    def peek(self) -> int:
        self._move_input_to_output()
        return self.output_stack[-1]
    
    def empty(self) -> bool:
        return len(self.input_stack) == 0 and len(self.output_stack) == 0
    
    def _move_input_to_output(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())

Amortized Complexity

Push:
Pop/Peek: Amortized(each element moved at most once)
Space:

LeetCode 225: Implement Stack using Queues

Problem Statement

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Solution: Two Queues Approach

Use one main queue and one temporary queue. For push, add to main. For pop/top, move all but last element to temp, then swap.

from collections import deque

class MyStack:
    def __init__(self):
        self.queue = deque()
    
    def push(self, x: int) -> None:
        self.queue.append(x)
        # Rotate to make newest element at front
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
    
    def pop(self) -> int:
        return self.queue.popleft()
    
    def top(self) -> int:
        return self.queue[0]
    
    def empty(self) -> bool:
        return len(self.queue) == 0

Alternative: Single Queue

class MyStack:
    def __init__(self):
        self.queue = deque()
    
    def push(self, x: int) -> None:
        self.queue.append(x)
        # Rotate to make newest element at front
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
    
    def pop(self) -> int:
        return self.queue.popleft()
    
    def top(self) -> int:
        return self.queue[0]
    
    def empty(self) -> bool:
        return len(self.queue) == 0

Complexity Analysis

Push:
need to rotateelements
Pop/Top:
Space:

Complexity Analysis Summary

Stack Operations

Operation	Time Complexity	Space Complexity
Push
Pop
Peek
Search

Queue Operations

Operation	Time Complexity	Space Complexity
Enqueue
Dequeue
Peek
Search

Priority Queue (Heap) Operations

Operation	Time Complexity	Space Complexity
Insert
Extract Min/Max
Peek
Build Heap

Deque Operations

Operation	Time Complexity	Space Complexity
Push Front/Back
Pop Front/Back
Peek Front/Back

Common Patterns and Tips

When to Use Stack

Matching problems: Parentheses, brackets, tags
Next/Previous greater/smaller element: Monotonic stack
Expression evaluation: RPN, infix to postfix
DFS traversal: Implicit call stack or explicit stack
Undo/Redo operations: History tracking

When to Use Queue

BFS traversal: Level-order processing
Sliding window: With deque for optimizations
Task scheduling: Round-robin, priority queues
Cache replacement: LRU cache (with hash map)

When to Use Monotonic Stack

Next greater element: Decreasing stack
Next smaller element: Increasing stack
Largest rectangle: Find boundaries efficiently
Trapping rainwater: Find left/right boundaries

When to Use Priority Queue

Top K problems: Maintain heap of size K
Merge K sorted lists: Compare heads efficiently
Dijkstra's algorithm: Process nodes by distance
Event scheduling: Process by time/priority

Q&A: Common Questions

Q1: Why use a deque instead of a list for queues in Python?

A: Python's list hastime complexity for pop(0) (removing from front), while deque.popleft() is. For BFS and queue operations, always use deque.

Q2: What's the difference between a stack and a queue?

A: Stack is LIFO (Last In First Out) - like a stack of plates. Queue is FIFO (First In First Out) - like a line at a store. The removal order is opposite.

Q3: Can I implement a stack using only one queue?

A: Yes, but push becomesbecause you need to rotate elements. The two-queue approach is more intuitive, but single queue works too.

Q4: When should I use a monotonic stack vs. a regular stack?

A: Use monotonic stack when you need to find "next greater/smaller element" patterns. Regular stack is fine for matching, expression evaluation, and DFS.

Q5: What's the space complexity of a recursive DFS vs. iterative DFS with stack?

A: Both arewhereis the height of the tree. Recursive uses call stack, iterative uses explicit stack. Iterative gives more control.

Q6: How do I choose between min-heap and max-heap for top-K problems?

A: For "top K largest", use min-heap of size K (remove smallest). For "top K smallest", use max-heap of size K (remove largest). In Python, use negative values for max-heap behavior with heapq.

Q7: Why is the sliding window maximum solutionnot?

A: Each element is added to deque once and removed at most once. Even though we have nested loops, the total operations are bounded by, making it.

Q8: Can I use a stack for BFS?

A: Technically yes, but it would give DFS behavior (LIFO). BFS requires FIFO, so use a queue. Stack + BFS = wrong algorithm.

Q9: What's the best way to implement a min-stack?

A: Two approaches: (1) Two stacks (values + mins), (2) Single stack with pairs (value, min_so_far). Both areoperations. Two stacks is slightly more space-efficient if many duplicates.

Q10: How do I handle division by zero in RPN evaluation?

A: Check if the divisor is zero before division. The problem usually guarantees valid input, but in interviews, mention this edge case.

Summary

Stacks and queues are deceptively simple data structures with powerful applications:

Key Takeaways

Stack (LIFO): Perfect for matching problems, expression evaluation, and monotonic stack optimizations
Queue (FIFO): Essential for BFS and level-order traversals
Monotonic Stack: Efficiently solves "next greater/smaller element" problems in
Priority Queue/Heap: Ideal for top-K problems and greedy algorithms
Deque: Optimizes sliding window problems withoperations on both ends

Problem Patterns

Valid Parentheses: Stack for matching
Min Stack: Maintain minimum at each level
RPN Evaluation: Stack for operands
Daily Temperatures: Monotonic stack for next greater
Largest Rectangle: Monotonic stack for boundaries
Level Order Traversal: Queue for BFS
Top K Frequent: Priority queue or bucket sort
Sliding Window Maximum: Deque for optimization

Interview Tips

Recognize the pattern: matching → stack, level-order → queue, next greater → monotonic stack
Watch for edge cases: empty stacks/queues, single elements, all same values
Consider space-time tradeoffs: monotonic stack trades space fortime
Practice implementations: Queue using stacks, stack using queues
Know your language: Python deque, Java PriorityQueue, C++ priority_queue

Master these fundamentals, and you'll be well-equipped to tackle stack and queue problems in LeetCode interviews!

Series Navigation

Stack Fundamentals

What is a Stack?

Core Operations

Time Complexity

Space Complexity

Implementation

Queue Fundamentals

What is a Queue?

Core Operations

Time Complexity

Space Complexity

Implementation

Classic Stack Applications

LeetCode 20: Valid Parentheses

Problem Statement

Intuition

Algorithm

Solution

Complexity Analysis

Edge Cases

LeetCode 155: Min Stack

Problem Statement

Intuition

Approach 1: Two Stacks

Approach 2: Single Stack with Pairs

Complexity Analysis

LeetCode 150: Evaluate Reverse Polish Notation

Problem Statement

Intuition

Solution

Important Note on Division

Complexity Analysis

LeetCode 739: Daily Temperatures

Problem Statement

Intuition

Solution

Walkthrough

Complexity Analysis

Monotonic Stack

Key Pattern

LeetCode 496: Next Greater Element I

Problem Statement

Solution

Complexity Analysis

LeetCode 84: Largest Rectangle in Histogram

Problem Statement

Intuition

Solution

Walkthrough

Complexity Analysis

Queue and BFS

BFS Pattern

LeetCode 102: Binary Tree Level Order Traversal

Problem Statement

Solution

Complexity Analysis

Priority Queue and Heap

Heap Operations

LeetCode 347: Top K Frequent Elements

Problem Statement

Approach 1: Min Heap (Size K)

Approach 2: Max Heap (All Elements)

Approach 3: Bucket Sort

Complexity Analysis

Deque (Double-Ended Queue)

LeetCode 239: Sliding Window Maximum

Problem Statement

Intuition

Solution

Walkthrough

Complexity Analysis

LeetCode 232: Implement Queue using Stacks

Problem Statement

Solution: Two Stacks Approach

Amortized Complexity

Space:

LeetCode 225: Implement Stack using Queues

Problem Statement

Solution: Two Queues Approach