Updated October 23, 2023
Introduction to Queue in Python
A queue in Python is a linear data structure that follows the First-In-First-Out (FIFO) principle. It stores and manages a collection of elements, with the earliest-added element at the front and the latest at the rear. Queues are essential for various applications, such as managing tasks, scheduling, and implementing algorithms like breadth-first search (BFS). Python offers built-in and module-based implementations for handling queues efficiently. There are four types of queues:
- FIFO
- LIFO
- Priority Queue
- Circular Queue
Table of Contents
There are two basic operations carried out in “Queue”:
- Enqueue is known as insertion.
- Dequeue is known as deletion.
A queue is open at both ends. The element that enters first is the one that comes out first from the queue. You cannot randomly add or delete items between queues. Queue helps you make the flow of tasks and keep track of it.
General Queue Algorithm
Below are the points in the general queue algorithm:
1. Declare a list of elements and maximum size of the Queue
2. Set the head and tail of the queue to 0
3. Number of elements in the queue -> Size = Tail – Head
4. Enqueue operation:
- Now check if Size < MaxSize:
- If yes: Append data to Queue and then increment Tail by 1
- If it’s no, print the message: Queue full
5. Dequeue operation
- Check if Size > 0:
- If yes: Pop the first element from the list and then increment Head by 1
- If no: Call the Reset method. Print Message: Empty message
Python provides this in the form of a module called “queue,” which you can import into the Python environment and use directly.
Types of Queue in Python
Below are the different examples as follows:
1. FIFO
Here is an example of a FIFO queue: addition and deletion of one element in the queue:
Code:
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.pop(0)
else:
return "Queue is empty"
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# Create a new queue
my_queue = Queue()
# Enqueue (add) elements to the queue
my_queue.enqueue(1)
my_queue.enqueue(2)
my_queue.enqueue(3)
# Dequeue (remove) an element from the queue
removed_item = my_queue.dequeue()
if removed_item != "Queue is empty":
print(f"Removed: {removed_item}")
# Check the size of the queue
print(f"Queue size: {my_queue.size()}")Output:
2. LIFO
The same addition and deletion can be done over LIFO as well. Here is the example of the LIFO(last in, first out) queue:
Code:
class LIFOQueue:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.pop()
def size(self):
return len(self.items)
# Example usage:
lifo_queue = LIFOQueue()
lifo_queue.enqueue(1)
lifo_queue.enqueue(2)
lifo_queue.enqueue(3)
print("LIFO Queue Size:", lifo_queue.size())
print("Dequeue:", lifo_queue.dequeue())
print("Dequeue:", lifo_queue.dequeue())
Output:
3. Priority Queue
This queue is a bit different from the LIFO and FIFO queues. Here, the order is not a matter of interest.
Why are priority queues used?
Priority Queues have many applications. Some are listed below:
- Graph algorithms: The priority queues are used in graph algorithms like Dijkstra’s Shortest Path and Prim’s Minimum Spanning Trees.
- Data Compression: It is used in Huffman codes, which are used to compress data.
- Artificial Intelligence: A* search algorithm finds the shortest path between two vertices of a weighted graph, first trying out the most promising routes. The priority queue keeps track of unexplored routes; the one with a lower bound on the total length is the smallest and is given the highest priority.
- Operating System: It is also used in the OS for load balancing and Interrupt handling. Priority queues are also used in Process Scheduling, where a high-priority task is assigned to the CPU before a low-priority task.
Here are some of the examples of priority queues in Python, which are as follows:
Example #1
This is an example of priority queues using a Python sorted list.
Code:
#Implementing Priority Queues with Sorted list
#declaring empty list
que=[]
#adding elements to the list
que.append((5,'Medium priority task'))
que.append((1,'High priority task'))
que.append((10,'Low priority task'))
#list is sorted evertime a new element is inserted
que.sort(reverse=True)
print("Tasks with their priorities :")
#looping through sorted list
while que:
queue_item=que.pop()
print(queue_item)Output:
Explanation: First, we have declared an empty list into which elements are inserted using the append() method of the List class. The list is then sorted in ascending order. While the loop is used to retrieve elements from the list using the pop() method. This is a manual method of implementing priority queues.
Pros and Cons of this Approach: It is best to identify and delete the smallest or largest element quickly. The main drawback is that inserting a new element into the list is a slow operation. Therefore, sorted lists are suitable only when there are few insertions.
Example #2
This is an example of priority queues using the heapq module. A binary heap is often used to implement priority queues. This Python provides a heapq library. But heapq only provides a min-heap implementation.
Min heap: A complete binary tree where the key at the root must be minimum among all the keys present in the Binary heap.
Code:
# Implementing Priority queue using heapq module
# Importing heapq module
import heapq
# declaring empty list
que = []
# adding elements to the list
heapq.heappush(que, (5, 'Medium Priority task'))
heapq.heappush(que, (1, 'High priority task'))
heapq.heappush(que, (10, 'low priority task'))
# dequeuing elements
print("Elements will be dequeued according to their prorities")
while que:
deque_item = heapq.heappop(que)
print(deque_item)Output:
Explanation: First, we imported the heapq module and then created an empty list. Using the heappush() method of the heapq module, we have inserted the elements into the list. While loop is then used to pop elements out of the list. It can be clearly depicted in the output that the order in which the elements are entered (5 -> 1 -> 10) is different from the dequeuing order (1 -> 5 -> 10).
Example #3
This is an example of priority queues using the queue.PriorityQueue class. Python provides a built-in implementation of the priority queue data structure. Python uses a binary heap to implement priority queues.
Max heap: A complete binary tree where the key at the root must be maximum among all the keys present in the Binary heap.
This is the basic example of implementing a priority queue using a queue. PriorityQueue class.
Code:
# Implementing priority queue using queue.PriorityQueue class
import queue as PQ
q = PQ.PriorityQueue()
q.put(10)
q.put(1)
q.put(5)
print("Dequeing elements")
while not q.empty():
print (q.get())Output:
Explanation: The code imports the queue module and creates an object “q” of the PriorityQueue class. Elements are inserted into this queue using the put() method. After that, a while loop retrieves or dequeues the elements using the get() method. Queue stores the elements according to their priorities ( 1 -> 5 -> 10 ), not by the order of element creation/insertion(10 -> 1 -> 5), as shown in the above output.
4. Circular Queue
This is a type of queue which is circular in shape. Here, the end of the queue, the tail, becomes the first of the queue, that is, the head. This also works on the principle of “FIFO”. This is also called “Ring Buffer”. The application of the circular queue is mostly in the traffic system, CPU scheduling, etc.
Example:
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:
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:
item = self.queue[self.front]
self.front = self.rear = -1
return item
else:
item = self.queue[self.front]
self.front = (self.front + 1) % self.size
return item
def display(self):
if self.front == -1:
print("Queue is empty")
else:
i = self.front
while True:
print(self.queue[i], end=" ")
if i == self.rear:
break
i = (i + 1) % self.size
print()
# Example usage:
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.enqueue(4)
cq.enqueue(5)
cq.display()
cq.dequeue()
cq.dequeue()
cq.display()Output:
Operations in Queue
Now, let’s see some operations related to the queue:
1. Queue empty(): In returns, True or False based on any item available in the queue. If the line holds some values, it returns True. If the queue holds no items, it returns False.
2. Queue full(): It returns True if the queue is full. Else False.
3. Queue task_done: If tasks are enqueued and going on. In order to check if it’s done, this function is used. It basically helps in thread handling.
4. Qyeue qsize(): It returns the size of the queue.
5. Queue put(): It puts an item in the queue.
6. Queue get(): This function get() is use to remove item from queue.
“Collections.deque” and “multiprocessing.queue” are good Python modules that can be explored for queues.
Conclusion – Queue in Python
We have just covered one of the most important concepts in Python’s data structures. We discussed the different types of queues and their operations. This knowledge should help you grasp these concepts better and understand their real-world applications. People widely use stacks and queues as data structures in the real world. Once you understand these concepts well, you can confidently solve data storage inefficiencies.
FAQs
Q1. What are some common use cases for queues in Python?
Ans: People use queues in scenarios such as task scheduling, printer job queue management, web server request handling, and when implementing breadth-first search in graph algorithms.
Q2. Can a Python list be used as a queue?
Ans: Yes, a Python list can be used to implement a basic queue. You can use the append() method to enqueue and the pop(0) method to dequeue. However, for efficiency, it’s better to use the collections.deque class or the queue module for thread-safe queues.
Q3. Are queues thread-safe in Python?
Ans: The queue module in Python provides thread-safe queues, including queue.Queue and queue.PriorityQueue, for use in multithreaded programs.
Recommended Articles
We hope that this EDUCBA information on “Queue in Python” was beneficial to you. You can view EDUCBA’s recommended articles for more information.
