A queue is a collection in which elements are added at one end and removed from the other, so the first item put in is the first taken out. This first-in-first-out, or FIFO, discipline is the opposite of a stack’s LIFO order, and it is captured by two operations: enqueue, which adds an element at the back, and dequeue, which removes and returns the element at the front. The everyday image is a line of people waiting their turn, served in the order they arrived. Knuth treats queues alongside stacks among the fundamental structures in Volume 1, “Fundamental Algorithms” (Knuth’s pages at Stanford, verified 2026-06-08).
Queues appear wherever work must be handled in arrival order. Operating systems hold pending tasks in scheduling queues; input and output streams are buffered in queues so a fast producer and a slow consumer can run at their own paces; and message-passing systems hand work between components through queues so that nothing is lost or reordered. In graph and tree algorithms, breadth-first traversal uses a queue to visit nodes level by level, the FIFO order ensuring that closer nodes are explored before farther ones.
Several variants extend the basic idea. A double-ended queue, or deque, allows adding and removing at both ends, generalizing both the stack and the queue. A circular buffer implements a fixed-size queue by wrapping the front and back pointers around a single array, reusing freed space without shifting elements. A priority queue relaxes strict arrival order, instead serving the element with the highest priority next, and is usually built on a heap rather than a plain linear structure.
Like a stack, a plain queue can be implemented on a linked list or an array. A linked list supports enqueue at the back and dequeue at the front in constant time by keeping references to both ends. A plain array makes the front operation awkward because removing the first element would shift the rest, which is exactly the inefficiency the circular buffer arrangement avoids.