Implement queue using doubly linked list
In this program, we implement a queue data structure using a doubly linked list in Java,c,c++,python,c#,php etc. A doubly linked list is a data structure where each element (node) in the list contains two references, one pointing to the previous node and the other pointing to the next node. Using a doubly linked list allows us to efficiently add elements to the rear of the queue and remove elements from the front of the queue.
Problem Statement
The problem is to implement a queue data structure using a doubly linked list. The queue should support standard queue operations like enqueue (add element to the rear), dequeue (remove element from the front), and peek (get the front element) efficiently.
Example
Let's consider the following example to demonstrate the implementation of a queue using a doubly linked list.
Input
 Enqueue 1
 Enqueue 2
 Enqueue 3
 Enqueue 4
 Enqueue 5
Output
 Queue Element: 1 2 3 4 5
 Size: 5
 Dequeue Node: 1
 Dequeue Node: 2
 Dequeue Node: 3
 Queue Element: 4 5
 Size: 2
Explanation
 We start by creating an empty queue using the
MyQueue
class.  We enqueue five elements (1, 2, 3, 4, 5) using the
enqueue
method. The elements are added to the rear of the queue.  We print the elements of the queue using the
printQdata
method, which displays "Queue Element: 1 2 3 4 5" and the size using theisSize
method, which displays "Size: 5".  We dequeue three elements from the front of the queue using the
dequeue
method. The elements are removed from the front, and we print the updated elements of the queue and its size.  After dequeuing three elements, the queue contains two elements (4, 5), and the output is "Queue Element: 4 5" and "Size: 2".
Idea to Solve the Problem
To implement the queue using a doubly linked list, we define a QNode
class representing each node in
the doubly linked list. Each node contains data, a reference to the next node (next
), and a
reference to the previous node (prev
). The MyQueue
class has a front
pointer to the front of the queue and a rear
pointer to the rear of the queue. We also keep track
of the size of the queue using the size
variable.
We implement standard queue operations using these pointers and variables. The enqueue
operation
adds a new node to the rear of the queue, the dequeue
operation removes a node from the front of
the queue, and the peek
operation returns the front element of the queue.
Pseudocode
// Define QNode class for each node in the doubly linked list
class QNode
data
next
prev
QNode(data, prev)
this.data = data
this.next = null
this.prev = prev
// Define MyQueue class for the queue
class MyQueue
front
rear
size
MyQueue()
this.front = null
this.rear = null
this.size = 0
function enqueue(data)
// Create a new node with the given data and the current rear as its prev
node = new QNode(data, this.rear)
// Update the rear pointer to the new node
this.rear = node
// If the queue is empty (front is null), update the front pointer to the new node
if this.front == null
this.front = node
// Increment the size by 1
this.size = this.size + 1
function dequeue()
// Check if the queue is empty, if yes, return 1 (indicating empty queue)
if this.isEmpty()
return 1
// Get the data from the front node
data = this.front.data
// Update the front pointer to the next node
this.front = this.front.next
// If the front becomes null, update the rear to null as well (indicating empty queue)
if this.front == null
this.rear = null
// Decrement the size by 1
this.size = this.size  1
// Return the data of the dequeued node
return data
function peek()
// Check if the queue is empty, if yes, return 1 (indicating empty queue)
if this.isEmpty()
return 1
// Otherwise, return the data from the front node
return this.front.data
function isEmpty()
// Check if the size is 0, if yes, return true; otherwise, return false
return this.size == 0
function size()
// Return the value of the size variable
return this.size
Algorithm
 Initialize the
front
andrear
pointers asnull
and thesize
as 0 in theMyQueue
constructor.  Implement the
enqueue
method: Create a new
QNode
with the given data and the currentrear
as itsprev
.  Update the
rear
pointer to the new node.  If the queue is empty (i.e.,
front
isnull
), update thefront
pointer to the new node as well.  Increment the
size
by 1.
 Create a new
 Implement the
dequeue
method: Check if the queue is empty. If yes, return 1 (indicating an empty queue).
 Otherwise, get the data from the
front
node.  Update the
front
pointer to the next node.  If the
front
becomesnull
, update therear
tonull
as well (indicating an empty queue).  Decrement the
size
by 1.  Return the data of the dequeued node.
 Implement the
peek
method: Check if the queue is empty. If yes, return 1 (indicating an empty queue).
 Otherwise, return the data from the
front
node.
 Implement the
isEmpty
method: Check if the
size
is 0. If yes, return true; otherwise, return false.
 Check if the
 Implement the
size
method: Return the value of the
size
variable.
 Return the value of the
Code Solution

1) Implement queue using doubly linked list in java
2) Implement queue using doubly linked list in c++
3) Implement queue using doubly linked list in c
4) Implement queue using doubly linked list in c#
5) Implement queue using doubly linked list in vb.net
6) Implement queue using doubly linked list in php
7) Implement queue using doubly linked list in node js
8) Implement queue using doubly linked list in python
9) Implement queue using doubly linked list in ruby
10) Implement queue using doubly linked list in scala
11) Implement queue using doubly linked list in kotlin
12) Implement queue using doubly linked list in swift
13) Implement queue using doubly linked list in golang
Time Complexity
The time complexity of the enqueue
, dequeue
, peek
, isEmpty
,
and size
operations in this implementation of a queue using a doubly linked list is O(1) since all
these operations involve constanttime pointer manipulations and updates.
Finally
The implementation of a queue using a doubly linked list provides an efficient data structure for queue operations with constanttime complexity for enqueue, dequeue, peek, and other operations. The doubly linked list allows for easy management of the front and rear of the queue, making
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment