Stacks, Queues, and Deques
Choose the ordering and overflow behavior before choosing the container. A stack retrieves the newest item first, a FIFO queue retrieves the oldest first, and a deque supports both ends. A bounded history that drops old items is different from a work queue that blocks or rejects a producer when full.
For concurrent work, also define who owns shutdown, failure, retry, and completion. A container can hold the next job without providing a durable delivery protocol. Decide what the application must preserve when a worker fails before treating a queue API as the whole design.
TL;DR
- Choose the ordering and overflow behavior before choosing the container.
- A stack returns the newest item first, a FIFO queue the oldest, and a deque supports both ends.
- A bounded history that evicts old items is different from a work queue that blocks or rejects producers when full.
- For concurrent work, decide who owns shutdown, failure, retry, and completion — a container is not a durable delivery protocol.
- Track task success and failure separately from queue accounting such as
join().
Quick Example
This standard-library example contrasts automatic history eviction with explicit rejection when a work queue is full. It then retrieves each queued item and completes its task accounting.
The deque keeps only two recent values and discards the oldest. The Queue rejects the third nonblocking insertion rather than silently dropping work. This is a single-threaded API check, not a throughput, multi-worker, shutdown, crash-recovery, or durable processing test. Join completes because the example explicitly balances retrievals with task_done calls; that says nothing about an external business effect.
Core Concepts
Ordering describes retrieval, not every runtime outcome
A stack is useful when the most recently added item should be considered next, such as an explicit traversal stack. FIFO ordering is useful when admitted work should be retrieved in arrival order. A deque is useful when the algorithm needs both ends, such as a sliding-window representation.
With multiple workers, FIFO retrieval does not guarantee FIFO completion. A later task may finish first because its processing is shorter. If completion order matters, model that requirement explicitly rather than assuming a FIFO container supplies it.
Python documents approximately constant-time deque appends and pops at either end. It contrasts these with list operations at the front that require moving existing elements. Use those documented operations when reasoning about the algorithm; do not generalize endpoint costs to every deque operation. Deque documentation
Capacity needs an overflow policy
A bounded deque evicts items from the opposite end during relevant append operations when full. That can suit recent history but can lose work if used as an unreviewed work queue. Queue's positive maxsize instead limits admitted waiting items, and blocking insertion waits for space. Nonblocking insertion can raise Full. Queue documentation
These are conditional choices. A deque is not an inferior queue; it has different semantics. The right choice preserves the application's intended loss and waiting behavior.
Completion and success are separate states
Queue tracks unfinished tasks so a coordinator can wait until task_done has been called for admitted work. The worker still needs an explicit policy for whether the attempt succeeded, failed, or requires retry. Calling task_done in cleanup may correctly finish an attempt's accounting without proving the underlying operation succeeded.
Define the transition between retrieval and effect. If a worker modifies another system and then crashes, an in-memory queue does not establish whether a retry should occur or whether the effect was already applied. Durable receipt, idempotent business identity and retry ownership belong to a larger protocol.
Avoid using qsize or empty as a promise about a later operation in concurrent code. Python documents these observations as approximate for coordination purposes. Prefer the operation's supported blocking, timeout, or exception behavior rather than a check-then-act sequence that can race.
Best Practices
Write the admission policy in plain language: wait, reject, drop newest, drop oldest, or persist elsewhere. Connect each choice to the consequence of losing or delaying a job. A sensor display may tolerate dropping old samples; a billing task usually needs a different design and qualified review of its actual effects.
Size capacity using workload evidence. A limit of two items does not bound memory if each item can contain a very large payload. Consider payload size, producer rate, service time, and what happens during downstream failure. A queue that absorbs a short burst can still remain full indefinitely under sustained overload.
Define worker lifecycle separately from storage. Identify how workers stop accepting new work, finish or release current work, and report completion or failure. Choose shutdown APIs available in the pinned runtime; do not assume a feature documented for a newer Python release exists in an older one. This example uses APIs available in the checked Python 3.12 environment.
Test empty, full, rejection, duplicate admission, worker failure and shutdown boundaries appropriate to the actual design. Keep the meaning of task completion explicit in assertions. A test that calls task_done for everything and waits successfully may demonstrate balanced counters while missing a dropped business operation.
Reverse the container choice when the required semantics change. If a recent-history buffer becomes a mandatory processing backlog, automatic eviction is no longer a harmless detail. If retrieval is single-threaded and concurrency features add no value, a simpler deque may be sufficient. Start from the required behavior and make the container justify its place.
Common Mistakes
Using list.pop(0) as a queue
Using deque(maxlen) as a work backlog
Treating queue capacity as a memory bound
Equating join() with success
FAQ
Is a bounded deque a backpressure queue?
Not in the demonstrated append behavior. It evicts old entries to retain the configured length. A bounded work queue can instead block or reject admission, leaving the producer responsible for its next action.
Does FIFO mean jobs finish in order?
Not with independent workers. FIFO determines retrieval order; processing duration and failures can change completion order. Enforce ordered effects explicitly if the application requires them.
What should I measure first?
Measure admission rate, waiting time, active processing, failures, rejection and payload sizes under representative load. The toy checks establish basic API behavior only and do not supply capacity or performance recommendations.