Stacks, queues, and deques

Stacks model last-in-first-out work such as parsing brackets, undo history, DFS, and monotonic candidates. Queues model first-in-first-out work such as BFS, scheduling, and buffering. Deques support both ends and appear in sliding window maximum and double-ended scheduling tasks.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Interviewers look for the access invariant: what enters, what leaves, and why the structure guarantees the next correct item.

Common pitfalls: Using Array.shift in JavaScript can be O(n) because elements move. Prefer a head index or deque abstraction for queues in performance-sensitive examples.

Checklist:

• State LIFO or FIFO.
• Explain the invariant.
• Pick head-index queues in JS.
• Test empty-pop behavior.