Queue (data structure)
A queue is an abstract data type that follows the First-In-First-Out (FIFO) principle, where elements are added at the rear (enqueue) and removed from the front (dequeue), mirroring a real-world waiting line. All primary operations (enqueue, dequeue, front/peek) run in O(1) time when implemented with a circular array or doubly linked list. Queues are essential for breadth-first search, CPU and disk scheduling, inter-process communication (message passing), print spooling, and buffering in streaming and network protocols.
Queue Variants and Their Applications
| Queue Variant | Ordering Policy | Key Operations | Time Complexity | Real-World Use |
|---|---|---|---|---|
| Simple Queue (FIFO) | First in, first out | enqueue, dequeue, front | O(1) all | BFS, print spooler |
| Priority Queue | Highest priority first | insert, extract-max/min | O(log n) insert/extract | Dijkstra, OS scheduling |
| Double-Ended Queue (Deque) | Both ends accessible | push/pop front and rear | O(1) all | Sliding window algorithms |
| Circular Queue | FIFO with wrap-around | enqueue, dequeue | O(1) all | Fixed-size buffers, rings |
| Blocking Queue | FIFO with synchronisation | blocking enqueue/dequeue | O(1) amortised | Producer-consumer pattern |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Stack (data structure)
A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle, where elements are added (pushed) and removed (popped) only from one end called the top. Stacks support three primary operations: push (add element to top), pop (remove and return top element), and peek/top (inspect top element without removal), all in O(1) time. They are fundamental to function call management (call stack), expression evaluation (operator precedence, postfix notation), depth-first search, backtracking algorithms, and undo mechanisms in text editors.
Breadth-First Search
Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the current depth level before moving on to vertices at the next depth level, using a queue data structure to track which vertices to visit next. It is guaranteed to find the shortest path (in terms of number of edges) between a source vertex and any reachable vertex in an unweighted graph. BFS is widely used in network routing protocols, social network analysis, and solving puzzles like the shortest path in a maze.
Priority Queue
A priority queue is an abstract data type similar to a regular queue or stack but where each element has an associated priority; elements are served in order of their priority rather than their insertion order. It supports at minimum the operations of inserting an element and extracting the element with the highest (or lowest) priority. Priority queues are commonly implemented using binary heaps, and they are essential in algorithms such as Dijkstra's shortest path, A* search, Prim's minimum spanning tree, and task scheduling in operating systems.
The word "queue" comes from the Latin "cauda" (tail) via Old French "coe/queue," meaning a line of waiting people or vehicles. Its adoption into computing terminology was natural given the FIFO analogy to waiting lines. The data structure was formalised alongside stacks in early 1960s computer science literature, with Donald Knuth's "The Art of Computer Programming" (1968) providing a definitive treatment of both structures.