A queue in a circular array

A queue is a collection that works on the first-in, first-out (FIFO) rule, like a line at a ticket counter. New items join at the back (enqueue), and items leave from the front (dequeue), so the item that has waited longest always leaves first. The goal is to make both operations take constant time, O(1), using a fixed-size array.

The idea in plain words

A first attempt keeps the front of the queue at index 0. But then every dequeue has to shift all remaining items one place to the left, which costs O(n). It is better to let the queue "walk" through the array. We keep two indices: head, the position of the front item, and tail, the first free position after the back item. Enqueue writes at tail and moves tail one step forward. Dequeue reads at head and moves head one step forward. Nothing ever shifts.

The catch is that both indices only move to the right, so they soon reach the end of the array even though the cells at the start have been freed. The fix is to treat the array as a ring: after the last index comes index 0 again. Moving forward means i = (i + 1) mod SIZE.

A 5-cell array holding 60, empty, 30, 40, 50 with head at index 2 and tail at index 1, drawn once as a row with an arrow from index 4 back to 0 and once as a ring of 5 cells
Head and tail only move forward and wrap from the last index to 0, so the queue 30 40 50 60 can sit in cells 2, 3, 4 and 0.

What the animation shows

The array has SIZE = 15 cells, indices 0–14 in blue. The Head and Tail boxes above it show the two indices. On Enqueue, a blue circle travels from the Tail box to cell tail, the value drops into it, and the Tail box is highlighted and advanced. On Dequeue, the circle goes from the Head box to cell head, the value moves up to "Dequeued Value", and Head advances. When an index passes 14, it goes back to 0. If you press Enqueue when the queue is full, or Dequeue when it is empty, nothing happens. Tick Random to fill the text field with a random number after each enqueue.

The operations

SIZE = 15;  A[0..SIZE-1];  head = 0;  tail = 0

isEmpty():  return head == tail
isFull():   return (tail + 1) mod SIZE == head

enqueue(x):
    if isFull(): error "queue full"
    A[tail] = x
    tail = (tail + 1) mod SIZE

dequeue():
    if isEmpty(): error "queue empty"
    x = A[head]
    head = (head + 1) mod SIZE
    return x

front():    return A[head]          // if not empty
size():     return (tail - head + SIZE) mod SIZE

The items in the queue are the cells head, head+1, …, tail−1, counted around the ring. That range may wrap past the end of the array.

A worked example

To keep it short, use SIZE = 5 (the page uses 15, but it behaves the same way at 14 → 0). A dot is an unused cell.

operation     head tail   A[0..4]            note
start           0    0    .  .  .  .  .       head == tail: empty
enqueue 10      0    1    10 .  .  .  .
enqueue 20      0    2    10 20 .  .  .
enqueue 30      0    3    10 20 30 .  .
enqueue 40      0    4    10 20 30 40 .       (4+1) mod 5 = 0 == head: FULL
enqueue 99      refused                       only 4 items fit in 5 cells
dequeue → 10   1    4    .  20 30 40 .
dequeue → 20   2    4    .  .  30 40 .
enqueue 50      2    0    .  .  30 40 50      tail wraps: (4+1) mod 5 = 0
enqueue 60      2    1    60 .  30 40 50      (1+1) mod 5 = 2 == head: FULL
enqueue 70      refused
dequeue → 30   3    1    60 .  .  40 50
dequeue → 40   4    1    60 .  .  .  50
dequeue → 50   0    1    60 .  .  .  .       head wraps: (4+1) mod 5 = 0
dequeue → 60   1    1    .  .  .  .  .       head == tail: empty again
dequeue         refused

After "enqueue 60", the queue 30 40 50 60 is stored as cells 2, 3, 4, 0: it wraps around the end. Its size is (1 − 2 + 5) mod 5 = 4. Values still come out in the order they went in: 10, 20, 30, 40, 50, 60.

Why one cell is always left empty

Suppose we let the queue fill all SIZE cells. After SIZE enqueues from an empty queue, tail would have gone all the way around and landed back on head. Then head == tail would mean "full", but it already means "empty". The indices alone cannot tell the two apart: with SIZE cells there are SIZE + 1 possible sizes (0 to SIZE), but only SIZE possible values of (tail − head) mod SIZE. There are two standard fixes:

  • Leave one cell empty (what this page does): call the queue full as soon as (tail + 1) mod SIZE == head. The 15-cell array then holds at most 14 values.
  • Keep a count (or a boolean "full" flag): empty is count == 0 and full is count == SIZE. All cells can be used, at the cost of one extra variable to update on every operation.
Two 5-cell arrays: on the left an empty queue with head and tail both at index 1; on the right a full queue holding 10, 20, 30, 40 with head 0 and tail 4, leaving cell 4 free
head == tail means empty, so the queue counts as full one cell early, when tail + 1 would land on head.

Why it is correct

The invariant is that the queue's items, from front to back, are exactly the cells from head up to (but not including) tail, going around the ring. At the start the queue is empty and head == tail, so the invariant holds. Enqueue puts the new item right after the current back item and extends the range by one at the back. Dequeue removes the front of the range. The full test makes sure tail never runs into head from behind, which would overwrite items that have not been dequeued yet. So the items leave in exactly the order they arrived.

Time and space complexity

  • enqueue, dequeue, front, isEmpty, isFull and size are all O(1): a few index calculations and one array access, and no loops.
  • Space is O(SIZE), reserved up front whether or not it is used.
  • Growing the array. A fixed array can fill up. A growable queue allocates an array twice as large when full, copies the items in queue order (starting at head and wrapping around) into positions 0, 1, 2, … of the new array, then sets head = 0 and tail = count. A single resize costs O(n). Because the size doubles, the total copying over n enqueues is under 2n, so enqueue is O(1) amortized.

Common mistakes, edge cases and variants

  • Forgetting the mod SIZE, so that an index runs off the end of the array.
  • Writing (tail − head) % SIZE for the size. In C, Java and JavaScript % can give a negative result, so add SIZE first.
  • When growing, copying the old array exactly as it is. The wrapped part then ends up in the wrong place. Copy in queue order instead.
  • Dequeuing from an empty queue or enqueuing into a full one. Check first, and report an error or return a special value.
  • Deque (double-ended queue): the same ring, but you can also add at the front (head = (head − 1 + SIZE) mod SIZE) and remove at the back. Java's ArrayDeque is exactly this kind of growable ring. C++ std::deque and Python's collections.deque use linked blocks of arrays instead.
  • Priority queue: items leave in order of priority, not arrival. It is usually built as a binary heap (see Heap), not as a ring.
  • Stack vs queue: a stack (LIFO) adds and removes at the same end, so it needs only one index (see Stack (array)). A queue uses both ends, so it needs two indices and the wrap-around. The same queue with linked nodes is on the Queue (linked list) page.

Where it is used

  • Ring buffers: keyboard and serial-port input buffers, audio and video streaming buffers, network card receive and transmit rings, and log buffers that keep the last N events.
  • Producer-consumer queues between threads or processes, where a fixed size also limits how far a fast producer can get ahead of a slow consumer.
  • Breadth-first search (the frontier is a FIFO queue), and task schedulers such as round-robin CPU scheduling and print queues.