Python - Queue

Neha Kumawat

2 months ago

Queue in Python | Insideaiml
Queue in Python | Insideaiml
We always stand in line where we have to wait for service. The same goes for the queue data structure where the items are arranged in the queue. queue variations are determined by how the item is added or removed. Items only allowed in one end and remove from the other end. It's the first-in-first-out method. The queue can be used using a python list, were input () and pop () methods are used to add and remove items. Since data items are always added at the end of the queue.
A good example of a queue in python is a token system where the first token is first served.

Operations Of a Queue in Python 

1) Enqueue: Adds an element to the end of the queue.  Overflow condition -Queue is full
2) Dequeue: Removes an element from the front of the queue. Underflow condition - Queue is  empty 
3) Front:  Get first item   
4) Rear:  Get  last item  
Time complexity of operations is O(1).

Implementation

We can implement queue in python using data structure and python modules as follows: 
1 ) list
2) collections.deque
3) queue.Queue
4) LinkedList
   
Recommended blog for you :  Introduction to Data Structures 

Adding Elements to a Queue in Python

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("JAN")
TheQueue.addtoq("FEB")
TheQueue.addtoq("MARCH")
print(TheQueue.size())

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

Removing Element from a Queue in Python

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!")

q = Queue()
q.addtoq("JAN")
q.addtoq("FEB")
q.addtoq("Wed")
print(q.removefromq())
print(q.removefromq())
When the above code is executed, it produces the following result −
JAN
FEB

Various Ways of Implementing Queue

Queue Implementation using list

We can use list data structure of python for implementing queue.Use append() method for enqueue() method and pop() method for dequeue() method.
# Python program to  
# demonstrate queue implementation 
# using list 
  
# Initializing a queue 
q = [] 
  
# Adding elements to the queue 
q.append('a') 
q.append('b') 
q.append('c') 
  
print("Initial queue") 
print(q) 
  
# Removing elements from the queue 
print("\nElements dequeued from queue") 
print(q.pop(0)) 
print(q.pop(0)) 
print(q.pop(0)) 
  
print("\nQueue after removing elements") 
print(q) 
  
# Uncommenting print(q.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

Queue Implementation using collections.deque

Queue in Python can be implemented using the deque class from the collections module. Enqueue and dequeue perform on both ends of containers so list data structure is not useful because it is slow. 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 
queue = deque() 
  
# Adding elements to a queue 
queue.append('a') 
queue.append('b') 
queue.append('c') 
  
print("Initial queue") 
print(queue) 
  
# Removing elements from a queue 
print("\nElements dequeued from the queue") 
print(queue.popleft()) 
print(queue.popleft()) 
print(queue.popleft()) 
  
print("\nQueue after removing elements") 
print(queue) 
  
# Uncommenting queue.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

Queue 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.

The functions of this module are:
  • maxsize – Maximum no of elements allowed in the queue.
  • empty() – Return true if empty, otherwise false.
  • full() – Return true if queue is full. 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 a queue is empty, wait until an element is available.
  • get_nowait() – Return an element if one is immediately available, else raise QueueEmpty.
  • put(item) – insert an element into the queue. 
  • put_nowait(item) – insert an element 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 
queue = Queue(maxsize = 3) 
  
# qsize() give the maxsize  
# of the Queue  
print(queue.qsize())  
  
# Adding of element to queue 
queue.put('x') 
queue.put('y') 
queue.put('z') 
  
# Return Boolean for Full  
# Queue  
print("\nFull: ", queue.full())  
  
# Removing element from queue 
print("\nElements dequeued from the queue") 
print(queue.get()) 
print(queue.get()) 
print(queue.get()) 
  
# Return Boolean for Empty  
# Queue  
print("\nEmpty: ", queue.empty()) 
  
queue.put(1) 
print("\nEmpty: ", queue.empty())  
print("Full: ", queue.full()) 
  
# This would result in Infinite  
# Loop as the Queue is empty.  
# print(queue.get()) 

Output:

0

Full:  true

Elements dequeued from the queue
x
y
z

Empty:  true

Empty:  false
Full:  false

Implement Queue in Python using Linked List

A linked list is a linear data structure where each data item points to another. To create a queue with a linked list, we will have to do the insertion and removal of items from the linked list so that the pre-inserted item can only be accessed. This is only possible if we insert items at the end of the linked list and access or delete items at the beginning of the linked list. This way the oldest item will be at the beginning of the linked list and can be accessed or deleted.
Define Node Object which include first item and link to the next inserted item.
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
Then declare empty queue as follows:
class Queue:
    def __init__(self):
        self.front=None
        self.queueSize=0

Implement Enqueue operation

When we put an item in a queue, the operation is called the enqueue operation. To make line functionality with the help of the linked list, in each installation we will add an item to be added at the end of the linked list. In this way, the most recent item will remain at the end of the linked list and the oldest item will remain at the front of the linked list. After adding an item to the queue, we will also find queue size and increase the size by 1. The Enqueue function can be used using the following python linked list.
def enQueue(self,data):
        temp=Node(data)
        if self.front is None:
            self.front=temp
            self.queueSize= self.queueSize+1
        else:
            curr=self.front
            while curr.next!=None:
                curr=curr.next
            curr.next=temp
            self.queueSize=self.queueSize+1

Implement Dequeue Operation

When we take something out of queue, operation is said to be dequeue operation. The item that will be removed from the queue is the oldest item in the line.
def deQueue(self):
        try:
            if self.front == None:
                raise Exception("Queue is Empty")
            else:
                temp=self.front
                self.front=self.front.next
                tempdata=temp.data
                self.queueSize= self.queueSize-1
                del temp
                return tempdata
        except Exception as e:
            print(str(e))

Access Front Element of Queue

def front_element(self):
        try:
            if self.front == None:
                raise Exception("Queue is Empty")
            else:
                return self.front.data
        except Exception as e:
            print(str(e))

The Size of The Queue

def size(self):
        return self.queueSize

Check if The Queue is Empty

def isEmpty(self):
        if self.queueSize==0:
            return True
        else:
            return False
To know more about python programming language follow the InsideAIML YouTube channel.
I hope you enjoyed reading this article and finally, you came to know about Queue in Python.
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

We're Online!

Chat now for any query