Implementation of Circular Queue in Python
Implementation of Circular Queue
Learn how to implement a Circular Queue in Python. A Circular Queue is a data structure that extends the functionality of a traditional queue by allowing elements to wrap around, creating a circular buffer.
In this page, we delve into the intricacies of circular queues, unraveling their characteristics, applications, implementation, and advantages over their linear counterparts.
Understanding Circular Queues
Circular queues, often referred to as ring buffers, present a dynamic data structure that fosters efficient data handling in scenarios demanding a fixed-size buffer. The cyclic nature of circular queues eliminates the wastage of memory space and enables seamless data circulation. To visualize this, consider a circle where the end points are connected, forming a loop. This loop structure embodies the essence of circular queues.
Implementing Circular Queues: A Step-By-Step Guide
Initialization:
- To create a circular queue, allocate memory for the queue and initialize front and rear pointers to -1, indicating an empty queue.
Enqueue Operation:
When adding elements to the circular queue, follow these steps:
- Check for queue overflow by comparing (rear + 1) % capacity with the front pointer. If they are equal, the queue is full.
- Increment the rear pointer using (rear + 1) % capacity.
Store the new element in the position pointed to by the rear.
Dequeue Operation:
Removing elements from the circular queue involves the following steps:
- Check for queue underflow by comparing the front and rear pointers. If they are equal, the queue is empty.
- Increment the front pointer using (front + 1) % capacity.
- The element at the position pointed to by the front is now dequeued.
Coding Example: Circular Queue in Python
class CircularQueue:
def __init__(self, size):
self.size = size
self.queue = [None] * size
self.front = self.rear = -1
def enqueue(self, item):
if (self.rear + 1) % self.size == self.front:
print("Queue is full")
elif self.front == -1: # First element to be inserted
self.front = self.rear = 0
self.queue[self.rear] = item
else:
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = item
def dequeue(self):
if self.front == -1:
print("Queue is empty")
elif self.front == self.rear: # Only one element was in queue
print("Deleted element:", self.queue[self.front])
self.front = self.rear = -1
else:
print("Deleted element:", self.queue[self.front])
self.front = (self.front + 1) % self.size
def display(self):
if self.front == -1:
print("Queue is empty")
else:
i = self.front
print("Queue elements:", end=" ")
while True:
print(self.queue[i], end=" ")
if i == self.rear:
break
i = (i + 1) % self.size
print()
# Test the CircularQueue
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50) # Should be full now
cq.display()
cq.dequeue()
cq.dequeue()
cq.display()
cq.enqueue(60)
cq.enqueue(70)
cq.display()
Output:
Queue is full Queue elements: 10 20 30 40 50 Deleted element: 10 Deleted element: 20 Queue elements: 30 40 50 Queue elements: 30 40 50 60 70
Explanation:
- Initializes a fixed-size list to store elements.
- front and rear track the queue’s start and end.
- Enqueue uses (rear + 1) % size to insert circularly.
- Dequeue updates front similarly or resets if queue becomes empty.
- Prevents overflow using circular logic (wrap-around).
- Display prints from front to rear with modular traversal.
- Efficient reuse of space unlike a linear queue.
Time & Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Enqueue | O(1) | O(n) |
| Dequeue | O(1) | O(n) |
| Display | O(n) | O(n) |
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
How to Implement a Circular Queue?
A circular queue can be implemented using two data structures :
- Array
- Linked List
Implementation of Circular Queue using Array
- Initialize the circular queue with a given capacity and create an array to hold queue elements.
- Initialize front and rear pointers to -1.
- To enqueue an item:
Check if the queue is full by comparing (rear + 1) % capacity with front.
If the queue is not full, check if it’s empty. If it is, set front and rear to 0 and add the item to the queue.
Otherwise, update rear to the next position and add the item. - To dequeue an item:
Check if the queue is empty by checking if front is -1.
If there’s only one element, set front and rear to -1.
Otherwise, set the element at front to None and update front to the next position.
To display the elements in the queue: - Check if the queue is empty.
If rear is greater than or equal to front, loop through the elements from front to rear and print them.
If not, loop through the elements from front to the end of the array and then from the start of the array to rear.
class CircularQueue:
def __init__(self, size):
# Initialize the circular queue
self.size = size
self.queue = [None] * size
self.front = -1
self.rear = -1
def enqueue(self, item):
# Check for overflow
if (self.rear + 1) % self.size == self.front:
print("Queue is full")
return
# If queue is empty
elif self.front == -1:
self.front = 0
self.rear = 0
else:
# Move rear to next position
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = item
print(f"Inserted {item}")
def dequeue(self):
# Check for underflow
if self.front == -1:
print("Queue is empty")
return
removed_item = self.queue[self.front]
# If only one element was present
if self.front == self.rear:
self.front = -1
self.rear = -1
else:
# Move front to next position
self.front = (self.front + 1) % self.size
print(f"Removed {removed_item}")
def display(self):
if self.front == -1:
print("Queue is empty")
return
print("Queue elements:")
i = self.front
while True:
print(self.queue[i], end=" ")
if i == self.rear:
break
i = (i + 1) % self.size
print()
# ------------------------
# Driver Code / Test Demo
# ------------------------
if __name__ == "__main__":
cq = CircularQueue(5)
# Insert elements
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50) # This should show "Queue is full"
# Display queue
cq.display()
# Remove 2 elements
cq.dequeue()
cq.dequeue()
# Insert more elements
cq.enqueue(60)
cq.enqueue(70)
# Final state
cq.display()
Output:
Inserted 10 Inserted 20 Inserted 30 Inserted 40 Queue is full Queue elements: 10 20 30 40 Removed 10 Removed 20 Inserted 60 Inserted 70 Queue elements: 30 40 60 70
Explanation:
- The queue is initialized with a fixed size and all values are set to None.
- enqueue adds elements circularly using modulo: (rear + 1) % size.
- If the queue becomes full, it prevents overflow.
- dequeue removes the element from front and shifts front circularly.
- When front == rear, after removal, the queue becomes empty.
- display() prints the elements from front to rear with wrap-around logic.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Enqueue | O(1) | O(n) |
| Dequeue | O(1) | O(n) |
| Display | O(n) | O(n) |
Implementation of Circular Queue using Linked List :
- Define a Node class with a data attribute and a next reference to the next node.
- Initialize the CircularQueue class with front and rear pointers set to None.
- To enqueue an item:
Create a new node with the given data.
If the queue is empty, set both front and rear to the new node, and make rear point to front.
Otherwise, make the current rear node point to the new node, update rear to the new node, and make rear point to front. - To dequeue an item:
If the queue is empty, print an error message.
If there’s only one element, set both front and rear to None.
Otherwise, move front to the next node and update rear to point to the new front node. - To display the elements in the queue:
Traverse through the circular linked list starting from front and print the data of each node until you reach the front node again.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularQueue:
def __init__(self):
self.rear = None
def enqueue(self, value):
new_node = Node(value)
if self.rear is None:
self.rear = new_node
self.rear.next = self.rear
else:
new_node.next = self.rear.next
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.rear is None:
print("Queue is empty")
return
front = self.rear.next
if self.rear == front:
print(f"Dequeued: {front.data}")
self.rear = None
else:
print(f"Dequeued: {front.data}")
self.rear.next = front.next
def display(self):
if self.rear is None:
print("Queue is empty")
return
current = self.rear.next
print("Queue elements:", end=" ")
while True:
print(current.data, end=" ")
current = current.next
if current == self.rear.next:
break
print()
# Test the Circular Queue
cq = CircularQueue()
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.display()
cq.dequeue()
cq.display()
cq.enqueue(40)
cq.display()
Output:
Queue elements: 10 20 30 Dequeued: 10 Queue elements: 20 30 Queue elements: 20 30 40
Explanation:
- Node Structure: Each node stores a data value and a next pointer to the next node.
- Queue Rear Pointer: Only the rear node is maintained to track the circular queue.
- Enqueue Operation:
- If the queue is empty, the new node points to itself.
- Otherwise, insert the new node after rear and update rear.
- Dequeue Operation:
- If there is only one node, deleting it sets rear to None.
- Otherwise, update rear.next to remove the front node.
- Display:
- Traverse the circular list starting from rear.next and print each element.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Enqueue | O(1) | O(1) |
| Dequeue | O(1) | O(1) |
| Display | O(n) | O(1) |
| Total Space (for n elements) | — | O(n) |
Benefits of Circular Queues
Circular queues bring forth a plethora of benefits that underscore their significance in the world of data structures:
- Optimized Memory Utilization: Unlike traditional linear queues, circular queues ensure optimal usage of memory. They prevent fragmentation and efficiently manage space allocation.
- Efficient Data Handling: Circular queues excel in scenarios where data needs to be cycled and overwritten in a systematic manner. They find applications in print spooling, task scheduling, and more.
- Constant Time Complexity: Enqueue and dequeue operations in circular queues boast constant time complexity, making them a favorable choice for real-time systems.
To summarize:
In the intricate tapestry of data structures, circular queues emerge as a thread that weaves efficiency, optimized memory utilization, and constant time complexity. Our endeavor to elucidate the nuances of circular queues equips you with an unmatched grasp over this fundamental concept.
As we part ways, remember that circular queues stand not only as a cornerstone of data structures but also as a testament to the power of organized data manipulation. May your journey through the world of circular queues be enlightening and transformative.
FAQs
A circular queue treats the array as circular, meaning the last position is connected back to the first, allowing better space utilization. In contrast, a normal queue does not reuse emptied slots once the rear reaches the end.
To check if the queue is full, use the condition (rear + 1) % size == front; for empty, check if front == -1. These conditions ensure the circular nature is maintained and prevent overflow or underflow.
The modulo operation ensures the pointers wrap around the end of the array to the beginning. This maintains the circular structure and avoids index out-of-bound errors.
Both enqueue and dequeue operations have O(1) time complexity as they involve direct index access and simple pointer manipulation. This makes circular queues highly efficient for real-time systems.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment