Stacks & Queues

intermediate5 problems· Prerequisites: Big O & Complexity, Arrays & Strings, Linked Lists

Stack (LIFO)

A stack follows Last In, First Out. Think of a stack of plates - you add and remove from the top.

Operation	Stack
Push	O(1)
Pop	O(1)
Peek	O(1)

Uses: Undo/redo, backtracking, expression evaluation, DFS (implicitly via recursion).

Stack usageC#

var stack = new Stack<int>();

stack.Push(1);  // [1]
stack.Push(2);  // [1, 2]
stack.Push(3);  // [1, 2, 3]

int top = stack.Peek();  // 3 (no removal)
int popped = stack.Pop(); // 3, stack is now [1, 2]

// Monotonic stack pattern - maintain increasing/decreasing order
int[] NextGreaterElement(int[] arr) {
    var result = new int[arr.Length];
    Array.Fill(result, -1);
    var monoStack = new Stack<int>(); // stores indices

    for (int i = 0; i < arr.Length; i++) {
        while (monoStack.Count > 0 && arr[i] > arr[monoStack.Peek()]) {
            int idx = monoStack.Pop();
            result[idx] = arr[i];
        }
        monoStack.Push(i);
    }
    return result;
}
// For [2, 1, 3], returns [3, 3, -1]

Queue (FIFO)

A queue follows First In, First Out. Think of a line at a store.

Operation	Queue
Enqueue	O(1)
Dequeue	O(1)
Peek	O(1)

Uses: BFS, task scheduling, buffering, sliding window.

Queue usageC#

var queue = new Queue<int>();

queue.Enqueue(1);  // [1]
queue.Enqueue(2);  // [1, 2]
queue.Enqueue(3);  // [1, 2, 3]

int front = queue.Peek();  // 1 (no removal)
int dequeued = queue.Dequeue(); // 1, queue is now [2, 3]

// BFS template using Queue
void Bfs(TreeNode root) {
    var q = new Queue<TreeNode>();
    q.Enqueue(root);

    while (q.Count > 0) {
        int levelSize = q.Count;
        for (int i = 0; i < levelSize; i++) {
            var node = q.Dequeue();
            Console.Write(node.val + " ");
            if (node.left != null) q.Enqueue(node.left);
            if (node.right != null) q.Enqueue(node.right);
        }
        Console.WriteLine(); // new level
    }
}

Priority Queue

A priority queue dequeues elements by priority, not insertion order.

Operation	Priority Queue
Enqueue	O(log n)
Dequeue	O(log n)
Peek	O(1)

Uses: Dijkstra's algorithm, Huffman coding, K smallest/largest elements.

PriorityQueue usageC#

// Min-heap by default (lower priority = dequeued first)
var pq = new PriorityQueue<string, int>();

pq.Enqueue("low", 3);
pq.Enqueue("high", 1);
pq.Enqueue("medium", 2);

string next = pq.Dequeue(); // "high" (priority 1)

// For max-heap, negate priorities or use a custom comparer
var maxHeap = new PriorityQueue<int, int>(
    Comparer<int>.Create((a, b) => b.CompareTo(a))
);

// Top K frequent elements pattern
int[] TopKFrequent(int[] nums, int k) {
    var counts = new Dictionary<int, int>();
    foreach (var n in nums) counts[n] = counts.GetValueOrDefault(n) + 1;

    var heap = new PriorityQueue<int, int>();
    foreach (var kvp in counts) {
        heap.Enqueue(kvp.Key, kvp.Value);
        if (heap.Count > k) heap.Dequeue(); // keep only top K
    }

    var result = new int[k];
    for (int i = 0; i < k; i++) result[i] = heap.Dequeue();
    return result;
}

Stack vs Queue vs Priority Queue

Stack (LIFO) is for:

"Last thing first" - undo/redo, backtracking, parsing nested structures
DFS (implicitly via recursion or explicitly with a stack)
Problems where the most recent element is what matters (valid parentheses, next greater element)
Signal keywords: "nested", "backtrack", "most recent", "undo"

Queue (FIFO) is for:

"First come, first served" - BFS, task scheduling, buffering
Level-order traversal of a tree
Problems where order of arrival determines priority
Signal keywords: "level order", "shortest path (unweighted)", "streaming", "buffer"

Priority Queue (Heap) is for:

"Always process the most/least important item next"
K smallest/largest elements, Dijkstra, scheduling with priorities
When you need to repeatedly extract the min or max
Signal keywords: "top K", "K smallest/largest", "merge K sorted", "schedule"

Decision guide:

Signal	Structure
"Process in reverse order"	Stack
"First come, first served"	Queue
"Always pick the smallest/largest"	Priority queue
"Need BFS / level order"	Queue
"Parse nested brackets"	Stack
"Track K most frequent"	Priority queue

Common Mistakes / Gotchas

Popping from an empty stack Always check stack.Count > 0 / !stack.isEmpty() before popping. An empty pop is a runtime error in most languages.

Using a queue when a stack was needed (or vice versa) LIFO vs FIFO: if you need "most recent first" it's a stack (undo, backtracking). If you need "first come, first served" it's a queue (BFS, buffering).

JavaScript array as queue: shift() is O(n) Using arr.shift() in JS re-indexes the entire array. Use an index pointer or a proper queue implementation instead.

Priority queue comparator order confusion In a min-heap, the smallest element is dequeued first. In a max-heap, the largest. Always check whether your language's default is min or max before using it.

Stack overflow with deep recursion Each recursive call uses stack space. If your recursion depth could exceed ~1000, consider an iterative approach with an explicit stack.

Common Interview Patterns

Monotonic stack - next greater element, daily temperatures, largest rectangle in histogram
Valid parentheses - classic stack problem with matching brackets
Queue with two stacks - implement a queue using two stacks
Min stack - stack that supports GetMin() in O(1)
Level-order traversal - BFS using a queue (tree problems)
Top K elements - use PriorityQueue to efficiently track K largest/smallest

Popping from an empty stack Always check stack.Count > 0 / !stack.isEmpty() before popping. An empty pop is a runtime error in most languages.

JavaScript array as queue: shift() is O(n) Using arr.shift() in JS re-indexes the entire array. Use an index pointer or a proper queue implementation instead.

Stack overflow with deep recursion Each recursive call uses stack space. If your recursion depth could exceed ~1000, consider an iterative approach with an explicit stack.