Circular Queue

A plain array-based queue has a real problem: once REAR reaches the last index, insertion is refused, even if earlier positions were freed up by dequeues and are sitting empty. A circular queue fixes this by treating the array as a ring instead of a straight line, so the position after the last index simply wraps back to the first.

Circular queue vs linear queue

The two use the exact same ENQUEUE/DEQUEUE idea, insert at REAR, remove at FRONT, only the position update differs: REAR = REAR + 1 for a linear queue versus REAR = (REAR + 1) % MAX for a circular one.

The wrap-around idea

The entire idea comes down to one expression: instead of moving to current + 1, move to (current + 1) % MAX.

% is the modulo operator, it gives the remainder of a division, and a remainder is always between 0 and MAX - 1, so it wraps automatically, no manual reset needed.

next = (current + 1) % MAX

For MAX = 5, moving forward from index 4 gives (4 + 1) % 5 = 0, wrapping straight back to the start rather than running off the end of the array.

Worked example

Start with an empty queue of capacity 5. By convention, FRONT = REAR = -1 marks an empty queue, the same idea as a plain queue's FRONT == -1:

Enqueue 10. This is the very first insertion into an empty queue, so both FRONT and REAR move to index 0 together, there's no existing REAR position to advance from yet:

Enqueue 20. Now FRONT stays put and only REAR advances, to index 1:

Enqueue 30, then 40, each one just moving REAR one step forward:

Dequeue 10 and 20, so FRONT moves forward to index 2. Then enqueue 50, so REAR moves forward to index 4, the last one:

Enqueue 60. In a plain array queue this would fail, REAR is already at the last index. In a circular queue, REAR wraps: (4 + 1) % 5 = 0, so 60 goes into index 0, one of the two positions freed earlier by the dequeues:

Enqueue 70. This fills the last free slot at index 1, and REAR catches up right behind FRONT:

The array is now full: every index holds a value, and advancing REAR one more step, (1 + 1) % 5 = 2, would land exactly on FRONT.

Circular queue full condition formula

(REAR + 1) % MAX == FRONT

This says the array is full exactly when advancing REAR by one more step would land on FRONT, meaning there's no free slot left between them going around the ring.

ENQUEUE and DEQUEUE

ENQUEUE(Q, item)
 
If (REAR + 1) % MAX == FRONT
    Print "OVERFLOW"
Else if FRONT == -1
    FRONT = 0
    REAR = 0
    Q[REAR] = item
Else
    REAR = (REAR + 1) % MAX
    Q[REAR] = item

The middle branch handles the first insertion into an empty queue. Since FRONT and REAR are both -1 initially, they are set to 0 to establish the first valid queue position.

DEQUEUE(Q)
 
If FRONT == -1
    return UNDERFLOW
Else
    item = Q[FRONT]
    If FRONT == REAR
        FRONT = -1
        REAR = -1
    Else
        FRONT = (FRONT + 1) % MAX
    return item

The FRONT == REAR check handles the case where the queue contains only one element. After removing it, the queue becomes empty, so both FRONT and REAR are reset to -1.

Overflow and underflow conditions

Together, ENQUEUE and DEQUEUE cover both failure cases for a circular queue:

• Overflow (insertion fails): (REAR + 1) % MAX == FRONT, the ring has no free slot left.
• Underflow (removal fails): FRONT == -1, the queue is empty, there's nothing to remove.

Applications

Circular queues fit naturally wherever data arrives and is consumed continuously, with a fixed amount of buffer space:

• Waiting line at a ticket counter: when one person leaves, the space can be reused by the next person.
• Printer queue: documents wait to be printed one after another, and the same queue space can be reused.
• Game turns: players can take turns repeatedly, after the last player, the turn goes back to the first player.
• Buffering streaming data: audio/video buffers, keyboard input buffers, and network packet queues are commonly circular, since data keeps arriving and being consumed indefinitely, and a fixed-size ring avoids constantly reallocating memory.
• Round-robin CPU scheduling: the operating system gives each running program a short turn to use the CPU, then moves to the next one, cycling back to the first once it reaches the end, the exact same "wrap back to the start" behavior as a circular queue. (You'll study this properly in an Operating Systems course, this is just a preview of where the idea shows up again.)
• Producer-consumer buffering: picture one part of a program constantly adding items to a queue (the producer) while another part removes and processes them (the consumer), possibly at a different speed. A circular queue lets that shared space be reused instead of growing forever. (This is a classic Operating Systems synchronization problem, you'll see it again with more depth there.)

Quick recall

• A circular queue treats the array as a ring: index MAX - 1 is followed by index 0, computed as (current + 1) % MAX.
• This solves the wasted-space problem of a plain array queue, where REAR reaching the last index blocks insertion even if earlier space was freed by dequeues.
• Full condition: (REAR + 1) % MAX == FRONT. Empty condition (common convention): FRONT == -1.
• Wrapping only changes what index REAR or FRONT point to, it never physically moves the existing elements in the array.