Queues and Deques

What is a queue?

A queue is a line. Items join at the back and leave from the front, so the first one in is the first one out: FIFO, first in, first out. A railway ticket counter, a printer handling documents and a call centre's waiting callers all work this way.

The operations are:

• enqueue(x): add x at the back.
• dequeue(): remove and return the item at the front.
• peek(): look at the front item without removing it.
• is_empty() / size().

A good queue does all of them in O(1).

Why not just use an array?

A first attempt is to enqueue by appending to an array and dequeue by removing arr[0]. Appending is O(1), but removing the first element shifts every other element left: O(n) per dequeue. With a long queue this gets slow fast.

The fix is to stop moving the items and move the front instead. Keep an index head pointing at the front item. Dequeue just reads data[head] and moves head forward. When the back reaches the end of the array, it wraps around to the free slots at the start. This is a circular buffer (or ring buffer). The position of the back is always (head + count) % capacity.

Operations and their cost

A linked list with head and tail pointers also gives O(1) at both ends (see the Linked lists guide), but a circular buffer keeps items side by side in memory, which is faster in practice.

Building one yourself

The queue below is a circular buffer that doubles when full. The program prints the raw storage so you can watch the wrap-around (5 lands at index 0) and the unwrapping when it grows. It then uses the queue for round-robin scheduling, the way an operating system shares the CPU: each task runs for at most 2 time units and, if it isn't finished, rejoins the back of the queue.

class Queue:
    """A queue stored in a circular buffer: head is the front, count is how many items are stored."""

    def __init__(self, capacity=4):
        self.data = [None] * capacity
        self.head = 0
        self.count = 0

    def enqueue(self, item):
        if self.count == len(self.data):
            self._grow()
        tail = (self.head + self.count) % len(self.data)  # wraps around to the start
        self.data[tail] = item
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise IndexError("dequeue from empty queue")
        item = self.data[self.head]
        self.data[self.head] = None
        self.head = (self.head + 1) % len(self.data)
        self.count -= 1
        return item

    def peek(self):
        if self.count == 0:
            raise IndexError("peek at empty queue")
        return self.data[self.head]

    def is_empty(self):
        return self.count == 0

    def _grow(self):
        bigger = [None] * (len(self.data) * 2)
        for i in range(self.count):  # unwrap: copy in queue order
            bigger[i] = self.data[(self.head + i) % len(self.data)]
        self.data = bigger
        self.head = 0

    def storage(self):
        return "[" + ", ".join("_" if x is None else str(x) for x in self.data) + "]"


q = Queue()
for n in (1, 2, 3):
    q.enqueue(n)
print("enqueue 1, 2, 3:", q.storage(), "head", q.head)
print("dequeue:", q.dequeue())
q.enqueue(4)
q.enqueue(5)
print("enqueue 4, 5:", q.storage(), "head", q.head)
q.enqueue(6)
print("enqueue 6 (full, grows):", q.storage(), "head", q.head)
print("peek:", q.peek())
order = []
while not q.is_empty():
    order.append(str(q.dequeue()))
print("dequeue all:", " ".join(order))

# Round-robin scheduling: each task runs for at most 2 time units, then goes to the back of the queue.
tasks = Queue()
for task in (("A", 3), ("B", 1), ("C", 4)):
    tasks.enqueue(task)
clock = 0
while not tasks.is_empty():
    name, remaining = tasks.dequeue()
    run = min(2, remaining)
    clock += run
    if remaining > run:
        tasks.enqueue((name, remaining - run))
    else:
        print(f"{name} finished at time {clock}")

enqueue 1, 2, 3: [1, 2, 3, _] head 0
dequeue: 1
enqueue 4, 5: [5, 2, 3, 4] head 1
enqueue 6 (full, grows): [2, 3, 4, 5, 6, _, _, _] head 0
peek: 2
dequeue all: 2 3 4 5 6
B finished at time 3
A finished at time 6
C finished at time 8

Deques: both ends at once

A deque (double-ended queue, said "deck") lets you add and remove at both the front and the back in O(1). It can act as a stack or a queue, and it is the key structure in the Sliding Window Maximum problem in the lab. The circular buffer above extends naturally to a deque: adding at the front just moves head backwards, head = (head - 1 + capacity) % capacity.

Queues in the standard libraries

In Python, don't use list.pop(0) as a queue: that's the O(n) array removal described above. In JavaScript, array.shift() has the same problem on large arrays.

Where queues appear

• Breadth-first search (BFS): explore a tree level by level, or find shortest paths in a graph. See the Binary trees and Graphs guides, and Level Order Traversal in the lab.
• Scheduling: CPU time slices, print jobs, background job queues on servers.
• Buffers: keyboard input, network packets and video streaming all queue data between a producer and a consumer.
• Rate limiting: keep the timestamps of recent requests in a queue and drop the old ones from the front.

Common mistakes

• Dequeuing from the front of a plain array, which is O(n) per call.
• Getting the wrap-around arithmetic wrong. The back is (head + count) % capacity, not head + count.
• Copying a full circular buffer in storage order when growing. Copy in queue order, starting from head, or the items come out jumbled.
• Confusing a queue with a priority queue. A priority queue serves the smallest (or most urgent) item first, not the oldest. It is built with a heap.

When to use a queue

Use a queue whenever things must be handled in the order they arrived, or when you explore something level by level. If you need the newest item first, use a stack; if you need the most important item first, use a priority queue.