What is a Circular Queue and How is it Implemented?
💡 Concept Name
Circular Queue – A linear data structure that connects the end of the queue back to the front, forming a logical circle and allowing efficient reuse of array space for FIFO operations.
📘 Quick Intro
A circular queue solves the problem of wasted space in traditional arrays after dequeue operations. By treating the storage as circular, elements can wrap around, ensuring no slot is left idle unless the queue is truly full.
🧠 Analogy / Short Story
Think of a circular queue like a carousel ride at an amusement park. When a seat at the front is vacated, the next rider can use it as the queue wraps around—no seat is ever left empty if someone is waiting, making full use of all seats.
🔧 Technical Explanation
- Uses a fixed-size array and two pointers:
frontandrear. - Enqueue operation:
rear = (rear + 1) % size. - Dequeue operation:
front = (front + 1) % size. - The queue is full when
(rear + 1) % size == front. - The queue is empty when
front == rear. - Prevents wasted space and enables O(1) enqueue and dequeue operations.
🎯 Purpose & Use Case
- ✅ Used in CPU task scheduling (round-robin style).
- ✅ Buffering streaming data (like audio or video).
- ✅ Printers and hardware device queues.
- ✅ Handling fixed-size resource pools in real-time systems.
💻 Real Code Example
public class CircularQueue
{
private int[] items;
private int size;
private int front;
private int rear;
public CircularQueue(int capacity)
{
size = capacity + 1; // Extra slot to distinguish full from empty
items = new int[size];
front = 0;
rear = 0;
}
public bool IsEmpty() => front == rear;
public bool IsFull() => (rear + 1) % size == front;
public void Enqueue(int value)
{
if (IsFull())
{
Console.WriteLine("Queue is full");
return;
}
items[rear] = value;
rear = (rear + 1) % size;
}
public int Dequeue()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty");
return -1;
}
int value = items[front];
front = (front + 1) % size;
return value;
}
}
// Usage
var queue = new CircularQueue(3);
queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(30);
Console.WriteLine(queue.Dequeue()); // 10
queue.Enqueue(40);
❓ Interview Q&A
Q1: What is the main benefit of a circular queue?
A: It efficiently reuses space and avoids wasted slots after dequeue operations.
Q2: How do you check if a circular queue is full?
A: (rear + 1) % size == front
Q3: Is a circular queue always fixed size?
A: Usually yes, but dynamic resizing is possible with extra logic.
Q4: Name an OS scheduling algorithm that uses circular queues.
A: Round-robin scheduling.
Q5: What is the time complexity of enqueue/dequeue?
A: O(1).
Q6: Why add one extra space in a circular queue array?
A: To distinguish between full and empty states.
Q7: Can a circular queue be implemented using linked lists?
A: Yes, for dynamic sizes and flexibility.
Q8: What happens if you enqueue into a full circular queue?
A: The operation fails, and no new element is added.
Q9: What is a real-world analogy for circular queues?
A: People sitting around a round table, reusing seats as soon as they become empty.
Q10: Which pointer moves on dequeue?
A: The front pointer.
📝 MCQs
Q1. Which structure avoids wasted space in queue operations?
- Stack
- Circular Queue
- Priority Queue
- Heap
Q2. What does rear = (rear + 1) % size achieve?
- Inserts data
- Deletes data
- Wraps index to start
- Sorts data
Q3. How to check if a circular queue is full?
- rear == front
- size == rear
- (rear + 1) % size == front
- rear == size
Q4. Which scenario is best for circular queue?
- Sorting
- Searching
- Round-robin scheduling
- Pathfinding
Q5. Is a circular queue FIFO?
- Yes
- No
- Only in arrays
- Only when sorted
Q6. What happens when rear exceeds size?
- Error
- Stops
- It wraps to 0
- Grows in size
Q7. Which data structure uses modulo arithmetic?
- Stack
- Queue
- Circular Queue
- Graph
Q8. Can a circular queue be dynamic?
- No
- Yes with resizing
- Only if empty
- Only in linked list
Q9. Time complexity of Enqueue in circular queue?
- O(n)
- O(log n)
- O(1)
- O(n^2)
Q10. Time complexity of Dequeue in circular queue?
- O(n)
- O(1)
- O(n log n)
- O(n^2)
💡 Bonus Insight
Always allocate one extra array slot when implementing circular queues to tell full from empty. For more flexibility, consider a linked list version for applications where the queue size isn't fixed in advance.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!