Queue - The First-In, First-Out Data Structure

A Queue is the fair counterpart to the stack. Where a stack gives priority to the most recent item (LIFO), a queue gives priority to the oldest — FIFO (First-In, First-Out). The first item added is the first item served. It’s the data structure that models a real-world queue: the first person in line is the first person served.

A Brief History

The queue as a formal computer science abstraction emerged naturally from early batch-processing systems in the 1950s and 1960s. Early computers ran jobs submitted on punch cards — the first job submitted was the first processed. Operating system design formalized the queue as a scheduling primitive. Donald Knuth’s The Art of Computer Programming (1968) gave queues their canonical treatment alongside stacks and deques. The queue’s FIFO discipline also appears in networking (packet queues), CPU task scheduling, and the foundational algorithm of Breadth-First Search — published by Moore in 1959 and based entirely on queue mechanics.

How It Works

A queue exposes operations on both ends:

• Enqueue (offer): Add an element to the back — $O(1)$
• Dequeue (poll): Remove and return the front element — $O(1)$
• Peek (front): View the front element without removing it — $O(1)$
• isEmpty: Check whether the queue is empty — $O(1)$

Implementations:

• Array-backed (circular buffer): A ring buffer tracks head and tail indices. Enqueue advances the tail; dequeue advances the head. When they wrap around, you reuse freed slots. All operations $O(1)$
• Linked list-backed: Enqueue appends to the tail ($O(1)$ with a tail pointer); dequeue removes the head ($O(1)$). Natural choice for dynamic-size queues

Caution with arrays in JavaScript: Using arr.shift() for dequeue is $O(n)$ — it shifts every element left by one. For a proper $O(1)$ queue, use a linked list or a circular buffer class.

Space Complexity

A queue holding $n$ elements uses $O(n)$ space.

Advantages and Disadvantages

Advantages:

• $O(1)$ enqueue and dequeue (with proper implementation)
• Fair ordering — preserves the sequence in which items arrived
• Simple mental model: serve the oldest item first
• Foundation for BFS and many scheduling algorithms

Disadvantages:

• No random access — you can only see or remove the front
• A naive JavaScript array implementation (shift() for dequeue) is $O(n)$ per dequeue
• Less flexible than a deque (double-ended queue) if you need LIFO and FIFO in one structure

Variants Worth Knowing

Priority Queue: Elements dequeue in order of priority, not arrival time. Implemented with a heap. Used in Dijkstra’s algorithm, A* search, and OS process scheduling. Dequeue is $O(\log n)$ instead of $O(1)$.

Deque (Double-Ended Queue): Supports $O(1)$ insertion and deletion at both ends. Acts as both a stack and a queue. Used in the monotone deque technique for sliding window problems.

Circular Queue: Fixed-size queue that wraps around. Used in OS kernel buffers, audio streaming, and network packet buffers where bounded memory is required.

When to Use a Queue

Any FIFO access pattern calls for a queue:

• BFS traversal — Breadth-First Search is entirely queue-driven: enqueue unvisited neighbors, dequeue to process. The queue is why BFS finds shortest paths
• Task/job scheduling — process tasks in the order they arrive; worker pools drain queues
• Print spooler — documents print in the order submitted
• Network packet handling — router buffers are queues; packets are forwarded in arrival order
• Producer-consumer patterns — a queue decouples the producer (adds work) from the consumer (processes work), letting them run at different speeds
• Tree level-order traversal — printing a tree level by level uses a queue to track “what’s next at this depth”
• Rate limiting — a sliding window of request timestamps in a queue tracks API call rates

In conclusion, the queue is computing’s fairness primitive. FIFO order is the natural expectation in most systems — the first request should be the first served. From BFS graph traversal to OS schedulers to message brokers like Kafka, queues are the backbone of ordered, fair processing. Reach for a queue whenever the order of arrival must determine the order of service.