Python Queue

Python Queue

There are various day to day activities where we find ourselves engaged with queues. Whether it is waiting in toll tax lane or standing on the billing counter for your turn in some store, we all are pretty familiar with the concept of the Queue as we wait for our services. In the same way, the queue in data structure plays a significant role in data science and computer engineering. The thing which makes the Queue unique is its functionalities. Based on the FIFO (First-In-First-Out) model, the data elements are allowed at one end and removed from the other one. But before we jump into the depth of the Queue, let’s discuss – What do we understand by the Queue in Python?

Queue in Python

The Queue in Python is an important concept in Data Structure. The Queue is a data structure where the data elements are organized in a linear manner. Moreover, the Queue in Python helps in controlling the flow of the tasks.

Like the Stack, the Queue is a linear data structure where the data elements are stored with the FIFO (First-In-First-Out) Principle. Its property implies that the least recently added data elements would be removed first. Let’s take a real-life example, where few customers are standing in Queue at the bill counter and wait for their turn to come. The shopkeeper is dealing with each customer one after one. Thus, who comes first would be served first.

Now, let’s discuss some operations associated with the Queue data structure. Have a look at a schematic diagram representing a Queue shown below:

Some of the operations associated with Queue and their descriptions are listed as follow:

S. No.	Operation	Description
1	Front	The Front returns the first data element from the Queue – Time Complexity: O(1)
2	Rear	The Rear returns the last data element from the Queue – Time Complexity: O(1)
3	Enqueue	The Enqueue is used to add the data element to the Queue. However, the condition is said to be overflowing if the Queue appears to be full – Time Complexity: O(1)
4	Dequeue	The Dequeue is used to remove the data element from the Queue. The data elements in the Queue are popped out in the same manner as they as pushed in. However, the condition is said to be underflowing if the Queue appears to be empty – Time Complexity: O(1)

Queue Implementation in Python

Python provides several methods for implementing a Queue. In this section, we will discuss the data structures and modules available in the Python library that are useful in implementing a Queue. Some of the methods used in Queue Implementation are given below:

list
queue.Queue
collections.deque

Queue Implementation using List

The list is a built-in Python data structure available that can help in implementing a Queue. The list uses the functions like append() and pop() instead of enqueue() and dequeue() respectively. However, the list is quite slow to fulfill the purpose as the insertion or removal of a data element at the start needs a shift in all the other data elements by one, requiring the O(n) time.

Here is an example given below that illustrates the Queue's implementation using list.

# Initializing a list
 # as the Queue
 my_queue = [] 
 # Adding some data elements
 # to my_queue
 my_queue.append('Apple')      
 my_queue.append('Banana')
 my_queue.append('Mango')
 my_queue.append('Orange')
 # Printing the data
 # elements of the Queue
 print(my_queue)                    
 # Removing the data
 # elements from
 # Zeroth Index
 print(my_queue.pop(0))             
 print(my_queue.pop(0))
 print(my_queue.pop(0))
 print(my_queue.pop(0))
 # Since the Queue is empty, it will display the error.
 print(my_queue.pop(0))

Output:

['Apple', 'Banana', 'Mango', 'Orange']
 'Apple'
 'Banana'
 'Mango'
 'Orange'
 Traceback (most recent call last):
   File "<stdin>", line 1, in <module>
 IndexError: pop from empty list

Explanation:

In the above code, we have initialized a list as the Queue and inserted a few data elements such as apple, banana, mango and orange in it with the append() function. Then, we have used the pop() function specifying the data element's zeroth position we wanted to remove.

Thus, the above list is behaving like a Queue. Moreover, in the last line of code, we have again used the pop() function on an empty queue that will return an Index Error stating the list is empty.

Queue Implementation using Classes

Using the collections.deque Class

The deque class in Python is used for implementing a double-ended queue supporting the insertion and elimination of data elements from either end in Time Complexity: O(1) (non-amortized).

We can implement a Queue in Python with the help of the deque class provided by the collections module. Since the deque class provides a quicker insert and remove operations, it becomes preferable over the list. However, the deque class uses append(), and popleft() functions instead of the enqueue and deque. Let’s see an example based on this class.

# importing the deque class from collections module
 from collections import deque
 # initializing a queue
 my_queue = deque()
 # inserting data elements to the queue
 my_queue.append('Apple')
 my_queue.append('Mango')
 my_queue.append('Banana')
 my_queue.append('Orange')
 my_queue.append('Kiwi')
 # printing the queue
 print(my_queue)
 # removing the data elements
 print(my_queue.popleft())
 print(my_queue.popleft())
 print(my_queue.popleft())
 print(my_queue.popleft())
 print(my_queue.popleft())
 # Since the queue is empty, it will return and Index error
 print(my_queue.popleft())

Output:

deque(['Apple', 'Mango', 'Banana', 'Orange', 'Kiwi'])
 Apple
 Mango
 Banana
 Orange
 Kiwi 
 Traceback (most recent call last):
   File "D:\Python\queue.py", line 18, in <module>
     print(my_queue.popleft())
 IndexError: pop from an empty deque

Explanation:

In the above example, we have imported the deque class from the collections module and initialize a queue using the class. We have then used the append() function to insert the data elements such as Apple, Mango, Banana, Orange, and Kiwi into the queue. Once the queue is created, we have used the popleft() function to remove data elements one by one in the systematic queue order. However, the function will return an error if the queue gets empty, as in the last example.

Using the queue.Queue class

Python provides a built-in queue module that provides access to its Queue class and implements a queue. The queue.Queue(maxsize) class is used to initialize a variable to a maximum size of maxsize. If maxsize is defined as zero ‘0’, it will create an infinite queue. Moreover, this Queue is based on the FIFO principle.

Some of the functions used in this module are listed in the following table:

S. No.	Function	Description
1	maxsize()	The maxsize() function is used to define the number of items that are allowed in the queue.
2	full()	The full() function returns a Boolean value depending on whether the queue is full or not. It returns True if the data elements are equal to the maxsize of the queue. However, it never returns True if the queue is initialized with the maxsize = 0 (i.e., default).
3	empty()	The empty() function also returns a Boolean value depending on whether the queue is empty or not. Thus, it returns True if the queue is empty or otherwise False.
4	put()	The put() function is used to insert an item or data element into the queue. However, it waits until a free slot is available if in case the queue is full.
5	get()	The get() function is used to remove and return an item or data element from the queue. However, it waits for the item until it’s available if in case the queue is empty.
6	put_nowait(item)	The put_nowait() function is used to insert an item or data element into the queue without blocking or waiting. Moreover, it returns QueueFull if there is no free slot available immediately in the queue.
7	get_nowait()	The get_nowait() function is used to remove and return an item or data element from the queue without blocking or waiting. Moreover, it returns QueueEmpty if in case the queue is empty.
8	qsize()	The qsize() function is used to return the total number of items available in the queue.

Let’s see an example based on this class.

# importing the Queue class from queue module
 from queue import Queue
 # Initializing a queue
 my_queue = Queue(maxsize = 4)
 # printing the present size of the queue
 print(my_queue.qsize()) 
 # Adding the data element to queue
 my_queue.put('Apple')
 my_queue.put('Mango')
 my_queue.put('Banana')
 my_queue.put('Orange')
 # Return Boolean for Full Queue 
 print("\nThe Queue is Full: ", my_queue.full()) 
 # Removing the data element from queue
 print("\nData Elements dequeued from the queue:")
 print(my_queue.get())
 print(my_queue.get())
 print(my_queue.get())
 print(my_queue.get())
 # Return Boolean for Empty Queue
 print("\nThe Queue is Empty: ", my_queue.empty())
 my_queue.put("Kiwi")
 print("\nThe Queue is Empty: ", my_queue.empty()) 
 print("The Queue is Full: ", my_queue.full())

Output:

0
 The Queue is Full: True
 Data Elements dequeued from the queue:
 Apple
 Mango
 Banana
 Orange
 The Queue is Empty: True
 The Queue is Empty: False
 The Queue is Full: False