Python Queue using Doubly Linked List

What is a Queue?

A queue is a linear data structure that works on the principle of FIFO(First in First out) i.e. the element which is inserted first will be removed first. In the queue, the insertion operation is known as enqueue in which an element is inserted into the rear(back) end of the queue, and the deletion operation is known as dequeue in which an element is removed from the front end of the queue.

What is a Doubly Linked List?

A doubly linked list is a type of linked list that contains both the pointers pointing toward the next node and towards the previous node. The node in the doubly linked list has three parts:

  1. Node data.
  2. Pointer to the next node of the sequence in the linked list.
  3. Pointer to the previous node of the sequence in the linked list.

Queue Operations

enqueue(): Add an element to the rear-end of the queue. In enqueue operation, if the queue is empty then create one node with value given by the user and point both head and last on it. But if the elements are in the queue, then create one node with value given by the user, store it in the next of last pointer, also make the prev pointer of the next of last node pointing towards the last node. And Finally update the last node pointer to the next of last node pointer.

dequeue(): Remove and return the first front-end element of the queue. In enqueue operation, if the queue is empty then create one node with value given by the user and point both head and last on it. But if the elements are in the queue, then create one node with value given by the user, store it in the next of last pointer, also make the prev pointer of the next of last node pointing towards the last node. And Finally update the last node pointer to the next of last node pointer.

first(): Return the first element from the queue without removing it. It will return the value of the head node.
size(): Return the number of elements present in the queue. In this operation, firstly one variable count will be initialized with 0 value and store the head in the temp variable. Then, a while loop will be used for the iteration with the condition that if temp is None then iteration will be stopped. On each iteration, update the count variable by 1 and temp variable to next of temp.

isEmpty(): Return True if no element is present in the queue. If the head is having None value i.e. queue is empty, then it will return True else it will return False.

printqueue(): Print all the elements that are present in the queue. In this operation, we will store the head pointer to the temp variable, then the loop will be used to traverse the whole queue with the condition that if temp is None then the loop will stop iterating. On each traversal, we will print the data of that node and update the temp to the next of temp.

Code Implementation

class Node:

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

    def __init__(self):
        self.head = None
        self.last=None
        

    def enqueue(self, data):
        if self.last is None:
            self.head =Node(data)
            self.last =self.head
        else:
            self.last.next = Node(data)
            self.last.next.prev=self.last
            self.last = self.last.next
            
            
            
    def dequeue(self):

        if self.head is None:
            return None
        else:
            temp= self.head.data
            self.head = self.head.next
            self.head.prev=None
            return temp


    def first(self):

        return self.head.data


    def size(self):

        temp=self.head
        count=0
        while temp is not None:
            count=count+1
            temp=temp.next
        return count
    
    
    def isEmpty(self):

        if self.head is None:
            return True
        else:
            return False
            

    def printqueue(self):
        
        print("queue elements are:")
        temp=self.head
        while temp is not None:
            print(temp.data,end=" ")
            temp=temp.next
    
        
if __name__=='__main__':
    queue = Queue()

print("Queue operations using doubly linked list")

queue.enqueue(2)

queue.enqueue(4)

queue.enqueue(6)

queue.enqueue(8)

queue.printqueue()

print("\nfirst element is ",queue.first())

print("Size of the queue is ",queue.size())

queue.dequeue()

queue.dequeue()

print("After applying dequeue() two times")
queue.printqueue()

print("\nqueue is empty:",queue.isEmpty())

This article tried to discuss Python Queue using Doubly Linked List. Hope this blog helps you understand the concept. To practice problems feel free to check MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *