Queue
A line. Join at the rear, leave from the front, so whoever has waited longest goes next.
A queue built from two stacks, each drawn with its bottom on the left and its top on the right. Enqueue pushes onto the in stack. Dequeue pops the out stack; when that is empty, every item is poured from in to out, which reverses them so the oldest ends up on top. Each item is moved at most three times in its life, so the pour is amortized O(1).
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.
The out stack is empty and in holds 5, 3, 9 bottom to top. Which value must dequeue return?
Answer: 5, the bottom of in. The oldest item is at the bottom of in; pouring brings it to the top of out.
Which value leaves the queue?
Answer: 5. The top of the out stack is the oldest item, so it leaves first.
Which value leaves the queue?
Answer: 3. The top of the out stack is the oldest item, so it leaves first.
Which value leaves the queue?
Answer: 9. The top of the out stack is the oldest item, so it leaves first.
The out stack is empty and in holds 7 bottom to top. Which value must peek return?
Answer: 7, the bottom of in. The oldest item is at the bottom of in; pouring brings it to the top of out.
Which value is at the front of the queue?
Answer: 7. The front is always the top of the out stack once it is non-empty.
Which value leaves the queue?
Answer: 7. The top of the out stack is the oldest item, so it leaves first.
Both stacks are empty and the script says dequeue. What happens?
Answer: Nothing, the queue is empty. No items anywhere means no front to serve.
How it runs, step by step
A queue built from two stacks, each drawn with its bottom on the left and its top on the right. Enqueue pushes onto the in stack. Dequeue pops the out stack; when that is empty, every item is poured from in to out, which reverses them so the oldest ends up on top. Each item is moved at most three times in its life, so the pour is amortized O(1).
Queue from two stacks, both empty.
enqueue 5: push it onto the in stack. Arrivals never touch the out stack.
Enqueued 5 onto the in stack.
enqueue 3: push it onto the in stack. Arrivals never touch the out stack.
Enqueued 3 onto the in stack.
enqueue 9: push it onto the in stack. Arrivals never touch the out stack.
Enqueued 9 onto the in stack.
dequeue: the out stack is empty, so the front of the queue is buried at the bottom of in. Pour: pop every item off in and push it onto out, 5, 3, 9 in that order, which puts 5, the oldest, on top of out.
Pouring 3 items from in to out.
Poured. The out stack now reads 9, 3, 5 bottom to top: reversed, so the queue's front, 5, is on top.
Out stack now 9, 3, 5.
dequeue: pop 5 off the out stack. It was the oldest item still waiting. Out still holds 9, 3.
Dequeued 5.
enqueue 7: push it onto the in stack. Arrivals never touch the out stack.
Enqueued 7 onto the in stack.
dequeue: pop 3 off the out stack. It was the oldest item still waiting. Out still holds 9.
Dequeued 3.
dequeue: pop 9 off the out stack. It was the oldest item still waiting. The out stack is empty again; the next dequeue will pour.
Dequeued 9.
peek: the out stack is empty, so the front of the queue is buried at the bottom of in. Pour: pop every item off in and push it onto out, 7 in that order, which puts 7, the oldest, on top of out.
Pouring 1 items from in to out.
Poured. The out stack now reads 7 bottom to top: reversed, so the queue's front, 7, is on top.
Out stack now 7.
peek: the top of the out stack is 7, the front of the queue. Nothing moves.
Front is 7.
dequeue: pop 7 off the out stack. It was the oldest item still waiting. The out stack is empty again; the next dequeue will pour.
Dequeued 7.
dequeue: both stacks are empty, so the queue is empty. Nothing to remove.
Queue empty.
10 operations cost 12 stack moves in total. A pour looks expensive, but each item is pushed onto in once, poured once and popped once, so the whole script is O(n): amortized O(1) per operation, which is the accounting trick behind this queue.
12 stack moves for 10 operations.
Remember
- First in, first out. The item that has waited longest leaves next.
- Enqueue and dequeue are both O(1). A circular buffer gets there without shifting anything.
- Breadth-first search is a queue of vertices waiting to be explored.
Topics covered
Related
Where this is used
Distributed systemsBackground job queues
Sidekiq keeps each queue as a Redis list and its workers block on BRPOP, which is a dequeue that waits; Celery on RabbitMQ or Redis is the same shape with a broker in the middle. The queue is what lets a web request hand off slow work and return immediately, and FIFO order is what stops old jobs starving while new ones keep arriving. That order costs something at scale: Amazon SQS standard queues spread messages over partitions and only make a best effort at arrival order, and its FIFO queues, which do guarantee it, cap throughput in exchange. Queue depth is also the cleanest backpressure signal a system has: a queue that grows means the consumers are slower than the producers.
NetworkingRouter and switch buffers
A packet arriving faster than the outbound link can send it waits in a FIFO, which is how a momentary burst gets absorbed instead of dropped. The failure mode is a buffer so deep that packets sit in it for hundreds of milliseconds before they are ever sent, which is bufferbloat: the link is busy, nothing is lost, and everything is slow. fq_codel fixes it by measuring how long a packet has been waiting rather than how many are waiting, and dropping from a queue that stays full.
BrowsersThe JavaScript event loop
Every timer callback, network response and click handler is appended to a task queue, and the loop runs one task to completion before starting the next, taking the oldest task in whichever queue it picks. With one thread and no preemption, a handler that takes 200ms delays every task queued behind it, which is what a janky page actually is. Promise callbacks sit in a separate microtask queue that is drained completely between tasks, which is why a promise callback runs before a setTimeout of 0 that was scheduled earlier.
ConcurrencyThread pools
Java's ThreadPoolExecutor is a queue plus a fixed set of workers blocked on take(), and a pool of goroutines receiving from one buffered channel is the same idea with the queue built into the language. The queue decouples how fast work arrives from how many threads you are willing to run, so a burst becomes a longer queue rather than a thousand new threads. The choice of queue is a capacity decision: Executors.newFixedThreadPool uses an unbounded one, so an overloaded pool grows until it runs out of memory, while a bounded queue with a rejection handler pushes back on the caller instead.
Why it works this way
Taking from the front of a plain array is the O(n) trap
CPython's list.pop(0) memmoves every remaining element down one slot, so each dequeue costs O(n) and draining a million items costs about 5 x 10^11 element moves instead of a million. The O(1) in the table is a claim about an implementation, not about the word queue: it holds only when the front is an index you move rather than a slot you empty. Use collections.deque, ArrayDeque, or the circular buffer above, and treat pop(0) inside a loop as a bug. JavaScript is murkier rather than safer: Array.prototype.shift is specified as moving every element down, but V8 skips the copy by left-trimming the backing store once the array is past a small length, so the cost is a property of the engine rather than of the language.
Two stacks: why one slow dequeue still averages O(1)
An item is pushed into the inbox once, poured into the outbox once, and popped once: three touches in its whole lifetime, however the operations interleave. So any sequence of n operations does at most about 3n work, which is constant per operation on average, even though one dequeue after a thousand enqueues moves a thousand items. Two details make it work: pour only when the outbox is empty, because pouring on every dequeue really is O(n) each time, and remember that amortized is not worst case. A call that must finish inside a deadline, like an audio callback or an interrupt handler, still misses it on the pour, and wants the circular buffer instead.
The fairness of FIFO is also head-of-line blocking
Serving the longest waiter first means one slow item holds up everything behind it, no matter how cheap those items are. HTTP/1.1 pipelining died on exactly this: responses had to come back in request order, so a single slow response stalled the rest, which is why HTTP/2 multiplexes independent streams instead, though that only pushes the blocking down to TCP, where one lost segment stalls every stream, and QUIC is the part that fixes it. In a job queue the same shape appears as one poison-pill task blocking a worker. Every fix breaks FIFO somewhere, by splitting work into separate queues, adding priorities, or rotating between flows the way fq_codel does.
An empty queue is not always an error
There are three honest answers to dequeue on an empty queue: throw, as the code here does and as Java's remove() does; return a sentinel, as poll() does with null; or wait until something arrives, as take() does. The third answer is what turns a queue from a container into a handoff between threads, and it is why a consumer thread costs nothing while idle. The sentinel choice has a consequence worth knowing: because null already means empty, the java.util.concurrent queues refuse null as an element, since storing one would make an empty queue and a queue holding null indistinguishable.
Read more
- Queue (abstract data type)Wikipedia
- Head-of-line blockingWikipedia
- BufferbloatWikipedia
- collections.deque, the O(1) queue in PythonPython documentation · docs.python.org
- BlockingQueue: throw, return null, or waitJava Platform SE 8 API · docs.oracle.com