Circular queue in Data Structures Theory - Full Explanation

Introduction

Imagine you have a line of people waiting for a service, but the space to hold them is limited. How can you efficiently reuse the empty spots when people leave from the front? This problem is solved by the circular queue, which helps manage limited space by connecting the end back to the beginning.

Explanation

Basic Structure

A circular queue is like a normal queue but the last position connects back to the first, forming a circle. This means when the queue reaches the end of the storage, it wraps around to use any free space at the start. It uses two pointers: front (where elements are removed) and rear (where elements are added).

The circular queue reuses empty space by connecting the end back to the start.

Enqueue Operation

To add an element, the rear pointer moves forward to the next position. If the rear reaches the end of the storage, it wraps around to the beginning if space is free. If the queue is full, no new elements can be added until some are removed.

Enqueue moves rear forward and wraps around to reuse space.

Dequeue Operation

To remove an element, the front pointer moves forward to the next position. Like rear, if front reaches the end, it wraps around to the start. This operation frees up space for new elements to be added later.

Dequeue moves front forward and wraps around to free space.

Full and Empty Conditions

The queue is empty when front and rear pointers are equal and no elements are present. It is full when moving rear forward would make it equal to front, meaning no space is left. This condition helps avoid confusion between full and empty states.

Full and empty states are detected by comparing front and rear positions carefully.

Real World Analogy

Imagine a circular table with chairs around it. People sit in the chairs in order, and when someone leaves, the next person can take that empty chair. The seating goes around the table continuously without needing extra chairs.

Basic Structure → The circular table where the last chair connects back to the first

Enqueue Operation → A new person sitting in the next available chair moving clockwise

Dequeue Operation → A person leaving their chair, freeing it for the next person

Full and Empty Conditions → All chairs occupied means full; all chairs empty means empty

Diagram

Diagram

┌─────────────┐
│   Circular  │
│    Queue    │
└─────────────┘

[Front] → [ ] → [ ] → [Rear]
   ↑                        ↓
   └────────────←───────────┘

This diagram shows a circular queue where front and rear pointers move around a circular buffer.

Key Facts

Circular queue → A queue where the end connects back to the start to reuse space.

Front pointer → Marks the position of the next element to be removed.

Rear pointer → Marks the position where the next element will be added.

Queue full condition → Occurs when moving rear forward would make it equal to front.

Queue empty condition → Occurs when front and rear pointers are equal and no elements exist.

Code Example

Data Structures Theory

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

    def is_full(self):
        return (self.rear + 1) % self.size == self.front

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

    def enqueue(self, value):
        if self.is_full():
            print("Queue is full")
            return
        if self.is_empty():
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = value

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty")
            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.size
        return value

cq = CircularQueue(3)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)  # Should print "Queue is full"
print(cq.dequeue())  # 10
cq.enqueue(40)
print(cq.dequeue())  # 20
print(cq.dequeue())  # 30
print(cq.dequeue())  # 40
print(cq.dequeue())  # Should print "Queue is empty"

Common Confusions

Believing a circular queue is just a normal queue with a fixed size.

Believing a circular queue is just a normal queue with a fixed size. A circular queue reuses empty space by wrapping rear and front pointers around, unlike a normal fixed queue that cannot reuse freed space.

Thinking front always stays at zero and only rear moves.

Thinking front always stays at zero and only rear moves. Both front and rear pointers move forward and wrap around to manage the queue correctly.

Assuming full and empty conditions are the same when front equals rear.

Assuming full and empty conditions are the same when front equals rear. When front equals rear, the queue can be either full or empty; additional logic is needed to distinguish these states.

Summary

A circular queue efficiently uses limited space by connecting the end back to the start.

Front and rear pointers move forward and wrap around to manage adding and removing elements.

Special conditions detect when the queue is full or empty to avoid confusion.