Stack vs queue: choose which item leaves next

An undo button should reverse your latest edit. A waiting list should usually offer the next place to its earliest arrival. Both store a sequence of items; their next removal follows a different rule. Choose the rule the task needs before choosing a container.

Same jobs, different removal order#

In this illustrative example, add Job 1, Job 2 and Job 3. Before removing anything, predict the next job under each rule. Switch the rule below while the jobs are still present: the values stay the same, but the next item changes.

Try it: same items, different exit

Add three jobs, then remove one as a stack and as a queue. The container can hold the same values; the removal rule changes the result.

Removal rule Stack: newest firstQueue: oldest first Add next job Remove one Reset

Add a job to start.

A stack removes Job 3, then Job 2, then Job 1. This is last in, first out, or LIFO. Adding is usually called push; removing is pop. Matching brackets needs this order: in ([]), the closing square bracket must match the most recently opened bracket, before the outer pair can close.

A FIFO queue removes Job 1, then Job 2, then Job 3. FIFO means first in, first out. Adding is often called enqueue; removing is dequeue. It suits a task whose waiting items should be taken in arrival order. Python’s queue documentation defines these policies by retrieval order and also provides LIFO and priority variants.

The lab models one removal at a time, with at most six jobs. It does not run workers, measure speed or model thread coordination. Its JavaScript array keeps the state easy to inspect; it is not an efficient queue implementation.

Choose the order, then the implementation#

A graph search makes the choice visible. A stack supports depth-first search, which follows a branch before returning to pending branches. A FIFO queue supports breadth-first search, which processes discovered nodes in increasing distance from the start when every edge counts as one step. Compare the same graph in the BFS and DFS experiment, or see how the rule produces different tree traversal orders.

The ordering rule does not require a particular memory layout. A stack can use a growable array or a linked list whose head is already known. A FIFO queue can use linked nodes with head and tail references, a ring buffer, or a container that supports both ends. Allocation and occasional growth still matter; constant-time pointer work does not mean zero cost.

In Python, list.append() and list.pop() implement a stack at the right end. For a queue, use deque.append() and deque.popleft(). The official deque reference documents approximately O(1) end operations and O(n) movement for list.pop(0). The deque versus list guide shows both ends and the effect of a size limit. Sharing work between threads also needs a suitable concurrency contract; the removal rule alone does not provide one.

Removal order is not completion order#

Suppose, in a simplified worker example, Job A takes ten steps and Job B takes one. Worker 1 removes A first; Worker 2 removes B next. B can finish while A is still running. FIFO has kept its promise: A was retrieved first. It never promised that A would finish first or that every worker would get an equal share of work.

Dependencies require more than a removal rule too. If a parent needs its children’s results, processing the parent first does not make those results available. A depth-first traversal can calculate results when it returns from each child; a queue-based design can wait explicitly for completed children. Merely replacing a queue with a stack does not create that coordination.

If urgency should override arrival order, inspect a priority queue. If the next calculation requires completed prerequisites, inspect topological ordering. Neither requirement should be inferred from the word “queue”.

Questions people also ask

5 QUESTIONS

▸ Is a deque a stack or a queue?

Neither exclusively. A deque is a container open at both ends; it becomes a stack when every push and pop happens at the same end, and a queue when pushes go in one end and pops come out the other. The container never changes — only the discipline applied to it does.

▸ Which is faster?

The ordering rule alone does not decide speed. Suitable implementations support constant-time end operations, sometimes amortised across many operations. Python list.pop(0) shifts the remaining items and costs O(n); deque.popleft() avoids that shift. Choose the required order before comparing the implementations.

▸ What is a priority queue?

It chooses the next item by priority rather than requiring FIFO order. Equal-priority items may use arrival order as a tie-breaker, depending on the implementation. Python's queue.PriorityQueue retrieves the lowest-valued entry first.

▸ Why does recursion use a stack?

In ordinary nested calls, a caller waits while its callee runs. Returning from the deepest call lets the caller continue, giving last-in, first-out behaviour. Some runtimes can optimise tail calls, so this explanation is not a promise of one physical stack frame for every call in every language.

▸ Does FIFO guarantee that jobs finish in order?

No. FIFO determines which queued item is removed first. With several workers, a later job can finish sooner because it takes less time. If results must appear in submission order, keep sequence numbers and coordinate their release separately.