Last Updated on December 14, 2022 by Prepbytes
A queue is an ordered collection of elements in which the addition of one element happens at one end known as REAR and the removal of existing elements occurs at the other end known as FRONT. In this blog, we will discuss a queue using doubly linked list in Python.
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:
- Node data.
- Pointer to the next node of the sequence in the linked list.
- Pointer to the previous node of the sequence in the linked list.
Queue Operations to implement the queue using doubly linked list in Python
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.
Lets take a look at the implementation of queue using doubly linked list in Python.
Code Implementation of queue using doubly linked list in Python
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())
Conclusion
This article tried to discuss queue using doubly linked list in Python. This blog gives you a clear illustration of a queue, a doubly linked list, and the implementation of queue using doubly linked list in Python. We Hope this blog helps you understand the concept. To practice problems feel free to check MYCODE | Competitive Programming.
FAQs related to queue using doubly linked list in Python
1. Why is a doubly linked list used?
A doubly linked list is easier to implement than a singly linked list. While the code for the doubly linked implementation is a little longer than for the singly linked version, it tends to be a bit more “obvious” in its intention, so easier to implement and debug.
2. Is python dequeue a linked list?
Deque uses a linked list as part of its data structure. This is the kind of linked list it uses. With doubly linked lists, the deque is capable of inserting or deleting elements from both ends of a queue with constant O(1) performance.
3. Can we use a queue using a linked list?
Queue supports operations like enqueue and dequeue. It can be implemented using an array and linked list.