When Stack, When Queue?

Stack and Queue solve different ordering problems. If the most recent element is needed first (Undo, Parsing, Depth-First Search with explicit Stack), the Stack is appropriate. If the order of arrival must be preserved (Queue, Breadth-First Search), the Queue is suitable.

Both ADTs can reside on arrays or linked structures. The choice of implementation affects constants and memory, not the semantic ordering.

Check: What invariant holds after a sequence of operations, and which error case is specified?

Two direction examples: Valid Parentheses [1], Implement Queue using Stacks [2].

Where used

Routing and Crawlers: BFS (Queue) for shortest unweighted paths, DFS/Stack for topology and nesting. Task Scheduler: FIFO for fairness, LIFO only if the most recently initiated task should be completed first (cache locality, Undo).

Depth

The appropriate structure follows from the desired temporal order. If the most recently discovered subproblems need to be completed first, LIFO is suitable. Conversely, if the order of arrival or the distance from the start must be preserved, FIFO is appropriate.

This choice fundamentally alters algorithms. In graph search, LIFO digs deeply into one branch, while FIFO processes nodes layer by layer according to their edge distance. Thus, the same graph and the same adjacency order can yield very different search trees.

In real systems, priorities and constraints come into play. A scheduler may require a priority structure, while Undo functions often combine two LIFO storages for forward and backward directions.

Difficulty levels

1. Associate everyday workflows with a temporal order.
2. Predict the output order for the same input sequence.
3. Derive search strategy and data structure from a system requirement.

Pitfalls

The structure is often chosen based on a familiar name rather than the required removal order. Prioritized tasks are not completely modeled by either of the two pure orders.