Why Every Programmer Needs to Understand Circular Queues

Imagine a highway toll booth system. Cars arrive continuously and form a queue. Each car is served and moves through. After serving a car, the booth does not shut down and refuse new cars just because some positions at the start of the lane are now empty. It keeps accepting new cars from behind while serving from the front.

Now imagine if the toll booth worked like a naive linear queue implemented with an array. Every time a car is served and leaves the front, that position in the lane becomes permanently unusable. After serving 100 cars, 100 positions at the front of the lane are wasted. The system would refuse new cars and report “lane full” even though 100 empty slots exist right there at the beginning of the lane.

This is exactly the problem with the linear array-based queue, and it is exactly why the circular queue was invented.

What is a Circular Queue?

A circular queue (also called a ring buffer) is a linear data structure that follows the FIFO (First In, First Out) principle, where the last position of the array is connected back to the first position, forming a logical circle. Unlike a linear queue, a circular queue reuses the spaces freed by dequeue operations at the front, eliminating memory waste.

Break that definition apart:

• FIFO principle: The element inserted first is the first one to be removed, just like a regular queue

• Last position connected to first: When the rear pointer reaches the end of the array, it wraps back to index 0

• Logical circle: The physical array is linear, but the pointer movement treats it as circular using modulo arithmetic

• Reuses freed spaces: Once front elements are dequeued, those positions become available for new insertions

Visualising the Circular Structure

A circular queue with SIZE = 5, after several enqueue and dequeue operations:

Physical array:   [ -- ] [ 30 ] [ 40 ] [ 50 ] [ -- ]
Index:               0      1      2      3      4
                             ^             ^
                          FRONT=1       REAR=3
(positions 0 and 4 are free, previously dequeued)

Next enqueue goes to:    (3+1) % 5 = 4  → position 4
After that:              (4+1) % 5 = 0  → position 0 (WRAP AROUND!)

The array is physically linear but logically circular:
     Index 0 → Index 1 → Index 2 → Index 3 → Index 4
        ^                                          |
        |__________________________________________| (wrap)

How a Circular Queue Works Under the Hood

Two Pointers on a Fixed Array

A circular queue maintains two index pointers:

• FRONT: Index of the element that will be removed next (the oldest element)

• REAR: Index of the most recently added element

The Modulo Formula: The Heart of Circular Queue

The entire circular behaviour is driven by one formula applied to both pointers:

Next REAR position:  REAR = (REAR + 1) % SIZE
Next FRONT position: FRONT = (FRONT + 1) % SIZE

When REAR equals SIZE - 1 (the last index) and we increment it: (SIZE - 1 + 1) % SIZE = SIZE % SIZE = 0 The pointer wraps back to index 0, making the physically linear array behave as a circle.

SIZE = 5

# Normal increment:
REAR = 2
REAR = (2 + 1) % 5 = 3   # Normal step forward

# Wrap-around increment:
REAR = 4
REAR = (4 + 1) % 5 = 0   # Wraps back to beginning!

The isFull Condition: The Trickiest Part

Detecting when a circular queue is full requires special care. There are two possible full conditions:

Case 1: FRONT is at index 0 and REAR is at the last index (SIZE - 1).

[ 10 ] [ 20 ] [ 30 ] [ 40 ] [ 50 ]
   0      1      2      3      4
FRONT = 0, REAR = 4
FULL: (FRONT == 0 && REAR == SIZE - 1)

Case 2: REAR + 1 equals FRONT (REAR has wrapped around and caught up to FRONT).

[ 50 ] [ 10 ] [ 20 ] [ 30 ] [ 40 ]
   0      1      2      3      4
FRONT = 1, REAR = 0
FULL: (REAR + 1) % SIZE == FRONT  →  (0 + 1) % 5 = 1 == FRONT (1)

Both cases captured by one combined formula:

isFull: (FRONT == 0 && REAR == SIZE - 1) OR (REAR + 1 == FRONT)

Or using size counter (simpler): isFull: size == capacity

The Classic Bug: Using only REAR == SIZE - 1 as the full condition only catches Case 1. This causes the queue to report full even when there is free space after wrap-around. Always use the full modulo-based check or a separate size counter.

The Space Waste Problem: Why Circular Queue Exists

# Linear Queue with SIZE = 5
# After enqueuing 5 elements and then dequeuing 3:

# State:
# [ -- ] [ -- ] [ -- ] [ 40 ] [ 50 ]
#    0      1      2      3      4
# FRONT = 3, REAR = 4
# Positions 0, 1, 2 are FREE but UNUSABLE

# Try to enqueue 60:
# rear = rear + 1 = 5
# 5 >= SIZE (5)  →  Queue reports FULL!
# Even though 3 out of 5 positions are empty!

Visual comparison:

Linear Queue after 3 dequeues:
[ -- ] [ -- ] [ -- ] [ 40 ] [ 50 ]
  FREE  FREE  FREE  USED   USED
Reports "FULL" even though only 2 of 5 slots are occupied!

Circular Queue same state:
[ 60 ] [ -- ] [ -- ] [ 40 ] [ 50 ]  ← 60 wraps to position 0
  USED  FREE  FREE  USED   USED
Only 3 of 5 slots occupied. 60 inserted successfully.

This is why circular queues exist. The circular wrap eliminates the logical overflow that arises when the rear pointer reaches the end of a linear array even though dequeued positions at the front are available.

Circular Queue Terminology

Core Operations

Every circular queue supports six core operations. All primary operations are O(1).

Operations Summary Table

Enqueue: Insert at the Rear

The enqueue operation adds a new element at the rear of the circular queue.

Algorithm

enqueue(element):
  1. Check if queue is full → print "Overflow" and stop
  2. If queue is empty (FRONT == -1): set FRONT = 0, REAR = 0
  3. Else: REAR = (REAR + 1) % SIZE   ← circular increment
  4. Place element at queue[REAR]
  5. Increment size counter

Enqueue Trace

Queue: [10, 20, 30, --, --], FRONT=0, REAR=2, SIZE=5

enqueue(40):
  REAR = (2 + 1) % 5 = 3
  queue[3] = 40
  Result: [10, 20, 30, 40, --], FRONT=0, REAR=3

enqueue(50):
  REAR = (3 + 1) % 5 = 4
  queue[4] = 50
  Result: [10, 20, 30, 40, 50], FRONT=0, REAR=4

After dequeue() removes 10 and 20: FRONT=2, REAR=4

enqueue(60):  ← WRAP-AROUND case!
  REAR = (4 + 1) % 5 = 0    ← wraps from 4 to 0
  queue[0] = 60
  Result: [60, --, 30, 40, 50], FRONT=2, REAR=0

class CircularQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.capacity = capacity
        self.front = -1
        self.rear = -1
        self.size = 0

    def is_empty(self): return self.front == -1
    def is_full(self):  return self.size == self.capacity

    def enqueue(self, element):
        if self.is_full():
            print("Queue Overflow: circular queue is full")
            return False

        if self.is_empty():
            self.front = 0
            self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.capacity   # Circular increment

        self.queue[self.rear] = element
        self.size += 1
        print(f"Enqueued:{element}")
        return True

cq = CircularQueue(5)
cq.enqueue(10)   # Enqueued: 10
cq.enqueue(20)   # Enqueued: 20
cq.enqueue(30)   # Enqueued: 30

Dequeue: Delete from the Front

The dequeue operation removes the element at the front of the circular queue and advances the FRONT pointer.

Algorithm

dequeue():
  1. Check if queue is empty (FRONT == -1) → print "Underflow" and stop
  2. Store value at queue[FRONT]
  3. If only one element left (FRONT == REAR):
       set FRONT = -1, REAR = -1 (queue becomes empty)
  4. Else:
       FRONT = (FRONT + 1) % SIZE   ← circular increment
  5. Decrement size
  6. Return stored value

Dequeue Trace

Queue: [10, 20, 30, 40, 50], FRONT=0, REAR=4, size=5

dequeue():
  value = queue[0] = 10
  FRONT (0) != REAR (4): more elements remain
  FRONT = (0 + 1) % 5 = 1
  Returns: 10

dequeue() again:
  value = queue[1] = 20
  FRONT = (1 + 1) % 5 = 2
  Returns: 20

Queue state: [--, --, 30, 40, 50], FRONT=2, REAR=4

def dequeue(self):
    if self.is_empty():
        print("Queue Underflow: circular queue is empty")
        return None

    value = self.queue[self.front]

    if self.front == self.rear:    # Only one element left
        self.front = -1
        self.rear = -1
    else:
        self.front = (self.front + 1) % self.capacity   # Circular increment

    self.size -= 1
    return value

cq = CircularQueue(5)
for val in [10, 20, 30, 40, 50]:
    cq.enqueue(val)

print(cq.dequeue())   # 10
print(cq.dequeue())   # 20

cq.enqueue(60)        # Wraps to position 0
cq.enqueue(70)        # Goes to position 1

Peek / Front

Returns the front element without removing it or changing any pointers.

def peek(self):
    if self.is_empty():
        print("Queue is empty")
        return None
    return self.queue[self.front]

cq = CircularQueue(5)
for val in [10, 20, 30]:
    cq.enqueue(val)

print(cq.peek())     # 10
print(cq.peek())     # 10 (still there, peek does not remove)
print(cq.dequeue())  # 10 (now actually removed)
print(cq.peek())     # 20 (new front)

Rear

Returns the most recently enqueued element without removing it.

def get_rear(self):
    if self.is_empty():
        print("Queue is empty")
        return None
    return self.queue[self.rear]

isEmpty and isFull

isEmpty

def is_empty(self): return self.front == -1

isFull (Two Approaches)

# Approach 1: Use a separate size counter (recommended, simpler)
def is_full(self): return self.size == self.capacity

# Approach 2: Pointer arithmetic only (no extra variable)
def is_full_pointers_only(self):
    return (self.front == 0 and self.rear == self.capacity - 1) or \
           (self.front == self.rear + 1)

Complete Implementation Using Arrays

class CircularQueue:
    def __init__(self, capacity=100):
        self.queue = [None] * capacity
        self.capacity = capacity
        self.front = -1
        self.rear = -1
        self.size = 0

    def is_empty(self): return self.front == -1
    def is_full(self):  return self.size == self.capacity
    def get_size(self): return self.size

    def enqueue(self, element):
        if self.is_full():
            print("Queue Overflow"); return False
        if self.is_empty():
            self.front = 0; self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = element
        self.size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            print("Queue Underflow"); return None
        value = self.queue[self.front]
        if self.front == self.rear:
            self.front = -1; self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return value

    def peek(self):     return None if self.is_empty() else self.queue[self.front]
    def get_rear(self): return None if self.is_empty() else self.queue[self.rear]

    def display(self):
        if self.is_empty():
            print("[ Empty Queue ]"); return
        print("Queue: [ ", end="")
        i = self.front
        for _ in range(self.size):
            print(self.queue[i], end=" ")
            i = (i + 1) % self.capacity
        print(f"] FRONT={self.front} REAR={self.rear} SIZE={self.size}")

# Full demo
cq = CircularQueue(5)
for val in [1, 2, 3, 4, 5]:
    cq.enqueue(val)

print(f"Is full:{cq.is_full()}")        # True
cq.display()                              # Queue: [ 1 2 3 4 5 ] FRONT=0 REAR=4
cq.enqueue(6)                             # Queue Overflow
print(f"Dequeued:{cq.dequeue()}")        # 1
print(f"Dequeued:{cq.dequeue()}")        # 2
cq.display()                              # Queue: [ 3 4 5 ] FRONT=2 REAR=4
cq.enqueue(6)                             # Wraps to index 0
cq.enqueue(7)                             # Goes to index 1
cq.display()                              # Queue: [ 3 4 5 6 7 ] FRONT=2 REAR=1
print(f"Peek:{cq.peek()}")            # 3
print(f"Rear:{cq.get_rear()}")        # 7

Complete Implementation Using Linked Lists

A linked-list-based circular queue avoids the fixed-size limitation. The last node’s nextalways points back to the first node.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularQueueLinkedList:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

    def is_empty(self): return self.front is None

    def enqueue(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.front = new_node
            self.rear = new_node
            new_node.next = self.front   # Points to itself: circular
        else:
            new_node.next = self.front   # New node → front
            self.rear.next = new_node    # Old rear → new node
            self.rear = new_node         # Update rear
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty"); return None

        value = self.front.data
        if self.front == self.rear:   # Only one node
            self.front = None
            self.rear = None
        else:
            self.front = self.front.next
            self.rear.next = self.front   # Maintain circular link
        self.size -= 1
        return value

    def peek(self):
        return None if self.is_empty() else self.front.data

    def display(self):
        if self.is_empty(): print("Empty"); return
        current = self.front
        print("Queue: ", end="")
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.front: break
        print("(back to front)")

cq_ll = CircularQueueLinkedList()
cq_ll.enqueue(14); cq_ll.enqueue(22); cq_ll.enqueue(6); cq_ll.enqueue(20)
cq_ll.display()              # Queue: 14 -> 22 -> 6 -> 20 -> (back to front)
print(cq_ll.dequeue())       # 14
print(cq_ll.dequeue())       # 22
cq_ll.display()              # Queue: 6 -> 20 -> (back to front)
cq_ll.enqueue(9)
print(f"Rear:{cq_ll.rear.data}")    # 9
print(f"Front:{cq_ll.front.data}")  # 6

C (Linked List Implementation):

#include<stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* link;
};

struct Node* front = NULL;
struct Node* rear = NULL;

bool is_empty_ll() { return front == NULL; }

void enqueue_ll(int value) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->link = NULL;
    if (is_empty_ll()) {
        front = newNode;
    } else {
        rear->link = newNode;
    }
    rear = newNode;
    rear->link = front;   // Maintain circular link: rear always points to front
}

int dequeue_ll() {
    if (is_empty_ll()) { printf("Queue is empty\n"); return -1; }
    int value;
    struct Node* temp = front;
    value = temp->data;
    if (front == rear) {
        front = rear = NULL;
    } else {
        front = front->link;
        rear->link = front;   // Keep circular
    }
    free(temp);
    return value;
}

void display_ll() {
    if (is_empty_ll()) { printf("Queue is empty\n"); return; }
    struct Node* temp = front;
    printf("Queue: ");
    do {
        printf("%d -> ", temp->data);
        temp = temp->link;
    } while (temp != front);
    printf("(front)\n");
}

int main() {
    enqueue_ll(14); enqueue_ll(22); enqueue_ll(6);
    printf("Initial: "); display_ll();
    printf("Deleted:%d\n", dequeue_ll());
    printf("After: "); display_ll();
    return 0;
}

Complexity Analysis

Time Complexity

Space Complexity

The O(1) Guarantee: Every primary operation on a circular queue runs in O(1) time. This guaranteed constant-time performance is critical for real-time systems where each enqueue or dequeue must complete in a predictable, bounded amount of time regardless of how many elements are in the queue.

Circular Queue vs Linear Queue vs Deque

Circular Queue Across Languages

Python collections.deque(maxlen=n) as a Circular Buffer

from collections import deque

# maxlen creates a bounded deque that automatically drops oldest items when full
circular_buffer = deque(maxlen=5)

for i in range(1, 6):
    circular_buffer.append(i)

print(circular_buffer)   # deque([1, 2, 3, 4, 5])

circular_buffer.append(6)   # 1 is automatically dropped!
print(circular_buffer)   # deque([2, 3, 4, 5, 6])

circular_buffer.append(7)   # 2 is automatically dropped!
print(circular_buffer)   # deque([3, 4, 5, 6, 7])

# Dequeue from front
print(circular_buffer.popleft())   # 3
print(circular_buffer[0])          # 4 (peek front)
print(circular_buffer[-1])         # 7 (peek rear)

Real-World Applications

Circular queues power systems that continuously process data streams within a fixed memory budget.

1. Audio and Video Buffering

When you stream a video, audio/video packets arrive from the network and are stored in a circular buffer. The decoder reads from the front while new data arrives at the rear. The buffer circulates continuously without ever running out.

class AudioBuffer:
    def __init__(self, buffer_size):
        self.buffer = CircularQueue(buffer_size)

    def receive_packet(self, packet_id):
        """Network thread adds incoming audio packets."""
        if self.buffer.is_full():
            print(f"Buffer full: dropping oldest packet")
            self.buffer.dequeue()   # Drop oldest for new data
        self.buffer.enqueue(packet_id)
        print(f"Buffered:{packet_id}")

    def play_next(self):
        """Audio output thread reads at a steady rate."""
        if self.buffer.is_empty():
            print("Buffer empty: audio stutter!")
            return None
        packet = self.buffer.dequeue()
        print(f"Playing:{packet}")
        return packet

audio = AudioBuffer(buffer_size=5)
for i in range(1, 6):
    audio.receive_packet(f"audio_{i}")

audio.play_next()   # Playing: audio_1
audio.play_next()   # Playing: audio_2
audio.receive_packet("audio_6")   # Fits now: space freed by playback

2. CPU Round-Robin Process Scheduler

In round-robin CPU scheduling, each process gets an equal time slice. After the last process runs, the scheduler returns to the first process.

class RoundRobinScheduler:
    def __init__(self, time_slice):
        self.ready_queue = CircularQueue(20)
        self.time_slice = time_slice

    def add_process(self, name, burst_time):
        self.ready_queue.enqueue({"name": name, "remaining": burst_time})
        print(f"Process{name} added")

    def run_one_cycle(self):
        if self.ready_queue.is_empty():
            print("No processes"); return

        process = self.ready_queue.dequeue()
        process["remaining"] -= self.time_slice
        remaining = max(0, process["remaining"])
        print(f"Running:{process['name']} | Remaining:{remaining}ms")

        if process["remaining"] > 0:
            self.ready_queue.enqueue(process)   # Re-add to rear if not done
        else:
            print(f"Process{process['name']} COMPLETED")

scheduler = RoundRobinScheduler(time_slice=10)
scheduler.add_process("Chrome", 35)
scheduler.add_process("Spotify", 20)
scheduler.add_process("VSCode", 15)

for _ in range(7):
    scheduler.run_one_cycle()
# Chrome(25ms), Spotify(10ms), VSCode(5ms), Chrome(15ms), Spotify DONE, VSCode DONE, Chrome(5ms)

Advantages and Disadvantages

Advantages of Circular Queues

• Solves the linear queue memory waste problem: The defining advantage. A circular queue reuses every dequeued position for future insertions. The same 5-position array can serve unlimited enqueue/dequeue cycles without ever falsely reporting “full.” This makes circular queues ideal for continuous data streams in fixed memory

• O(1) guaranteed for all primary operations: Every enqueue, dequeue, peek, and isEmpty check executes in constant time with no exceptions. This predictable constant-time performance is critical for real-time systems where timing guarantees are required

• Maximum utilisation of allocated memory: The capacity is set once and used continuously and completely. Unlike a linear queue that exhausts its array from one direction, a circular queue keeps 100% of its allocated capacity usable as long as it does not exceed capacity simultaneously held elements

• Simpler than dynamic resizing: Alternatives to the linear queue overflow problem include resizing (O(n) copy), shifting (O(n) work), or growing the array. Circular queues solve the same problem in O(1) using only the modulo formula

• Natural model for cyclic processes: Round-robin scheduling, audio buffers, traffic signal control, and ring topology networks are all inherently cyclic. A circular queue models these processes directly without any adaptation

Disadvantages of Circular Queues

• Fixed size limitation: The capacity must be set at creation and cannot change. If demand exceeds fixed capacity, elements must be dropped or the structure replaced with a dynamic alternative

• Complex isFull condition: Determining fullness requires checking two separate conditions without a size counter. Using only REAR == SIZE - 1 is a common bug that misses the wrap-around full case

• More complex implementation than linear queue: The modulo arithmetic, two-case full condition, and special empty-to-non-empty transitions make circular queues more complex to implement and debug correctly

• No random access: Only the front element is directly accessible. Accessing any other element requires dequeuing all elements ahead of it, destroying them in the process

• Debugging difficulty: When REAR < FRONT (after wrap-around), the logical element order does not match the physical array layout. Printing the raw array does not show elements in queue order, making print-based debugging confusing

Conclusion

The circular queue solves one of the most fundamental inefficiencies in data structures with a single elegant idea and a single formula. Here is a recap of everything covered:

• A circular queue connects the last array position back to the first using modulo arithmetic: (index + 1) % SIZE. This wrap-around formula is the entire mechanism that separates a circular queue from a linear one

• The space waste problem of linear queues occurs when REAR reaches SIZE-1 and the queue reports full even though dequeued positions at the front are empty. Circular queues solve this by wrapping REAR back to index 0, reusing those freed positions

• Two pointers, FRONT and REAR, track the oldest and newest elements. Both move forward with (pointer + 1) % SIZE and wrap to 0 when they exceed the last index

• The isFull condition has two cases: linear-full (FRONT == 0 AND REAR == SIZE-1) and wrap-full ((REAR+1) % SIZE == FRONT). Using a separate size counter simplifies this to size == capacity

• All six core operations: enqueue, dequeue, peek, rear, isEmpty, isFull run in O(1) time. This guaranteed constant performance is why circular queues are used in real-time systems

• Circular queues are implemented either with a fixed-size array (simpler, cache-friendly) or a linked list (dynamic size, pointer overhead per node)

• Key real-world applications include audio/video streaming buffers, CPU round-robin schedulers, traffic signal controllers, keyboard input buffers, and network packet buffers in routers

• The most common implementation mistakes are: using only REAR == SIZE - 1 as the full check (misses the wrap-around full case), and not resetting both FRONT and REAR to -1 when the last element is dequeued

​

The circular queue teaches a fundamental principle of data structure design: often the most powerful improvements come not from building something entirely new, but from adding one connection to an existing structure.

The linear queue already had everything needed: two pointers, a fixed array, FIFO ordering. The circular queue adds one thing: the connection from the last position back to the first, captured entirely in the formula (index + 1) % SIZE.

That one change solves the memory waste problem completely and enables continuous, efficient operation on fixed memory resources.