Circular Queue

A circular queue solves the wasted-space issue of a linear array queue by reusing freed positions via wrap-around indexing. Both enqueue and dequeue remain O(1).

On this page

Representation — array with front/rear pointers
Conditions — full and empty checks
Example in C — enqueue/dequeue with modulo
Trade-offs — fixed-size efficiency

1) Circular queue representation

Core fields in a circular queue
Field	Purpose	Rule
`q[]`	Stores values	Fixed capacity `MAX`
`front`	Next index to dequeue	Advance by `(front + 1) % MAX`
`rear`	Last inserted index	Advance by `(rear + 1) % MAX` before insert
`size`	Current element count	Empty if `size == 0`, full if `size == MAX`

2) Key operations and conditions

Circular queue operation mapping
Operation	Logic	Failure case
`enqueue(x)`	check full, move rear circularly, assign, increment size	Overflow if full
`dequeue()`	check empty, read front, move front circularly, decrement size	Underflow if empty
`peek()`	return `q[front]` without changing indices	Underflow if empty

3) Example in C

#include <stdio.h>

#define MAX 5

static int q[MAX];
static int front = 0;
static int rear = -1;
static int size = 0;
static int queue_last;

int is_empty(void) { return size == 0; }
int is_full(void)  { return size == MAX; }

int enqueue(int value) {
    if (is_full()) return 0;
    rear = (rear + 1) % MAX;
    q[rear] = value;
    size++;
    return 1;
}

int dequeue(void) {
    if (is_empty()) return 0;
    queue_last = q[front];
    front = (front + 1) % MAX;
    size--;
    return 1;
}

int peek(void) {
    if (is_empty()) return 0;
    queue_last = q[front];
    return 1;
}

int main(void) {
    enqueue(10); enqueue(20); enqueue(30); enqueue(40);
    dequeue(); dequeue();      /* frees two positions */
    enqueue(50); enqueue(60);  /* wraps around */

    if (peek()) printf("peek: %d\n", queue_last);
    return 0;
}

Enqueue operation

Circular enqueue trace (`MAX = 5`)
Step	Operation	Value	front (before)	rear (before)	size (before)	Is full?	Action (circular)	rear (after)	Queue array state	size (after)
1	`enqueue(10)`	10	0	-1	0	No	`rear = (0) % 5 = 0`, `q[0]=10`	0	`[10, ?, ?, ?, ?]`	1
2	`enqueue(20)`	20	0	0	1	No	`rear = (1) % 5 = 1`, `q[1]=20`	1	`[10, 20, ?, ?, ?]`	2
3	`enqueue(30)`	30	0	1	2	No	`rear = (2) % 5 = 2`, `q[2]=30`	2	`[10, 20, 30, ?, ?]`	3
4	`enqueue(40)`	40	0	2	3	No	`rear = (3) % 5 = 3`, `q[3]=40`	3	`[10, 20, 30, 40, ?]`	4
5	`enqueue(50)`	50	2	3	2	No	`rear = (4) % 5 = 4`, `q[4]=50`	4	`[?, 60, 30, 40, 50]`	3
6	`enqueue(60)`	60	2	4	3	No	`rear = (0) % 5 = 0`, `q[0]=60`	0	`[60, 60, 30, 40, 50]`	4

Note: Steps 5–6 happen after dequeue operations (explained below).

Dequeue operation

Dequeue trace before wrap-around enqueues
Step	Operation	front (before)	size (before)	Queue array (before)	Action	`queue_last` set to	front (after)	size (after)	Queue array (after)
1	`dequeue()`	0	4	`[10, 20, 30, 40, ?]`	`queue_last = q[0]=10`, `front = (0+1)%5 = 1`	10	1	3	`[10, 20, 30, 40, ?]`
2	`dequeue()`	1	3	`[10, 20, 30, 40, ?]`	`queue_last = q[1]=20`, `front = (1+1)%5 = 2`	20	2	2	`[10, 20, 30, 40, ?]`

Visual representation (circular queue)

After all operations:

Array indices:    0      1      2      3      4
Values:          [60,    20,    30,    40,    50]
                   ↑            ↑
                  rear         front
                 (points       (points
                  to 0)         to 2)

Key points

Circular wrap-around: rear goes from 4 to 0 (wrapped) when enqueuing 60.
FIFO behavior maintained: front always points to the next element to dequeue (30).
Efficient space usage: Reuses empty slots after dequeue.
Modulo arithmetic: (rear + 1) % MAX and (front + 1) % MAX enable circular behavior.

Final output

peek: 30

Execution summary

State flow
Step	Action	Queue order (front → rear)
1	enqueue 10,20,30,40	`[10, 20, 30, 40]`
2	dequeue twice	`[30, 40]`
3	enqueue 50,60 (wrap-around)	`[30, 40, 50, 60]`
4	peek	`peek: 30`

4) Trade-offs

Pros — Reuses array slots, O(1) operations, memory predictable.
Cons — Capacity fixed; careful index logic required.

Use dynamic array queue when growth is needed, or linked-list queue for dynamic memory without resizing copies.

Key takeaway

Circular queue is the practical fixed-size array queue. Master wrap-around updates and full/empty checks to avoid index bugs.

Next up: Priority queue · Deque · Queue complexity