= FIFO queue
{c}
= Queue data structure
{synonym}
A <FIFO queue> is a <data structure> with first-in, first-out behavior: `enqueue` inserts at the rear, `dequeue` removes and returns the front, and `peek` inspects the front without removing it. Removal and inspection require a nonempty <FIFO queue>, or an explicitly defined empty-case result. Enqueue $A,B,C$ in that order, dequeue $A$, then enqueue $D$: the remaining <sequence> is $B,C,D$, with $B$ next. A <LIFO stack> would remove the most recently inserted item instead. A <FIFO queue> models arrival-order service and supplies the next <vertex> for <breadth-first search>; a stochastic service model belongs to <queueing theory>. https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/Queue.java[Sedgewick and Wayne, Algorithms: Queue interface and implementation]{ref}
The <FIFO queue> interface specifies removal order, not <time complexity>. A <linked list> with both front and rear pointers supports `enqueue`, `dequeue` and `peek` in $O(1)$ worst-case time under constant-cost pointer operations and allocation, as in Sedgewick and Wayne's implementation. A plain <array> that deletes its first entry by shifting the remaining $n-1$ entries takes $O(n)$ time per such removal. An <array> with advancing front and rear indices can avoid these shifts; storage and resizing policies still need analysis. The <two-list functional queue> gives a different implementation with constant <amortized analysis> cost along a single sequence of uses. These representation choices matter when deriving the linear <time complexity> of <breadth-first search> in <Big O notation>.
// Destination: computer-science.bigb
Back to article page
