.png)
[Follow here] for daily coding insights
DSA SERIES Chapter 7 – Circular Queue
in Python
Concept: Why Circular Queue?
Problem in Linear Queue
In a linear queue using arrays:
-
Front moves forward after each dequeue.
-
Even if elements are removed, those positions cannot be reused.
-
Eventually, queue appears full even when there are empty spaces.
Example:
Positions: [10, 20, 30, 40, 50]
After dequeuing 10, 20, 30 → remaining: [ _ , _ , _ , 40, 50 ]
But rear has reached end → cannot insert more → wasted space.
Solution: Circular Queue
In circular queue:
-
When rear reaches end, it wraps around to index 0.
-
Space is fully utilized.
-
Ideal for:
-
CPU scheduling
-
Call center systems
-
Streaming data
-
Buffer management
-
Operations Explained
| Operation | Meaning |
|---|---|
| enqueue(x) | Insert element |
| dequeue() | Remove element |
| isFull() | Check queue is full |
| isEmpty() | Check queue is empty |
| peek() | Return front element |
| display() | Show all elements |
Python Implementation: Circular Queue Using List
Python Code: Circular Queue
class CircularQueue:
def __init__(self, size):
self.size = size # Maximum size of queue
self.queue = [None] * size # Allocate fixed-size list
self.front = -1 # Points to front element
self.rear = -1 # Points to last element
# Check if queue is full
def isFull(self):
return (self.rear + 1) % self.size == self.front
# Check if queue is empty
def isEmpty(self):
return self.front == -1
# Insert element into circular queue
def enqueue(self, value):
if self.isFull():
print("Queue is FULL! Cannot insert.")
return
# First element insertion
if self.front == -1:
self.front = 0
# Move rear circularly
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = value
print(f"Inserted {value}")
# Delete element from circular queue
def dequeue(self):
if self.isEmpty():
print("Queue is EMPTY! Cannot delete.")
return
removed = self.queue[self.front]
# Only one element left
if self.front == self.rear:
self.front = self.rear = -1
else:
# Move front circularly
self.front = (self.front + 1) % self.size
print(f"Deleted {removed}")
return removed
# Return front element
def peek(self):
if self.isEmpty():
print("Queue is EMPTY!")
return
return self.queue[self.front]
# Display circular queue
def display(self):
if self.isEmpty():
print("Queue is EMPTY!")
return
print("Circular Queue elements:")
i = self.front
while True:
print(self.queue[i], end=" ")
if i == self.rear:
break
i = (i + 1) % self.size
print()
Explanation of Important Parts
✔ Modulus Operation (Circular Movement)
self.rear = (self.rear + 1) % self.size
This ensures the rear value wraps back to 0 when it reaches the last index.
✔ Full Condition
(self.rear + 1) % self.size == self.front
This means the next position of rear is front → no more space.
✔ Empty Condition
self.front == -1
This indicates no elements.
✔ Why front = rear = -1 after deletion?
When the last element is deleted, queue becomes empty again.
Example Execution
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.dequeue()
cq.enqueue(50)
cq.enqueue(60) # Wraps around
cq.display()
Output:
Inserted 10
Inserted 20
Inserted 30
Inserted 40
Deleted 10
Inserted 50
Inserted 60
Circular Queue elements:
20 30 40 50 60
Time & Space Complexity
| Operation | Complexity | Why? |
|---|---|---|
| enqueue | O(1) | Direct index calculation |
| dequeue | O(1) | Direct index calculation |
| peek | O(1) | Single access |
| isFull/isEmpty | O(1) | Logical conditions |
| display | O(n) | Must traverse elements |
Space complexity → O(n) due to fixed array.
ALSO CHECK
ALSO CHECK
Comments
Post a Comment