Queue Data Structure In Python
The primary queue operations are as follows:
- Enqueue: It adds an element to the end of the queue. When the queue reaches its total capacity, it reaches an overflow condition. The time complexity of enqueueing is O:1.
- Dequeue: This operation removes an element from the queue. Since it bases the queue on a FIFO manner, it releases the items in the order of their additions. When the queue becomes empty, it reaches an underflow condition. The time complexity is O:1.
- Front: It gives you the first item from the queue. The time complexity is O:1.
- Rare: It gives you the last item from the queue. The time complexity is O:1.
What are the Methods Available for Queue in Python?
There are numerous methods available in Python to perform operations on the queue. Some of the standard methods are:
- put(item): Inserts an element to the queue
- get(): Gets an element from the queue
- empty(): Checks and returns true if the queue is empty
- qsize: Returns queue’s length
- full(): Checks and returns true if the queue is full
- maxsize(): Maximum elements allowed in a queue
How to Implement Queue in Python?
There are different ways to implement a queue in Python. Some common ways to implement a queue include:
- list
- collections.deque
- collections.Queue
Example: Implementing a Queue in Python with a List
Python list is used as a way of implementing queues. The list’s append() and pop() methods can insert and delete elements from the queue. However, while using this method, shift all the other elements of the list by one to maintain the FIFO manner. This results in requiring O(n) time complexity. The example below demonstrates a Python queue using a list.
# Initialize a queue
queue_exm = []
# Adding elements to the queue
queue_exm.append(‘x’)
queue_exm.append(‘y’)
queue_exm.append(‘z’)
print(“Queue before any operations”)
print(queue_exm)
# Removing elements from the queue
print(“\nDequeuing items”)
print(queue_exm.pop(0))
print(queue_exm.pop(0))
print(queue_exm.pop(0))
print(“\nQueue after deque operations”)
print(queue_exm)
Output:
Example: Implementing a Queue in Python with collections.deque
Collections.deque provides the same O(1) time complexity as queues. Hence, it implements a queue, and performs append() & pop() functions quicker than lists. For performing enqueuing and dequeuing using collections.deque, append() and popleft() functions are used.
From collections import deque
queue_exm = deque()
queue_exm.append(‘x’)
queue_exm.append(‘y’)
queue_exm.append(‘z’)
print(“Queue before operations”)
print(queue_exm)
# Dequeuing elements
print(“\nDequeuing elements”)
print(queue_exm.popleft())
print(queue_exm.popleft())
print(queue_exm.popleft())
print(“\nQueue after operations”)
print(queue_exm)
Output:
Example: Implementing a Queue in Python with the queue.Queue
It is an in-built module for implementing a queue in Python. You can use different functions available in the module to perform operations on a queue. Below is an example of implementing a queue with the help of a queue, along with the use of different functions.
From queue import Queue
queue_exm = Queue(maxsize = 3)
print(queue_exm.qsize())
# Adding of element to queue
queue_exm.put(‘x’)
queue_exm.put(‘y’)
queue_exm.put(‘z’)
print(“Full: “, queue_exm.full())
print(“Dequeuing elements”)
print(queue_exm.get())
print(queue_exm.get())
print(queue_exm.get())
print(“Empty: “, queue_exm.empty())
queue_exm.put(1)
print(“Empty: “, queue_exm.empty())
print(“Full: “, queue_exm.full())
Output:
How to Add Elements to a Queue in Python?
You can add elements to a Python queue from the rear end. The process of adding elements is known as enqueuing. Depicted below is an example to understand it. In this example, you will create a Queue class and use the insert method to implement a FIFO queue.
# Creating the queue class
class Queue:
def __init__(self):
self.queue = list()
def element_add_exm(self,data):
# Using the insert method
if data not in self.queue:
self.queue.insert(0,data)
return True
return False
def leng(self):
return len(self.queue)
Queue_add = Queue()
Queue_add.element_add_exm(“Mercedes Benz”)
Queue_add.element_add_exm(“BMW”)
Queue_add.element_add_exm(“Maserati”)
Queue_add.element_add_exm(“Ferrari”)
Queue_add.element_add_exm(“Lamborghini”)
print(“Queue’s Length: “,Queue_add.leng())
Output:
How to Remove Elements From a Queue in Python?
You can also remove an element from a queue, and that process is called dequeuing. Use the built-in pop() function in the below example to see how to remove an element from the queue. In this code, you will create a Queue class and then define two methods: to add elements and delete them. You will then check the underflow status of the queue (if it’s empty). When it returns false, you will start removing the elements one-by-one.
# Creating the queue class
class Queue:
def __init__(self):
self.queue = list()
def element_add_exm(self,data):
# Using the insert method
if data not in self.queue:
self.queue.insert(0,data)
return True
return False
# Removing elements
def element_remove_exm(self):
if len(self.queue)>0:
return self.queue.pop()
return (“Empty Queue”)
queu = Queue()
queu.element_add_exm(“A”)
queu.element_add_exm(“B”)
queu.element_add_exm(“C”)
queu.element_add_exm(“D”)
print(queu)
print(queu.element_remove_exm())
print(queu.element_remove_exm())
Output:
How to Sort a Python Queue?
You can also sort a queue in Python using for loops. Here’s an example to better understand it. In the code below, you will use two for loops to sort a queue having integer values.
import queue
queu = queue.Queue()
queu.put(5)
queu.put(24)
queu.put(16)
queu.put(33)
queu.put(6)
# Using bubble sort algorithm for sorting
i = queu.qsize()
for x in range(i):
# Removing elements
n = queu.get()
for j in range(i-1):
# Removing elements
y = queu.get()
if n > y :
# putting smaller elements at beginning
queu.put(y)
else:
queu.put(n)
n = y
queu.put(n)
while (queu.empty() == False):
print(queu.queue[0], end = ” “)
queu.get()
Output:
What is multiprocessing.Queue Class?
The multiprocessing.Queue is a class in Python that helps implement a queue that provides process-based parallelism through multi-current workers. It parallelly shares data between multiple processes and stores pickle-able objects. Here’s an example of using multiprocessing.Queue in Python.
from multiprocessing import Queue
queu = Queue()
queu.put(‘Mercedes Benz’)
queu.put(‘BMW’)
queu.put(‘Ferrari’)
print(queu)
print(queu.get())
print(queu.get())
print(queu.get())
Output:
What is the Priority Queue in Python?
Priority queue in Python is a special type of queue that is executed based on priorities. It is not a completely FIFO queue as it sorts and dequeues an element based on priority and not based on when they were added.
It calculates the priorities based on the ordering of their key pairs. They are most useful in scheduling tasks where priority is of importance. For instance, an operating system executes and completes a task based on priority; hence, a priority queue can be used here.
There are multiple ways to implement a priority queue. The two standard ways are through:
- Manually sorted list
- queue.PriorityQueue Class
Example: Implementing Priority Queue in Python with a Manually Sorted List
The manually sorted list can help identify and dequeue smaller and largest items. However, inserting new elements can be challenging as it follows an O(n) time complexity. Hence, the best use of a manually sorted list can be when the number of insertions is minimal. In the code below, you will manually sort a list to implement a priority queue in Python.
priority_queu = []
priority_queu.append((3, ‘Mercedes Benz’))
priority_queu.append((4, ‘BMW’))
priority_queu.append((1, ‘Ferrari’))
priority_queu.append((2, ‘Lamborghini’))
# Resort everytime a new element is added
priority_queu.sort(reverse=True)
while priority_queu:
nxt_itm = priority_queu.pop()
print(nxt_itm)
Output:
Example: Implementing Priority Queue in Python with the queue.PriorityQueue Class
The queue.PriorityQueue class is a preferred option compared to a manually sorted list as it shares common time complexity with a standard queue. It also uses heapq (Heap Queue Algorithm) to perform quick operations.
The primary difference between a standard queue and a queue.PriorityQueue is that the latter offers coordination and locking semantics to handle multiple concurrent events. Here’s an example of implementing a priority queue in Python.
from queue import PriorityQueue
priority_queu = PriorityQueue()
priority_queu.put((3, ‘Mercedes Benz’))
priority_queu.put((4, ‘BMW’))
priority_queu.put((1, ‘Ferrari’))
priority_queu.put((2, ‘Lamborghini’))
while not priority_queu.empty():
nxt_itm = priority_queu.get()
print(nxt_itm)
Output:
Summing it up
In this article, you learned everything about queues in Python, along with examples. You also looked into what priority queues are. You can use these queues as a form of data structure in Python. Python offers several other, less complicated, data structures such as a list, tuple, array, string, etc. Read our next tutorial on the python sort function.
