What's the difference between a stack and a queue, and when would you use each?
AlgorithmsJunior
In shortA stack is last in, first out; a queue is first in, first out. Use a stack for undo, matching brackets and depth-first traversal, and a queue for processing in arrival order and breadth-first traversal.
Model answer
- A stack is LIFO, last in, first out: push and pop at the top, like a pile of plates. Used for undo, the back button, matching brackets, evaluating expressions, and depth-first search. Function calls themselves live on the call stack, which is why very deep recursion can overflow.
- A queue is FIFO, first in, first out: add at the back, remove from the front, like a line at a shop. Used for tasks in arrival order, message processing, rate-limited work, and breadth-first search, which finds shortest paths in unweighted graphs.
Both have O(1) operations at their ends, but only with the right type:
| Stack | Queue | |
|---|---|---|
| Swift | Array (append, popLast) | Deque from swift-collections |
| Kotlin | ArrayDeque (addLast, removeLast) | ArrayDeque (addLast, removeFirst) |
| Java | ArrayDeque (push, pop) | ArrayDeque (offer, poll) |
A strong answer also mentions the monotonic stack for “next greater element” problems, and bounded queues for backpressure between producers and consumers.
What they're looking for
Correct definitions with everyday examples, O(1) operations at the ends, concrete use cases including DFS/BFS, and the right type in your language (ArrayDeque, Array, Deque).
Common mistakes
- Using an ArrayList's remove(0) or a Swift Array's removeFirst() as a queue, which is O(n).
- Recommending Java's legacy Stack class.
- Not connecting recursion to the call stack.
More algorithms questions
- How do you work out and explain the time and space complexity of your solution?Junior
- How do you find the first occurrence of a value in a sorted array that has duplicates?Mid-level
- When would you use BFS instead of DFS, and vice versa?Mid-level
- How do you approach a dynamic programming problem?Mid-level