Python - Queue

Neha Kumawat

9 months ago

Queues in Python | Insideaiml
Queues in Python | Insideaiml
We always stand in a queue when we have to wait for service. The same goes for the queue data structure where elements are arranged in the queue. The uniqueness of the queue is decided by the way the item is added or removed. The items are only allowed at one end and removed from the other end. It is a First-in-First-out method. The queue can be implemented using a python list, where the insert() and pop() methods are used to add and remove elements.  As data elements are always added at the end of the queue there is no insertion.
A good example of the queue is any queue of consumers for a resource where the consumer that came first is served first.

Operations associated with a queue are 

1) Enqueue: Adds an item to the queue. The queue is said to be an  Overflow condition when it is full – Time Complexity: O(1)
2) Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. The queue is said to be an Underflow condition if it is empty – Time Complexity: O(1)
3) Front:  From the queue, the first item is chosen – Time Complexity: O(1)  
4) Rear:  From queue last item is chosen – Time Complexity : O(1)

Implementation

The queue can be implemented in different ways in python. Implementation of the queue using data structures and modules from the Python library will be covered in this article.
 The following ways are used to implement queue in python:
1 ) list
2) collections.deque
3) queue.Queue

Adding Elements to a Queue

Let us first learn how to add elements to queue.
In the below example we implement the First-in-First-Out method. We use the in-built insert method for adding data elements.
class Queue:

  def __init__(self):
      self.queue = list()

  def addtoq(self,dataval):
# Insert method to add element
      if dataval not in self.queue:
          self.queue.insert(0,dataval)
          return true
      return false

  def size(self):
      return len(self.queue)

TheQueue = Queue()
TheQueue.addtoq("Mon")
TheQueue.addtoq("Tue")
TheQueue.addtoq("Wed")
print(TheQueue.size())

	
When the above code is executed, it produces the following result −
3

Removing Element from a Queue

In the below example we create a queue class where we insert the data and then remove the data using the in-built pop method.
class Queue:

  def __init__(self):
      self.queue = list()

  def addtoq(self,dataval):
# Insert method to add element
      if dataval not in self.queue:
          self.queue.insert(0,dataval)
          return true
      return false
# Pop method to remove element
  def removefromq(self):
      if len(self.queue)>0:
          return self.queue.pop()
      return ("No elements in Queue!")

TheQueue = Queue()
TheQueue.addtoq("Mon")
TheQueue.addtoq("Tue")
TheQueue.addtoq("Wed")
print(TheQueue.removefromq())
print(TheQueue.removefromq())
When the above code is executed, it produces the following result −
Mon
Tue

Various ways  of Implementing Queue

Implementation using list

List is a Python’s built-in data structure that can be used as a queue. Instead of enqueue() and dequeue(), append() and pop() function is used. However, because inserting or deleting an element at the beginning requires shifting all of the other   elements by one, lists are quite slow.
# Python program to  
# demonstrate queue implementation 
# using list 
  
# Initializing a queue 
queue = [] 
  
# Adding elements to the queue 
queue.append('a') 
queue.append('b') 
queue.append('c') 
  
print("Initial queue") 
print(queue) 
  
# Removing elements from the queue 
print("\nElements dequeued from queue") 
print(queue.pop(0)) 
print(queue.pop(0)) 
print(queue.pop(0)) 
  
print("\nQueue after removing elements") 
print(queue) 
  
# Uncommenting print(queue.pop(0)) 
# will raise and IndexError 
# as the queue is now empty 

Output:

Initial queue
['a', 'b', 'c']

Elements dequeued from queue
a
b
c

Queue after removing elements
[]

Traceback (most recent call last):
  File "/home/ef51acf025182ccd69d906e58f17b6de.py", line 25, in 
    print(queue.pop(0))
IndexError: pop from empty list

Implementation using collections.deque

Using deque class from the collections module Queue in Python can be implemented, in the case where we need quicker append and pop operations from both the ends of container Deque is preferred over the list, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity. Instead of enqueue and deque, append() and popleft() functions are used
# Python program to 
# demonstrate queue implementation 
# using collections.dequeue 
  
  
from collections import deque 
  
# Initializing a queue 
q = deque() 
  
# Adding elements to a queue 
q.append('a') 
q.append('b') 
q.append('c') 
  
print("Initial queue") 
print(q) 
  
# Removing elements from a queue 
print("\nElements dequeued from the queue") 
print(q.popleft()) 
print(q.popleft()) 
print(q.popleft()) 
  
print("\nQueue after removing elements") 
print(q) 
  
# Uncommenting q.popleft() 
# will raise an IndexError 
# as queue is now empty 

Output:

Initial queue
deque(['a', 'b', 'c'])

Elements dequeued from the queue
a
b
c

Queue after removing elements
deque([])
Traceback (most recent call last):
  File "/home/b2fa8ce438c2a9f82d6c3e5da587490f.py", line 23, in 
    q.popleft()
IndexError: pop from an empty deque

Implementation using a queue.Queue

The queue is a built-in module of Python is used to implement a queue. queue.Queue(max size) initializes a variable to a maximum size of maxsize. A  maxsize of zero ‘0’ means an infinite queue. This Queue follows the FIFO rule.

There are various functions available in this module:
  • maxsize – Number of items allowed in the queue.
  • empty() – Return true if the queue is empty, false otherwise.
  • full() – Return true if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns true.
  • get() – Remove and return an item from the queue. If queue is empty, wait until an item is available.
  • get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
  • put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
  • put_nowait(item) – Put an item into the queue without blocking.
  • qsize() – Return the number of items in the queue. If no free slot is immediately available, raise QueueFull.
# Python program to 
# demonstrate implementation of 
# queue using queue module 
  
  
from queue import Queue 
  
# Initializing a queue 
q = Queue(maxsize = 3) 
  
# qsize() give the maxsize  
# of the Queue  
print(q.qsize())  
  
# Adding of element to queue 
q.put('a') 
q.put('b') 
q.put('c') 
  
# Return Boolean for Full  
# Queue  
print("\nFull: ", q.full())  
  
# Removing element from queue 
print("\nElements dequeued from the queue") 
print(q.get()) 
print(q.get()) 
print(q.get()) 
  
# Return Boolean for Empty  
# Queue  
print("\nEmpty: ", q.empty()) 
  
q.put(1) 
print("\nEmpty: ", q.empty())  
print("Full: ", q.full()) 
  
# This would result in Infinite  
# Loop as the Queue is empty.  
# print(q.get()) 

Output:

0

Full:  true

Elements dequeued from the queue
a
b
c

Empty:  true

Empty:  false
Full:  false
To know more about python click here and select python option.
I hope you enjoyed reading this article and finally, you came to know about Python - Queue.
For more such blogs/courses on data science, machine learning, artificial intelligence and emerging new technologies do visit us at InsideAIML.
Thanks for reading…
Happy Learning…

Submit Review