Introduction to Circular Queues in Python
Introduction to Circular Queues
Get concept of introduction to Circular Queues in Python. Circular queues are a variation of traditional queues that offer efficient data management in a circular, ring-like structure.
In this page, we’ll delve into the concept of circular queues, their implementation in Python, and their relevance in data structure and algorithm (DSA) practices.
What is Circular Queue
A circular queue, also known as a ring buffer, is a linear data structure that operates on the principles of a regular queue but with a twist. Unlike a traditional queue, where elements are enqueued and dequeued from opposite ends, a circular queue operates within a fixed-size buffer. Once the buffer is full, new elements start overwriting the oldest ones, creating a circular behavior.
How Circular Queue Works
Circular Queue works by the process of circular increment, you’ll need two pointers: a front pointer and a rear pointer. Initially, both pointers point to the same location in the array.
Here, the circular increment is shown :
# Initialize variables
REAR = 0
# Check for overflow condition
if REAR + 1 == 5:
# Set REAR to the start of the queue
REAR = (REAR + 1) % 5
# Print the updated value of REAR
print("Updated REAR:", REAR)
The following are the operations that can be performed on a circular queue:
- Front : It is used to get the front item from the queue.
- Rear : It is used to get the last element from the queue.
- enQueue(value): This function is used to insert the new value in the queue . The new element is always inserted at the rear end.
- deQueue() : This function deletes an element from the queue. The deletion in queue always takes place from the front end.
Steps for performing enQueue and deQueue operation in Circular Queue:
- Initially queue has a single value 1 and front and rear are set to 1.
- Then insert the value 2 after incrementing the rear.
- Similarly insert the value 3 by incrementing the rear.
- Again insert the value 4 by incrementing the rear.
- Again insert the value 5 by incrementing the rear.
- Now our queue becomes full so delete the element from the front and increment the front .So our front will set at value 2.
- Now Again insert the value 6 by incrementing the rear.
Implementation of Circular Queue in Python
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.front = self.rear = -1
def is_empty(self):
return self.front == -1
def is_full(self):
return (self.rear + 1) % self.capacity == self.front
def enqueue(self, item):
if self.is_full():
print("Queue is full. Cannot enqueue.")
return
elif self.is_empty():
self.front = self.rear = 0
else:
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
print(item, "enqueued to the queue.")
def dequeue(self):
if self.is_empty():
print("Queue is empty. Cannot dequeue.")
return None
elif self.front == self.rear:
item = self.queue[self.front]
self.front = self.rear = -1
else:
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
return item
def display(self):
if self.is_empty():
print("Queue is empty.")
return
print("Queue:", end=" ")
i = self.front
while True:
print(self.queue[i], end=" ")
if i == self.rear:
break
i = (i + 1) % self.capacity
print()
# Create a circular queue with a capacity of 5
cq = CircularQueue(5)
# Enqueue elements
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50)
# Display the queue
cq.display()
# Dequeue elements
print("Dequeued:", cq.dequeue())
print("Dequeued:", cq.dequeue())
# Display the updated queue
cq.display()
# Enqueue more elements
cq.enqueue(60)
cq.enqueue(70)
# Display the final queue
cq.display()
Complexity Analysis of Circular Queue Operation
- Space Complexity: O(N)
- Enqueue Complexity: O(1)
- Dequeue Complexity: O(1)
Difference between Circular Queue and Linear Queue
| Aspect | Circular Queue | Linear Queue |
|---|---|---|
| Data Structure | Circular arrangement of elements | Linear arrangement of elements |
| Overflow Handling | Reuses vacant spaces, wraps around | Requires resizing or memory reallocation |
| Memory Utilization | Optimized due to circular arrangement | May lead to memory fragmentation |
| Space Efficiency | Higher due to circular structure | Can have wasted space due to dequeued elements |
| Implementation | Simpler due to circular nature | Slightly more complex |
Advantages of Circular Queues
Circular queues offer several distinct advantages that make them a preferred choice in various scenarios:
- Efficient Space Usage: Circular queues use a fixed-size buffer, making them suitable for applications with limited memory resources.
- Constant Time Operations: Enqueue and dequeue operations in a circular queue generally occur in constant time, regardless of the number of elements present.
- Data Streaming: Circular queues are commonly used in scenarios involving data streaming, such as audio and video processing, where continuous data flow needs to be managed effectively.
- Implementation of Buffers: They are often employed to implement buffers for communication between different parts of a system.
Conclusion
In conclusion, circular queues are a versatile and efficient data structure with a wide range of applications. Their ability to manage elements in a circular fashion while optimizing memory usage and enabling constant-time operations makes them a valuable tool in computer science. Whether you’re working on system programming, real-time data processing, or any application that involves managing a continuous flow of data, circular queues are an essential concept to grasp.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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