Implement queue in Python using linked list

A linked list is a linear data structure in which each data object points to one another. To implement a queue with linked list, we will have to perform insertion and deletion of elements from a linked list such that the element which was added first can only be accessed. This is only possible when we will insert elements at the end of the linked list and access or delete elements from the start of the linked list. In this way the oldest element will be at the start of the linked list and can be accessed or deleted.

To implement a queue with linked list in python, we will first define a node object which will have the current element and will point to the node which will be inserted just after it. The Node can be implemented as follows in python.

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None

When we implement a queue with a linked list, it will have an element named front which will refer to the oldest element inserted in the linked list i.e the first element. All other  elements can be accessed with the help of that.It will also contain a variable named queueSize which will contain the length of the queue. We can implement an empty queue in python as follows.

class Queue:
    def __init__(self):
        self.front=None
        self.queueSize=0

Implement Enqueue operation in queue in Python

When we insert an element into the queue, the operation is called enqueue operation. To implement enqueue operation in a queue with the help of linked list, for every insertion we will add the element to be inserted at the end of the linked list. In this way, the most recent element will always be at the end of the linked list and the oldest element will always be at the front of the linked list.After inserting the element to the queue, we will also get the size of the queue and increment the size by 1. The Enqueue operation can be implemented using linked lists in python as follows.

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 in queue in python

When we take out an element from the queue, the operation is said to be a dequeue operation. The element to be taken out from the queue is the oldest element in the queue. As we know that during a enqueue operation, we add the most recent element to the end of the linked list and the oldest element is on the start of the linked list which is pointed by the front of the queue hence we will remove the element pointed by front and will point front to the next oldest element.Before performing dequeue operation, we will check if queue is empty. If the queue is empty i.e. front points to None, we will raise an exception using python try except with a message that queue is empty. We can implement the dequeue operation as follows.

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

How to access front element of queue

As the front element of the queue is being referenced by front, we just have to return the data in the node pointed by front. It can be implemented as follows.

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

Get the size of the queue

As we keep the current size of the queue in queueSize, we just have to return the value in the queueSize element of the queue. This can be done as follows.

def size(self):
        return self.queueSize

Check if the queue is empty

The element front refers to the oldest element in the queue. If there is no element in the queue, the front will point to None. Thus, to check if the queue is empty, we just have to check if the front points to None. We can implement isEmpty() method to check if the queue is empty as follows.

def isEmpty(self):
        if self.queueSize==0:
            return True
        else:
            return False

The full working code to implement a queue using linked list in python is as follows.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 00:13:19 2021

@author: aditya1117
"""

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
class Queue:
    def __init__(self):
        self.front=None
        self.queueSize=0
    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
    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))
    def isEmpty(self):
        if self.queueSize==0:
            return True
        else:
            return False
    def size(self):
        return self.queueSize
    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))

Conclusion

In this article, we have implemented queue and all its operations using linked list in python. To gain more insight into it and understand how queue is different from inbuilt data structures like python dictionary, list and set , copy the full code given in the above example, paste it into your IDE and experiment with the operations in it. Stay tuned for more informative articles.

The post Implement Queue in Python appeared first on PythonForBeginners.com.

How to implement queue in python?

Queue is a linear data structure in which we can only access or remove the element which was added first to it. We will implement a queue using a list. For implementation, we will define a queue class which will have a list to contain the elements and a queueLength field to contain the length of the list. The Queue class implementation in python will be as follows.

class Queue:
    def __init__(self):
        self.queueList=list()
        self.queueLength=0

Add element to a queue in python

When we add an element to a queue, the operation is termed as enqueue operation. To implement the enqueue operation, we will just append the element to the list in the queue. Then, we will increment the queueLength by one. The enQueue() method to implement the enqueue operation will take the element as argument and perform the operation. This can be implemented as follows.

def enQueue(self,data):
        self.queueList.append(data)
        self.queueLength=self.queueLength+1

Remove element from queue in python

When we remove an element from a queue, the operation is termed as dequeue operation. To implement the dequeue operation, we will just pop the first element of the list in the queue. Then, we will decrement the queueLength by 1. Before dequeue operation, we will check if the queue is empty. If yes, an exception will be raised using python try except with a message that the queue is empty.Otherwise dequeue operation will be done.The deQueue() method to implement the dequeue operation can be implemented as follows.

def deQueue(self):
        try:
            if self.queueLength==0:
                raise Exception("Queue is Empty")
            else:
                temp=self.queueList.pop(0)
                self.queueLength=self.queueLength-1
                return temp
        except Exception as e:
            print(str(e))

Find the length of the queue

To find the length of the queue, we just have to look at the value of the queueLength variable. The length() method implements it as follows.

def length(self):
        return self.queueLength

Check if the queue is empty

To check if the queue is empty, we have to find if the queueLength is 0.The isEmpty() method will implement the logic as follows.

def isEmpty(self):
        if self.queueLength==0:
            return True
        else:
            return False

Get the front element in the queue

To get the front element in the queue, we have to return the first element of the list in the queue. This can be implemented as follows.

def front(self):
        try:
            if self.queueLength==0:
                raise Exception("Queue is Empty")
            else:
                temp=self.queueList[-1]
                return temp
        except Exception as e:
            print(str(e))

The complete code for implementing a queue in python is follows.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 25 20:15:56 2021

@author: aditya1117
"""

class Queue:
    def __init__(self):
        self.queueList=list()
        self.queueLength=0
    def enQueue(self,data):
        self.queueList.append(data)
        self.queueLength=self.queueLength+1
    def deQueue(self):
        try:
            if self.queueLength==0:
                raise Exception("Queue is Empty")
            else:
                temp=self.queueList.pop(0)
                self.queueLength=self.queueLength-1
                return temp
        except Exception as e:
            print(str(e))
    def isEmpty(self):
        if self.queueLength==0:
            return True
        else:
            return False
    def length(self):
        return self.queueLength
    def front(self):
        try:
            if self.queueLength==0:
                raise Exception("Queue is Empty")
            else:
                temp=self.queueList[-1]
                return temp
        except Exception as e:
            print(str(e))

Conclusion

In this article, we have understood the concept behind queue and implemented it in python. Copy the complete code given above, paste it in your IDE to experiment  with the operations to understand the concepts and see how a queue is different from other data structures like python dictionary, list and sets. Stay tuned for more informative articles.

The post Queue in Python appeared first on PythonForBeginners.com.