Queue

#How does it work?

A queue is a data structure where elements enter at one end and leave at the other, like a checkout line. Newcomers go to the rear, and the element at the front is served next.

This rule is called FIFO (First In, First Out): elements are processed in the order they arrived.

Queues are usually implemented with a linked list or a circular array (ring buffer), so both adding and removing are O(1).

#Try it yourself

#Basic operations

enqueue(x)

Adds x at the rear.

dequeue()

Removes and returns the front element. Fails if the queue is empty.

peek() / front()

Reads the front element without removing it.

isEmpty()

Tells whether the queue has any elements.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

class Queue:
    """Circular buffer: front and rear wrap around, so nothing is ever shifted."""

    def __init__(self, capacity: int) -> None:
        self._items = [0] * capacity
        self._front = 0
        self._size = 0

    def enqueue(self, value: int) -> None:
        if self._size == len(self._items):
            raise OverflowError("queue is full")
        self._items[(self._front + self._size) % len(self._items)] = value
        self._size += 1

    def dequeue(self) -> int:
        value = self.peek()
        self._front = (self._front + 1) % len(self._items)
        self._size -= 1
        return value

    def peek(self) -> int:
        if self._size == 0:
            raise IndexError("queue is empty")
        return self._items[self._front]

    def __len__(self) -> int:
        return self._size


q = Queue(8)
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1: first in, first out
print(q.peek())     # 2
print(len(q))       # 2

#Complexity

With a circular array or linked list, adding and removing are constant time. With a plain array, removing the front and shifting the rest would be O(n); a circular array avoids that by advancing the front and rear indices. The shifting in the animation shows the logical order.

#When to use it?

Job queues, print queues, message queues (e.g. RabbitMQ), task scheduling in operating systems, streaming buffers and breadth-first search (BFS) use queues. Whenever things must be handled in arrival order, a queue is the right choice.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Breadth-First Search (BFS)
• Deque
• Graph