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()

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.