Posted on by Kalkicode
Code Queue

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

• 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

1. We start by creating an empty queue using the `MyQueue` class.
2. We enqueue five elements (1, 2, 3, 4, 5) using the `enqueue` method. The elements are added to the rear of the queue.
3. We print the elements of the queue using the `printQdata` method, which displays "Queue Element: 1 2 3 4 5" and the size using the `isSize` method, which displays "Size: 5".
4. 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.
5. 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

1. Initialize the `front` and `rear` pointers as `null` and the `size` as 0 in the `MyQueue` constructor.
2. Implement the `enqueue` method:
• Create a new `QNode` with the given data and the current `rear` as its `prev`.
• Update the `rear` pointer to the new node.
• If the queue is empty (i.e., `front` is `null`), update the `front` pointer to the new node as well.
• Increment the `size` by 1.
3. 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` becomes `null`, update the `rear` to `null` as well (indicating an empty queue).
• Decrement the `size` by 1.
• Return the data of the dequeued node.
4. 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.
5. Implement the `isEmpty` method:
• Check if the `size` is 0. If yes, return true; otherwise, return false.
6. Implement the `size` method:
• Return the value of the `size` variable.

## 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 constant-time pointer manipulations and updates.

## Finally

The implementation of a queue using a doubly linked list provides an efficient data structure for queue operations with constant-time 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

## Comment

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

Naeem     678 Day ago
``good``
Categories
Relative Post