Stack and Queue Explained

Stacks and queues are fundamental linear data structures that control the order of element access. They appear in tree traversals, BFS/DFS, expression evaluation, and scheduling problems.

Stack : LIFO (Last In, First Out)

The last element pushed is the first popped. Think of a stack of plates : you add and remove from the top.

// Stack operations
const stack: number[] = [];
stack.push(1);    // [1]
stack.push(2);    // [1, 2]
stack.push(3);    // [1, 2, 3]
stack.pop();      // returns 3, stack is [1, 2]
stack[stack.length - 1]; // peek: returns 2

Common Stack Use Cases

• Balanced parentheses: Push opening brackets, pop on closing. If stack is empty at the end, it is balanced.
• Next greater element: Monotonic stack : see below.
• Evaluate expression: Push operands, pop when operator is found.
• DFS traversal: The call stack is implicitly a stack for recursive DFS.

Queue : FIFO (First In, First Out)

The first element enqueued is the first dequeued. Think of a line at a store : first person in line is served first.

// Queue operations (use array with pointer or deque)
const queue: number[] = [];
queue.push(1);    // enqueue: [1]
queue.push(2);    // [1, 2]
queue.shift();    // dequeue: returns 1, queue is [2]

Common Queue Use Cases

• BFS traversal: BFS uses a queue to explore level by level.
• Task scheduling: Round-robin scheduling processes tasks in FIFO order.
• Sliding window maximum: Deque (double-ended queue) maintains candidates.

Monotonic Stack

A stack that maintains elements in strictly increasing or decreasing order. Used to find the next greater/smaller element in O(n).

// Next Greater Element : O(n)
function nextGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = []; // stores indices
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()!] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

Deque (Double-Ended Queue)

Supports O(1) insertion and deletion at both ends. Used for sliding window maximum and implementing both stack and queue.

Common Mistakes

• Using shift() on arrays for queue : shift() is O(n) in JavaScript. Use a proper queue implementation or deque for O(1).
• Not using a visited set with stack/queue : when traversing graphs, always track visited nodes.
• Confusing stack and queue in traversal : DFS uses stack, BFS uses queue. Mixing them up changes the traversal order.
• Off-by-one in monotonic stack : remember to process remaining elements in the stack after the loop.
• Not considering edge cases : empty input, single element, all identical elements.