- Introduction
- What is a Queue in Python?
- How does Python Queue work?
- Types of the queue in Python
- Operations in Python
- Methods available in the queue
- Built-in Python List
Introduction
A queue is a type of data structure that holds data in a First in First Out manner. Queue follows a specific order for the operations to be performed on the data. The queue is widely implemented as a waiting list for single shared resources or devices such as Printers, CPU, Disk, etc. There are different types of queues like a simple queue, priority queue, circular queue, and deque or double-ended queue. All these types of queues are used for different scenarios. Queues are very useful for example, if we need a process to be executed one after other automatically in an order i.e. just like a list. It will process the tasks in a manner called “First In First Out” which means the first process or task in the queue will be executed and removed first, after that other processes will be started. A queue can be implemented in programming languages such as Python, Java, C++, etc. Here are going to discuss its implementation in Python Programming Language.
What is a Queue in Python?
As we just discussed what is a queue. It is the same in Python and works on the same methodology “First in First Out” (FIFO). A queue has two ends such as the front end and rear end. The items that can be inserted from is the rear end and the items that are removed from the queue are from the Front end. Therefore, the item that is inserted first in the queue will be the first item that will be removed from the queue and it satisfies the FIFO methodology.
How does Python Queue work?
Python queue can be easily implemented to work with real-world problems. For better understanding, it can be compared with a line of people waiting for their number to purchase tickets from the ticket counter. The first person who entered the line will get the tickets first and after that, he will be removed from the line, followed by the next person in the lane and so on. A similar logic will be applied in Python Queue too for programs and processes to be executed.
Let us see the below diagram to better understand the ends of the Queue:
| 1 | 2 | 3 | 4 | 5 |
In the above queue, the first element 1 is representing the Front end of the queue and the last element 5 is representing the end of the queue that will be processed at last. The insertion will take place after the last element i.e. 5 and the removal of elements will take place from the start of the list i.e. 1.
Types of the queue in Python
As we just discussed in the introduction that there are 4 types of the queue in the data structure. But, In Python, there are mainly two types of queues that are discussed below:
- FIFO Queue: FIFO stands for “First In First Out” which means the element that will be inserted first is the element to come out first. While working with FIFO Queue in python, we need to call Queue() class from the queue module.
- LIFO Queue: LIFO stands for “Last In First Out” which means that the element that is to be inserted at the last is the element to come out first. It is just like a stack, where the top element will be treated first. While working with LIFO Queue, we need to call LifoQueue() class from the queue module in Python.
Operations in Python
The operations available in Python are described as follows:
- Front: The operation gives the first element from the queue where the Time Complexity for this operation is O(1).
- Rear: The operation gives the last element from the queue where the Time Complexity for this operation is O(1).
- Enqueue: In this operation, an element is added at the end of the queue. When there is no capacity for elements to be added to the queue, it goes to a condition of overflow and the Time complexity for this operation is also O(1).
- Dequeue: In this type of operation, we can delete the element from any end of the queue such as front or rear. Also, the insertion of elements takes place at both ends. The time complexity for this operation is the same as other operations i.e. O(1).
Methods available in the queue
There are some important methods available in Python which are very useful. These methods are listed below:
- get(): This method is used to remove and return an element from the queue. When there is no element in the queue, it waits for the element to be available in the queue.
- put(): This method is used to add an element in the queue which can be represented as an instance of Queue. If there is no capacity for more elements to be added to the queue, then the method will block.
- qsize: The qsize() method in the queue class of Python returns the total number of elements present in the queue. Or we can say that it tells us the length of the queue.
- full(): This method is used to check if the queue is full and it returns True if the queue is full.
- maxsize(): This method is an integer that tells the upper bound limit of the number of elements that can be entered in the queue. The insertion of the elements will be blocked once it reaches the maxsize of the elements to be inserted.
Built-in Python List
The built-in list of methods in Python can be used as the queue, but the use of these built-in methods as the queue is not well suited when we see it from the view of performance. The built-in methods in Python are the insert() and pop() functions that are used to add and remove elements from the queue. Lists are a little slow as compared with queues and the reason behind this is when we insert a new element to the list, it requires the shifting of elements by one. And this process takes O(n) time. To better understand this concept, go through the example below:
Example:
que = []
que.append(‘Person1’)
que.append(‘Person2’)
que.append(‘Person3’)
print(que)
#List is quite slow because of the shifting of elements by one place.
print(que.pop(0))
OUTPUT:
[‘Person1’, ‘Person2’, ‘Person3’]
Person1
class Queue:
def __init__(self):
self.queue = list()
def add_elements(self, val):
if val not in self.queue:
self.queue.insert(0, val)
return True
return False
def size(self):
return len(self.queue)
OurQueue = Queue()
OurQueue.add_element(“Person1”)
OurQueue.add_element(“Person2”)
OurQueue.add_element(“Person3”)
OurQueue.add_element(“Person4”)
print(“Length of the Queue: “, OurQueue.size())
OUTPUT:
Length of the Queue: 4
Removing elements from a queue
The removal of elements from a queue takes place from the Rear end of the queue. The process of removing an element from a queue is also called deque. Let us see the following example to understand this concept more clearly:
class Queue:
def __init__(self):
self.queue = list()
def add_element(self,val):
# Insert method to add element in the queue
if val not in self.queue:
self.queue.insert(0,val)
return True
return False
# Pop method to delete element from the queue
def remove_element(self):
if len(self.queue)>0:
return self.queue.pop()
return ("Queue is Empty")
que = Queue()
que.add_element("January")
que.add_element("February")
que.add_element("March")
que.add_element("April")
print(que)
print(que.remove_element())
print(que.remove_element())
OUTPUT:
January
February
Sorting a Python queue
Sorting a queue becomes important in some scenarios where we need to perform specific operations. It can be done in Python by various methods. Here is an example below to better understand the sorting of queue:
import queue
q = queue.Queue()
q.put(10)
q.put(22)
q.put(16)
q.put(2)
q.put(1)
# Here, we use bubble sort algorithm for sorting
n = q.qsize()
for i in range(n):
# Remove the element
x = q.get()
for j in range(n-1):
# Remove the element
y = q.get()
if x > y :
q.put(y)
else:
q.put(x)
x = y
q.put(x)
while (q.empty() == False):
print(q.queue[0], end = " ")
q.get()
OUTPUT:
1 2 10 16 22
Reversing a Python queue
The queue can be reversed to make use of another queue. It can also be implemented for recursion.
The example below can be understood to know how we can reverse a Python queue:
import queue
q1 = queue.Queue()
q1.put(10)
q1.put(4)
q1.put(3)
q1.put(20)
q1.put(2)
q1.put(9)
def reverseQueue (q1src, q2dest) :
buffer = q1src.get()
if (q1src.empty() == False) :
reverseQueue(q1src, q2dest) #using recursion
q2dest.put(buffer)
return q2dest
q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)
while (qReversed.empty() == False):
print(qReversed.queue[0], end = " ")
qReversed.get()
OUTPUT:
9 2 20 3 4 10
Working with a queue.queue class
Various classes come in the Queue module of Python. Out of all the classes, the Queue class is more important that helps in parallel computing and multiprogramming. This concept can be understood very easily by the following example:
from queue import Queue
que = Queue()
que.put('Person1’)
que.put('Person2')
que.put('Person3')
print(que)
print(que.get())
print(que.get())
print(que.get())
print(que.get_nowait())
print(que.get())
OUTPUT:
<queue.Queue object at 0x00000114B30656A0>
Person1
Person2
Person3
Traceback (most recent call last):
File “C:/Users/Ashu Lakhwan/PycharmProjects/Hello/Queue.py”, line 78, in <module>
print(que.get_nowait())
File “C:Pythonlibqueue.py”, line 198, in get_nowait
return self.get(block=False)
File “C:Pythonlibqueue.py”, line 167, in get
raise Empty
_queue.Empty
Working with a collection.deque Class
The collection. deque class becomes very useful when we are implementing a double-ended queue. The double-ended queue or deque is used to support the insertion and deletion of elements from both the ends such as the Front and Rear ends. The time complexity it takes is O(1) to complete the process.
The example of collection. deque class is as follows:
from collections import deque
queue = deque()
queue.append('Monday')
queue.append('Tuesday')
queue.append('Wednesday')
print(queue)
deque(['Monday ', 'Tuesday', 'Wednesday'])
print(queue.popleft())
print(queue.popleft())
print(queue.popleft())
queue.popleft()
OUTPUT:
deque([‘Monday’, ‘Tuesday’, ‘Wednesday’])
Monday
Tuesday
Wednesday
Traceback (most recent call last):
File “C:/Users/Ashu Lakhwan/PycharmProjects/Hello/Queue.py”, line 101, in <module>
que.popleft()
IndexError: pop from an empty deque
Working with a multiprocessing.Queue Class
This class can be used to process queued items parallelly by multicurrent workers. The multiprocessing. Queue Class shares the data between multiple processes and stores the information of any object that can be picked while processing items.
Example:
from multiprocessing import Queue
queue = Queue()
queue.put('Monday')
queue.put('Tuesday')
queue.put('Wednesday')
print(queue)
print(queue.get())
print(queue.get())
print(queue.get())
OUTPUT:
<multiprocessing.queues.Queue object at 0x000002CA073356A0>
Monday
Tuesday
Wednesday
Implementation of Python queue
There are several ways to implement a Queue to Python. However, some commonly used methods for implementing queues in python include the following:
- list
- collections.deque
- collections.Queue
These methods are discussed above in this article with each topic having a separate example. You may refer to the previous section to understand the different ways of implementing Python Queue.
How to add more than one element in Python?
In this article, we have seen how we can add a single item or element to our queue. Now, let us see how we can add more than one element in Python:
Adding an item in FIFOqueue:
import queue
que = queue.Queue()
for i in range(5):
que.put(i)
while not que.empty():
print(“The value inserted is ”, que)
OUTPUT:
The value inserted is 0
The value inserted is 1
The value inserted is 2
The value inserted is 3
The value inserted is 4
In the above example, the put() method will put the elements from 0 to 5 to the queue.
First In First Out Queue Example
FIFO means the element that is inserted first will be the first element to be removed from the list. To implement the FIFO queue, we are required to import the queue() module in Python.
Let us see an example of implementing FIFO queue to add an item:
Import queue
que = queue.Queue()
que.put(10)
The put() method in the above example will add an element to the queue.
To remove an element from our Queue, the following example can be understood:
Import queue
que = queue.Queue()
que.put(10)
removed_item = que.get()
print(“The removed element from the queue is ”, removed_item)
OUTPUT:
The removed element from the queue is 10
In the above example, the get() method is used to remove the element from the queue.
Last In First Out queue Example
LIFO means the element that is entered at the last will be the first element to be popped out or deleted. To implement, LIFO, we are required to import the queue module and use LifoQueue() method in Python.
Let us understand how we can implement the adding of an element in the LIFO queue:
Import queue
que = queue.LifoQueue()
que.put(5)
The put() method adds an element to the LIFO queue.
Removing an element from the LIFO queue:
Import queue
que = queue.LifoQueue()
que.put(5)
remove_item = que.get()
print(“The removed item is ”, remove_item)
OUTPUT:
The removed item is 5
Conclusion
In this article, we discussed some useful and important concepts of Python Queue and we also looked at how they can be implemented in examples. Python Queue is very similar to standard List in Python, but it is considered as always better from the performance point of view.
Embarking on a journey towards a career in data science opens up a world of limitless possibilities. Whether you’re an aspiring data scientist or someone intrigued by the power of data, understanding the key factors that contribute to success in this field is crucial. The below path will guide you to become a proficient data scientist.
