Queue

A queue is a first-in, first-out (FIFO) collection: values join at the back and leave from the front, like people at a ticket counter.

An empty queue

empty

A queue is first in, first out (FIFO): join at the back, leave from the front — like a ticket counter.

Step 1 / 12
Size
0
  1. enqueue(4)
  2. enqueue(8)
  3. enqueue(2)
  4. dequeue()
  5. enqueue(6)
  6. peek()
  7. dequeue()
  8. dequeue()

Step by step

The example above, written out — the same steps the animation plays.

  1. 1An empty queue. A queue is first in, first out (FIFO): join at the back, leave from the front — like a ticket counter.
  2. 2enqueue(4). 4 joins at the back.
  3. 3enqueue(8). 8 joins at the back.
  4. 4enqueue(2). 2 joins at the back.
  5. 5dequeue(). Who is served next?
  6. 6dequeue() → 4. 4 was first in, so it is first out. Everyone else moves up.
  7. 7enqueue(6). 6 joins at the back.
  8. 8peek() → 8. peek looks at the front without removing it.
  9. 9dequeue(). Who is served next?
  10. 10dequeue() → 8. 8 was first in, so it is first out. Everyone else moves up.
  11. 11dequeue(). Who is served next?
  12. 12dequeue() → 2. 2 was first in, so it is first out. Everyone else moves up.

What's happening?

  1. enqueue adds a value at the back; dequeue removes and returns the value at the front.
  2. Whoever has waited longest is always served next.
  3. Implemented with a linked list or a circular array, both ends are O(1).

Complexity

Time
O(1) enqueue and dequeue
Space
O(n)

Where you'll meet it

Print and task queues, request buffers in web servers, message queues like Kafka and RabbitMQ, and breadth-first search.

Common mistake

Building a queue on an array by removing from index 0 — every dequeue then shifts all the others, O(n).

FAQ

Where are queues used in algorithms?

Breadth-first search keeps the nodes to visit in a queue — see BFS in the Visual Lab.

What is a priority queue?

A queue where the smallest (or most urgent) value leaves first, whatever its arrival order — usually built on a heap.

What is a deque?

A double-ended queue: you can add and remove at both ends.