Queue Using Array in Python
Implementation of Queue Using Array in Python
Queue using an array in Python are fundamental for managing data in a first-in, first-out (FIFO) fashion. They are commonly used in various applications, from managing tasks in an operating system to handling print jobs in a printer queue.
In this page, we will delve into the implementation of a queue using an array in python, exploring its advantages, limitations, and the step-by-step process to create one.
Implementation of Queue Using Array
Implementing a queue using an array in python involves creating an array to store the elements and maintaining pointers to keep track of the front and rear positions.
Array Implementation of Queue: How Does it Work?
The array implementation of a queue involves using an array to hold the queue elements. Two pointers, usually named “FRONT” and “REAR,” keep track of the positions for insertion and deletion. The front pointer points to the element that will be dequeued next, and the rear pointer points to the location where the next element will be enqueued.
Algorithm
Enqueue(item)
Step 1:
IF REAR = N -1
Print “OVERFLOW! QUEUE IS ALREADY FULL”
TERMINATE
Step 2:
IF FRONT = -1 AND REAR = -1
SET FRONT AND REAR AT 0 FRONT = REAR = 0
ELSE
INCREMENT REAR BY 1 SET REAR = REAR = 1
[ END OF IF]
Step 3:
INSERT ELEMNET AT REAR Set QUEUE[ REAR] = ITEM
Step 4:
EXIT
Algorithm
Dequeue()
Step 1:
IF FRONT = -1 or FRONT > REAR
Print “UNDERFLOW! QUEUE IS EMPTY”
TERMINATE
ELSE
SET DELETE FRONT VALUE VAL = QUEUE[ FRONT]
Step 2:
IF FRONT == REAR
SET BOTH FRONT AND REAR AT -1 SET FRONT = REAR =-1
ELSE
INCREMENT FRONT BY 1 SET FRONT = FRONT + 1
[ END OF IF ]
STEP 3:
EXIT
Scenario 1: Printer Queue Management
In this scenario, we’ll create a simple implementation of a printer queue using an array-based queue.
class PrinterQueue:
def __init__(self, size):
self.size = size
self.queue = [None] * size
self.front = self.rear = -1
def enqueue(self, job):
if self.rear == self.size - 1:
print("Queue is full. Cannot enqueue.")
return
if self.front == -1:
self.front = 0
self.rear += 1
self.queue[self.rear] = job
def dequeue(self):
if self.front == -1:
print("Queue is empty. Cannot dequeue.")
return None
job = self.queue[self.front]
if self.front == self.rear:
self.front = self.rear = -1
else:
self.front += 1
return job
printer_queue = PrinterQueue(5)
printer_queue.enqueue("Print Job 1")
printer_queue.enqueue("Print Job 2")
printer_queue.enqueue("Print Job 3")
jobs
print(printer_queue.dequeue())
print(printer_queue.dequeue())
Explanation:
- We define a ‘PrinterQueue’ class with methods for enqueue and dequeue operations.
- The ‘enqueue’ method adds a print job to the rear of the queue, and the ‘dequeue’ method removes and returns the front print job.
- The queue is implemented as an array, and the ‘front’ and ‘rear’ pointers keep track of the positions.
- If the queue is full and an enqueue operation is attempted, it displays a message that the queue is full.
- If the queue is empty and a dequeue operation is attempted, it displays a message that the queue is empty.
Scenario 2: Breadth-First Search (BFS) Traversal
For this scenario, we’ll create a BFS traversal using an array-based queue.
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in self.graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
graph = Graph()
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(2, 5)
graph.add_edge(3, 6)
graph.add_edge(3, 7)
print("BFS Traversal:")
graph.bfs(1)
Explanation:
- We define a ‘Graph’ class with methods to add edges and perform BFS traversal.
- The BFS traversal uses an array-based queue (‘deque’) to keep track of nodes to be visited.
- The ‘visited’ set helps avoid revisiting nodes.
We start the traversal from a given starting node and enqueue its neighbors for processing.
Advantages of Array-Based Queue Implementation
- Simple implementation
- Efficient memory usage
- Suitable for small to medium-sized queues
Limitations and Considerations
- Fixed size: Array-based queues have a fixed size, leading to potential overflow.
- Wasted space: Empty spaces in the array cannot be used, causing inefficient memory utilization.
Conclusion
Implementing a queue using an array provides a simple and efficient way to manage data in a first-come, first-served fashion. While it has its limitations, it remains a valuable tool in various applications.
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