.png)
DSA Series Chapter 7– Circular Queue Using Linked List (Python Version)
1. Description
A Circular Queue using Linked List is a queue where the last node points back to the first node, forming a cycle. This avoids the "queue full" problem that arises in array-based circular queues, because linked lists grow dynamically.
We maintain two pointers:
-
front→ first node -
rear→ last node (whose next pointer always points to front)
2. Node Structure in Python
Each node contains:
-
data -
nextpointer
class Node:
def __init__(self, data):
self.data = data
self.next = None
Explanation
-
self.data→ stores element -
self.next→ stores link to next node (for circular queue, last node's next → front)
3. Circular Queue Class
class CircularQueue:
def __init__(self):
self.front = None
self.rear = None
Explanation
-
If queue is empty → both pointers are
None.
4. Enqueue Operation (Insert Element)
def enqueue(self, data):
new_node = Node(data)
# If queue is empty
if self.front is None:
self.front = self.rear = new_node
self.rear.next = self.front # circular link
return
# Otherwise
self.rear.next = new_node # link old rear → new node
self.rear = new_node # update rear
self.rear.next = self.front # maintain circular link
Brief Explanation
-
First insertion makes it circular by pointing rear.next → front
-
Subsequent insertions update rear and maintain circular structure
-
Time Complexity → O(1) always
5. Dequeue Operation (Remove Element)
def dequeue(self):
# If queue is empty
if self.front is None:
print("Queue Underflow")
return None
data = self.front.data
# If only one node
if self.front == self.rear:
self.front = self.rear = None
return data
# Otherwise
self.front = self.front.next # move front ahead
self.rear.next = self.front # maintain circular link
return data
Brief Explanation
-
If queue has 1 element → after deletion both pointers become None
-
If more than 1 element → move front and update circular link
-
Time Complexity → O(1)
6. Peek Operation
def peek(self):
if self.front is None:
print("Queue is empty")
return None
return self.front.data
7. Display Operation
def display(self):
if self.front is None:
print("Queue is empty")
return
temp = self.front
while True:
print(temp.data, end=" ")
temp = temp.next
if temp == self.front:
break
print()
8. Full Program (Complete Implementation)
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularQueue:
def __init__(self):
self.front = None
self.rear = None
def enqueue(self, data):
new_node = Node(data)
if self.front is None:
self.front = self.rear = new_node
self.rear.next = self.front
return
self.rear.next = new_node
self.rear = new_node
self.rear.next = self.front
def dequeue(self):
if self.front is None:
print("Queue Underflow")
return None
data = self.front.data
if self.front == self.rear:
self.front = self.rear = None
return data
self.front = self.front.next
self.rear.next = self.front
return data
def peek(self):
if self.front is None:
print("Queue is empty")
return None
return self.front.data
def display(self):
if self.front is None:
print("Queue is empty")
return
temp = self.front
while True:
print(temp.data, end=" ")
temp = temp.next
if temp == self.front:
break
print()
# Driver code
cq = CircularQueue()
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.display() # 10 20 30
print("Dequeued:", cq.dequeue()) # 10
cq.display() # 20 30
9. Exercises (Important)
Basic Level (10 Questions)
-
Create a circular queue and perform enqueue of 5 integers, then display.
-
Insert elements and remove all elements one by one. Check underflow.
-
Write a function to count the number of nodes in the circular queue.
-
Modify display() to show indexes with values.
-
Check whether the queue has only one element.
-
Write code to get the rear element.
-
Create a method
is_empty()for circular queue. -
Enqueue elements until user stops, then print them.
-
Write a function to clear the entire queue.
-
Modify dequeue() to return -1 instead of None on underflow.
Intermediate Level (10 Questions)
-
Implement search in a circular queue (find if element exists).
-
Write a function to reverse the circular queue.
-
Write a function to insert element at front (still keeping it circular).
-
Detect loop in the queue (though inherently circular).
-
Implement a merge of two circular queues.
-
Convert circular queue to a normal list.
-
Add a method to return the sum of all elements.
-
Find maximum and minimum values in circular queue.
-
Implement circular queue but with strings instead of integers.
-
Delete the last element (special operation).
ALSO CHECK
ALSO CHECK
Comments
Post a Comment