Queue and stack visualizer

Pick a structure and add or remove elements. The picture shows the memory the structure really uses: the slots of the array, which of them hold elements, and where the head, tail or top is. The log names every step, and the totals count slot writes, elements copied when the array grows, and elements moved between the two stacks.

• Enqueue until the ring buffer is full: the next enqueue allocates twice the space and copies everything, unwrapping the elements so the head is at slot 0.
• Dequeue a few and enqueue again: the tail wraps round to slot 0 and reuses the space at the front, with nothing shifted.
• In the queue made from two stacks, enqueue several and then dequeue once: every element moves to the out stack in one go. The next dequeues move nothing.
• Press "20 random" a few times and watch work per operation settle at a small constant, however large the occasional copy.

A queue is a collection where elements are added at one end, the tail, and removed from the other, the head, so they leave in the order they arrived: first in, first out, or FIFO. A stack adds and removes at the same end, the top, so the newest element always leaves first: last in, first out, or LIFO. Both offer only these operations plus a look at the next element, and both can do them in constant time.

A deque (double-ended queue) allows both at either end, so it can serve as either. A priority queue keeps the same interface but always removes the element with the smallest key; it is a different structure underneath, usually a binary heap.

A stack is the simplest: an array and the index of the next free slot. A push writes there and increments the index; a pop decrements it and reads.

A queue in a plain array would have to shift every element when the head is removed, or leave unused space at the front forever. A ring buffer, also called a circular buffer, avoids both: the head and tail indices advance through the array and wrap round to slot 0 at the end, so freed space at the front is reused. A deque's head can also step backwards, wrapping to the last slot. With a capacity that is a power of two, the wrap is a bitwise AND instead of a division, which is why many implementations, Linux's kfifo among them, round the size up to one.

When the array is full it must be replaced by a larger one, copying every element. That one operation costs O(n), but if the capacity grows by a constant factor the copies are rare enough to average out. Elements copied per element added, over n pushes onto a stack that starts with 4 slots:

A queue can be built from two stacks. New elements are pushed on the in stack. Removals pop from the out stack, and when it is empty the whole in stack is popped onto it first, which reverses the order so the oldest element ends up on top.

Each element is pushed on the in stack once, moved once and popped from the out stack once, so the average cost per operation is constant. The cost is lumpy: after n enqueues, the first dequeue moves all n elements, and the next n − 1 move none. Moves between the stacks, over n enqueues followed by n dequeues:

A server's request queue is where the choice of order has real consequences. FIFO looks fair, but when requests arrive faster than they can be served, the queue grows without limit and every request waits behind all the older ones. Clients give up long before their turn, and the server spends its time answering requests nobody is waiting for any more.

Ben Maurer's 2015 article "Fail at Scale" describes two fixes Facebook uses. A queue timeout in the style of CoDel limits how long a request may wait: if the queue has not been empty at any time in the last 100 ms, new requests may wait only 5 ms, otherwise 100 ms, and requests that run out of time are rejected without doing the work. Adaptive LIFO serves requests in FIFO order normally but switches to LIFO once a queue builds up, so the newest requests, whose clients are still waiting, are served first.

The simulation below has one server with a mean service time of 1 ms (exponentially distributed), requests arriving at random, and clients that give up after 100 ms. Adaptive LIFO here switches when the queue has not been empty for 100 ms, the same signal the timeout uses. Share of all requests answered in time:

• The call stack. Every function call pushes a frame with its arguments, locals and return address, and returning pops it; recursion depth is stack depth.
• Parsers and interpreters. Matching brackets, evaluating expressions in postfix order and running stack-based virtual machines such as the JVM and CPython's bytecode interpreter.
• Graph search. Breadth-first search keeps its frontier in a queue, depth-first search in a stack; swapping one for the other changes the order nodes are visited and nothing else.
• Channels and kernel buffers. A buffered Go channel is a ring buffer with send and receive indices, and Linux's kfifo is a lock-free ring buffer for one producer and one consumer.
• High-throughput messaging. The LMAX Disruptor passes events between threads through a preallocated ring buffer with sequence numbers instead of a locked queue.
• Library deques. Java's ArrayDeque is a resizable ring buffer; Python's collections.deque is a doubly linked list of fixed-size blocks, so it never copies elements to grow.

Alan Turing's 1946 design for the ACE computer used a stack of return addresses for subroutines, with instructions he called BURY and UNBURY. Friedrich Ludwig Bauer and Klaus Samelson patented the "Kellerprinzip" (cellar principle) in 1957, using a stack to translate arithmetic formulas, and it went into the design of ALGOL 60 compilers. The study of queues as waiting lines is older: Agner Krarup Erlang analysed telephone exchanges as queues from 1909, founding queueing theory, and the M/M/1 notation used above is David Kendall's, from 1953.