Stack versus queue
“What is the difference between a stack and a queue, and how do you decide which one a problem needs?”
What this tests
- Whether LIFO vs FIFO is understood as a statement about *which pending item is handled next*.
- Ability to connect the structure to the traversal it induces (DFS vs BFS).
- Recognition of nesting and matching as stack signals, and ordering or levels as queue signals.
Strong answer
Both hold pending work; they differ only in which item comes out next. A Stack returns the most recently added item (LIFO), a Queue returns the oldest (FIFO). The consequence is bigger than the definition: a stack processes things in nested order — the innermost open thing finishes first — while a queue processes things in arrival order.
Stack signals: matching brackets, undo, expression evaluation, "most recent unmatched element", recursion elimination, and anything where the answer for the current element depends on the nearest previous element with some property (Monotonic Stack). Queue signals: level-by-level processing, "shortest number of steps", scheduling in arrival order, and Breadth-First Search (BFS).
A strong candidate also mentions the Deque as the generalization that supports both ends, used for sliding-window maximum and 0-1 BFS, and notes that swapping the stack for a queue in a graph traversal turns DFS into BFS with no other change.
Green flags · Red flags
- Frames the difference as "which pending item next", not just acronyms.
- Links stack to DFS and nesting, queue to BFS and levels.
- Mentions monotonic stack as the common interview extension.
- Knows the deque and where it is needed.
- Cannot give an example beyond "browser back button".
- Thinks a queue is needed for balanced parentheses.
- Implements a queue with
array.shift()and calls itO(1).
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
shift() on a JavaScript array not a real queue?