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.

Practice

1. What is the main advantage of a circular queue compared to a regular linear queue?

easy

A. It allows storing different data types in the same queue.

B. It efficiently reuses empty space by connecting the end to the start.

C. It automatically sorts elements while enqueuing.

D. It requires shifting elements after every dequeue operation.

Solution

1. Step 1: Understand the structure of a circular queue

   A circular queue connects the last position back to the first, forming a circle.

2. Step 2: Identify the advantage over a linear queue

   This connection allows the queue to reuse spaces freed by dequeued elements without shifting.

3. Final Answer:

   It efficiently reuses empty space by connecting the end to the start. -> Option B

4. Quick Check:

   Circular queue = space reuse [OK]

Hint: Circular queue wraps around to reuse space [OK]

Common Mistakes:

• Thinking it sorts elements automatically
• Believing it stores multiple data types
• Assuming it shifts elements after dequeue

2. Which of the following is the correct way to update the rear pointer in a circular queue after an enqueue operation?

easy

A. rear = (rear + 1) % size

B. rear = rear + 1

C. rear = rear - 1

D. rear = size - rear

Solution

1. Step 1: Recall how circular queue pointers move

   In a circular queue, pointers wrap around using modulo arithmetic to stay within bounds.

2. Step 2: Apply modulo to update rear pointer

   After enqueue, rear moves to (rear + 1) modulo the queue size to wrap if needed.

3. Final Answer:

   rear = (rear + 1) % size -> Option A

4. Quick Check:

   Rear update uses modulo [OK]

Hint: Use modulo (%) to wrap rear pointer [OK]

Common Mistakes:

• Incrementing rear without modulo
• Decrementing rear after enqueue
• Using subtraction instead of modulo

3. Consider a circular queue of size 5 with front = 3 and rear = 1. Which of the following statements is true about the queue state?

medium

A. The queue is empty.

B. The queue is full.

C. The queue has 3 elements.

D. The queue has 4 elements.

Solution

1. Step 1: Understand front and rear positions in circular queue

   Front at 3 and rear at 1 means rear has wrapped around past front.

2. Step 2: Calculate number of elements using formula

   Number of elements = (rear - front + size) % size = (1 - 3 + 5) % 5 = 3 % 5 = 3.

3. Final Answer:

   The queue has 3 elements. -> Option C

4. Quick Check:

   Elements count = 3 [OK]

Hint: Use (rear - front + size) % size to count elements [OK]

Common Mistakes:

• Confusing full and empty conditions
• Ignoring modulo in calculation
• Assuming rear < front means empty

4. Given this code snippet for dequeue in a circular queue, what is the error?

if front == -1:
    print("Queue is empty")
else:
    data = queue[front]
    if front == rear:
        front = rear = -1
    else:
        front = (front + 1) % size

medium

A. The code does not return or use the dequeued data.

B. The front pointer update should use rear instead of front.

C. The condition to check empty queue is incorrect.

D. The rear pointer should be incremented after dequeue.

Solution

1. Step 1: Analyze the dequeue operation steps

   The code checks if queue is empty, retrieves data, updates pointers correctly.

2. Step 2: Identify missing usage of dequeued data

   Though data is assigned, it is neither returned nor used, so the operation loses the dequeued value.

3. Final Answer:

   The code does not return or use the dequeued data. -> Option A

4. Quick Check:

   Dequeue must return data [OK]

Hint: Always return dequeued element [OK]

Common Mistakes:

• Not returning dequeued value
• Incorrect pointer updates
• Incrementing rear on dequeue

5. You have a circular queue of size 6. Initially, front = 0 and rear = 4. You perform two dequeue operations followed by three enqueue operations. What will be the final positions of front and rear?

hard

A. front = 1, rear = 2

B. front = 2, rear = 0

C. front = 0, rear = 5

D. front = 2, rear = 1

Solution

1. Step 1: Update front after two dequeues

   Each dequeue moves front by 1 modulo size: front = (0 + 2) % 6 = 2.

2. Step 2: Update rear after three enqueues

   Each enqueue moves rear by 1 modulo size: rear = (4 + 3) % 6 = 7 % 6 = 1.

3. Final Answer:

   front = 2, rear = 1 -> Option D

4. Quick Check:

   Front and rear updated with modulo [OK]

Hint: Add operations to pointers using modulo size [OK]

Common Mistakes:

• Not using modulo for pointer wrap-around
• Mixing front and rear updates
• Forgetting to update pointers after each operation