Posted on by Kalkicode
Code Queue

# Deque implementation using doubly linked list

The problem addressed in this code is the implementation of a Deque (Double-Ended Queue) using a doubly linked list in the C programming language. A Deque is a data structure that supports insertion and deletion of elements at both ends, allowing it to function as both a queue and a stack.

## Problem Statement

The task is to create a Deque using a doubly linked list with the following operations:

1. `newDeque()`: Creates a new Deque.
2. `isEmpty(q)`: Checks if the Deque is empty.
3. `isSize(q)`: Returns the number of elements in the Deque.
4. `insertFront(q, element)`: Inserts an element at the front of the Deque.
5. `insertRear(q, element)`: Inserts an element at the rear of the Deque.
6. `deleteFront(q)`: Removes an element from the front of the Deque.
7. `deleteRear(q)`: Removes an element from the rear of the Deque.
8. `peekFront(q)`: Returns the element at the front of the Deque without removing it.
9. `peekRear(q)`: Returns the element at the rear of the Deque without removing it.
10. `printDqueue(q)`: Displays the elements in the Deque.

## Explanation with an Example

Imagine a restaurant line where customers can join the line at both the front and the back. Additionally, customers can leave the line from both ends. This scenario can be modeled using a Deque, allowing customers to choose where they want to join or leave the line.

## Idea to Solve

The solution involves using a doubly linked list to implement a Deque. Elements can be inserted at both the front and the rear of the list, and they can be removed from both ends as well.

## Pseudocode

``````Structure QNode:
element
next
prev

Structure Deque:
front
rear
size

newDeque():
Create and initialize a new Deque
Return the new Deque

isEmpty(q):
Check if the Deque is empty and return a boolean value

isSize(q):
Return the size of the Deque

insertFront(q, element):
Create a new QNode with the given element
Adjust pointers to insert the node at the front
Increment the size of the Deque

insertRear(q, element):
Create a new QNode with the given element
Adjust pointers to insert the node at the rear
Increment the size of the Deque

deleteFront(q):
Remove the front node from the Deque

deleteRear(q):
Remove the rear node from the Deque

peekFront(q):
Return the element at the front of the Deque without removing it

peekRear(q):
Return the element at the rear of the Deque without removing it

printDqueue(q):
Traverse the Deque and print the elements

Main:
Initialize a new Deque
Insert elements at both ends of the Deque
Print the Deque elements and size
Get and print the front and rear elements
Delete elements from both ends of the Deque
Print the updated Deque elements and size
Get and print the front and rear elements``````

## Algorithm Explanation

1. Initialize a new Deque using the `newDeque` function.
2. Insert elements at the front and rear of the Deque using the `insertFront` and `insertRear` functions.
3. Print the Deque elements and size using the `printDqueue` and `isSize` functions.
4. Use the `peekFront` and `peekRear` functions to get and print the front and rear elements of the Deque.
5. Use the `deleteFront` and `deleteRear` functions to remove elements from the front and rear of the Deque.
6. Print the updated Deque elements and size.

## Code Solution

``````/*
C Program
Deque implementation using doubly linked list
*/
#include <stdio.h>
#include <stdlib.h>

// Queue Node
struct QNode
{
int element;
struct QNode *next;
struct QNode *prev;
};
// Structure of Deque
struct Deque
{
struct QNode *front;
struct QNode *rear;
int size;
};
// Returns a new queue
struct Deque *newDeque()
{
struct Deque *q = (struct Deque *) malloc(sizeof(struct Deque));
if (q == NULL)
{
printf("\n Memory overflow , When creating a new Deque");
}
else
{
// Set initial value
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
return q;
}
int isEmpty(struct Deque *q)
{
if (q->size == 0)
{
return 1;
}
else
{
return 0;
}
}
// Returns the number of elements in queue
int isSize(struct Deque *q)
{
return q->size;
}
// Add node at beginning of queue
void insertFront(struct Deque *q, int element)
{
// Make a new Queue node
struct QNode *node = (struct QNode *) malloc(sizeof(struct QNode));
if (node != NULL)
{
// Set node values
node->element = element;
node->next = q->front;
node->prev = NULL;
if (q->front == NULL)
{
//  When inserting a first node of queue
q->front = node;
q->rear = node;
}
else
{
// Add node at beginning position
q->front->prev = node;
q->front = node;
}
q->size++;
}
else
{
printf("\n Memory Overflow, when creating a new Queue Node\n");
}
}
// Add node at end of queue
void insertRear(struct Deque *q, int element)
{
// Make a new Queue node
struct QNode *node = (struct QNode *) malloc(sizeof(struct QNode));
if (node != NULL)
{
// Set node values
node->element = element;
node->next = NULL;
node->prev = NULL;
if (q->front == NULL)
{
//  When inserting a first node of queue
q->front = node;
q->rear = node;
}
else
{
// Add node at the end
q->rear->next = node;
node->prev = q->rear;
q->rear = node;
}
q->size++;
}
else
{
printf("\n Memory Overflow, when creating a new Queue Node\n");
}
}
// Delete first node
void deleteFront(struct Deque *q)
{
if (isEmpty(q) == 1)
{
return;
}
struct QNode *temp = q->front;
q->front = temp->next;
if (q->front == NULL)
{
q->rear = NULL;
}
else
{
q->front->prev = NULL;
}
q->size--;
free(temp);
}
// Delete last node
void deleteRear(struct Deque *q)
{
if (isEmpty(q) == 1)
{
return;
}
struct QNode *temp = q->rear;
q->rear = temp->prev;
if (q->rear == NULL)
{
q->front = NULL;
}
else
{
q->rear->next = NULL;
}
q->size--;
free(temp);
}
// Returns the first element
int peekFront(struct Deque *q)
{
if (isEmpty(q) == 1)
{
printf("\n Empty Deque \n");
return -1;
}
return q->front->element;
}
// Returns the last element
int peekRear(struct Deque *q)
{
if (isEmpty(q) == 1)
{
printf("\n Empty Deque \n");
return -1;
}
return q->rear->element;
}
// Print the elements of Deque
void printDqueue(struct Deque *q)
{
struct QNode *node = q->front;
printf("\n Deque Element \n");
// Display node of from front to rear
while (node != NULL)
{
printf(" %d", node->element);
node = node->next;
}
printf("\n");
}
int main(int argc, char
const *argv[])
{
struct Deque *q = newDeque();
// Add node at beginning position
insertFront(q, 1);
insertFront(q, 2);
// Add node at last position
insertRear(q, 3);
insertRear(q, 4);
// Add node at beginning position
insertFront(q, 5);
insertFront(q, 6);
// Print inserted node
printDqueue(q);
printf(" Size : %d", isSize(q));
// Get first and last element
printf("\n Front Node : %d", peekFront(q));
printf("\n Rear Node  : %d", peekRear(q));
// Remove queue element
deleteFront(q);
deleteRear(q);
// After delete element
printf(" Size : %d", isSize(q));
printDqueue(q);
// Get first and last element
printf(" Front Node : %d", peekFront(q));
printf("\n Rear Node  : %d", peekRear(q));
return 0;
}``````

#### Output

`````` Deque Element
6 5 2 1 3 4
Size : 6
Front Node : 6
Rear Node  : 4 Size : 4
Deque Element
5 2 1 3
Front Node : 5
Rear Node  : 3``````
``````/*
Java Program
Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
public int element;
public QNode next;
public QNode prev;
public QNode(int element)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
// Implement Deque
public class Deque
{
public QNode front;
public QNode rear;
public int size;
public Deque()
{
this.front = null;
this.rear = null;
this.size = 0;
}
public boolean isEmpty()
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Returns the number of elements in queue
public int isSize()
{
return this.size;
}
// Add node at beginning of queue
public void insertFront(int element)
{
// Make a new Queue node
QNode node = new QNode(element);
node.next =  this.front;
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at beginning position
this.front.prev = node;
this.front = node;
}
this.size++;
}
// Add node at end of queue
public void insertRear(int element)
{
// Make a new Queue node
QNode node = new QNode(element);
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at the end
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
this.size++;
}
// Delete first node
public void deleteFront()
{
if (this.isEmpty() == true)
{
return;
}
QNode temp = this.front;
this.front = temp.next;
if (this.front == null)
{
this.rear = null;
}
else
{
this.front.prev = null;
}
this.size--;
temp = null;
}
// Delete last node
public void deleteRear()
{
if (this.isEmpty() == true)
{
return;
}
QNode temp = this.rear;
this.rear = temp.prev;
if (this.rear == null)
{
this.front = null;
}
else
{
this.rear.next = null;
}
this.size--;
temp = null;
}
// Returns the first element
public int peekFront()
{
if (this.isEmpty() == true)
{
System.out.print("\n Empty Deque \n");
return -1;
}
return this.front.element;
}
// Returns the last element
public int peekRear()
{
if (this.isEmpty() == true)
{
System.out.print("\n Empty Deque \n");
return -1;
}
return this.rear.element;
}
// Print the elements of Deque
public void printDqueue()
{
QNode node = this.front;
System.out.print("\n Deque Element \n");
// Display node of from front to rear
while (node != null)
{
System.out.print(" " + node.element);
node = node.next;
}
System.out.print("\n");
}
public static void main(String[] args)
{
Deque q = new Deque();
// Add node at beginning position
q.insertFront(1);
q.insertFront(2);
// Add node at last position
q.insertRear(3);
q.insertRear(4);
// Add node at beginning position
q.insertFront(5);
q.insertFront(6);
// Print inserted node
q.printDqueue();
System.out.print(" Size : " + q.isSize());
// Get first and last element
System.out.print("\n Front Node : " + q.peekFront());
System.out.print("\n Rear Node : " + q.peekRear());
// Remove queue element
q.deleteFront();
q.deleteRear();
// After delete element
System.out.print("\n Size : " + q.isSize());
q.printDqueue();
// Get first and last element
System.out.print(" Front Node : " + q.peekFront());
System.out.print("\n Rear Node : " + q.peekRear());
}
}``````

#### Output

`````` Deque Element
6 5 2 1 3 4
Size : 6
Front Node : 6
Rear Node : 4
Size : 4
Deque Element
5 2 1 3
Front Node : 5
Rear Node : 3``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
public: int element;
QNode *next;
QNode *prev;
QNode(int element)
{
this->element = element;
this->next = NULL;
this->prev = NULL;
}
};
// Implement Deque
class Deque
{
public: QNode *front;
QNode *rear;
int size;
Deque()
{
this->front = NULL;
this->rear = NULL;
this->size = 0;
}
bool isEmpty()
{
if (this->size == 0)
{
return true;
}
else
{
return false;
}
}
// Returns the number of elements in queue
int isSize()
{
return this->size;
}
// Add node at beginning of queue
void insertFront(int element)
{
// Make a new Queue node
QNode *node = new QNode(element);
node->next = this->front;
if (this->front == NULL)
{
//  When inserting a first node of queue
this->front = node;
this->rear = node;
}
else
{
// Add node at beginning position
this->front->prev = node;
this->front = node;
}
this->size++;
}
// Add node at end of queue
void insertRear(int element)
{
// Make a new Queue node
QNode *node = new QNode(element);
if (this->front == NULL)
{
//  When inserting a first node of queue
this->front = node;
this->rear = node;
}
else
{
// Add node at the end
this->rear->next = node;
node->prev = this->rear;
this->rear = node;
}
this->size++;
}
// Delete first node
void deleteFront()
{
if (this->isEmpty() == true)
{
return;
}
QNode *temp = this->front;
this->front = temp->next;
if (this->front == NULL)
{
this->rear = NULL;
}
else
{
this->front->prev = NULL;
}
this->size--;
temp = NULL;
}
// Delete last node
void deleteRear()
{
if (this->isEmpty() == true)
{
return;
}
QNode *temp = this->rear;
this->rear = temp->prev;
if (this->rear == NULL)
{
this->front = NULL;
}
else
{
this->rear->next = NULL;
}
this->size--;
temp = NULL;
}
// Returns the first element
int peekFront()
{
if (this->isEmpty() == true)
{
cout << "\n Empty Deque \n";
return -1;
}
return this->front->element;
}
// Returns the last element
int peekRear()
{
if (this->isEmpty() == true)
{
cout << "\n Empty Deque \n";
return -1;
}
return this->rear->element;
}
// Print the elements of Deque
void printDqueue()
{
QNode *node = this->front;
cout << "\n Deque Element \n";
// Display node of from front to rear
while (node != NULL)
{
cout << " " << node->element;
node = node->next;
}
cout << "\n";
}
};
int main()
{
Deque q = Deque();
// Add node at beginning position
q.insertFront(1);
q.insertFront(2);
// Add node at last position
q.insertRear(3);
q.insertRear(4);
// Add node at beginning position
q.insertFront(5);
q.insertFront(6);
// Print inserted node
q.printDqueue();
cout << " Size : " << q.isSize();
// Get first and last element
cout << "\n Front Node : " << q.peekFront();
cout << "\n Rear Node : " << q.peekRear();
// Remove queue element
q.deleteFront();
q.deleteRear();
// After delete element
cout << "\n Size : " << q.isSize();
q.printDqueue();
// Get first and last element
cout << " Front Node : " << q.peekFront();
cout << "\n Rear Node : " << q.peekRear();
return 0;
}``````

#### Output

`````` Deque Element
6 5 2 1 3 4
Size : 6
Front Node : 6
Rear Node : 4
Size : 4
Deque Element
5 2 1 3
Front Node : 5
Rear Node : 3``````
``````// Include namespace system
using System;
/*
C# Program
Deque implementation using doubly linked list
*/
// Queue Node
public class QNode
{
public int element;
public QNode next;
public QNode prev;
public QNode(int element)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
// Implement Deque
public class Deque
{
public QNode front;
public QNode rear;
public int size;
public Deque()
{
this.front = null;
this.rear = null;
this.size = 0;
}
public Boolean isEmpty()
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Returns the number of elements in queue
public int isSize()
{
return this.size;
}
// Add node at beginning of queue
public void insertFront(int element)
{
// Make a new Queue node
QNode node = new QNode(element);
node.next = this.front;
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at beginning position
this.front.prev = node;
this.front = node;
}
this.size++;
}
// Add node at end of queue
public void insertRear(int element)
{
// Make a new Queue node
QNode node = new QNode(element);
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at the end
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
this.size++;
}
// Delete first node
public void deleteFront()
{
if (this.isEmpty() == true)
{
return;
}
QNode temp = this.front;
this.front = temp.next;
if (this.front == null)
{
this.rear = null;
}
else
{
this.front.prev = null;
}
this.size--;
temp = null;
}
// Delete last node
public void deleteRear()
{
if (this.isEmpty() == true)
{
return;
}
QNode temp = this.rear;
this.rear = temp.prev;
if (this.rear == null)
{
this.front = null;
}
else
{
this.rear.next = null;
}
this.size--;
temp = null;
}
// Returns the first element
public int peekFront()
{
if (this.isEmpty() == true)
{
Console.Write("\n Empty Deque \n");
return -1;
}
return this.front.element;
}
// Returns the last element
public int peekRear()
{
if (this.isEmpty() == true)
{
Console.Write("\n Empty Deque \n");
return -1;
}
return this.rear.element;
}
// Print the elements of Deque
public void printDqueue()
{
QNode node = this.front;
Console.Write("\n Deque Element \n");
// Display node of from front to rear
while (node != null)
{
Console.Write(" " + node.element);
node = node.next;
}
Console.Write("\n");
}
public static void Main(String[] args)
{
Deque q = new Deque();
// Add node at beginning position
q.insertFront(1);
q.insertFront(2);
// Add node at last position
q.insertRear(3);
q.insertRear(4);
// Add node at beginning position
q.insertFront(5);
q.insertFront(6);
// Print inserted node
q.printDqueue();
Console.Write(" Size : " + q.isSize());
// Get first and last element
Console.Write("\n Front Node : " + q.peekFront());
Console.Write("\n Rear Node : " + q.peekRear());
// Remove queue element
q.deleteFront();
q.deleteRear();
// After delete element
Console.Write("\n Size : " + q.isSize());
q.printDqueue();
// Get first and last element
Console.Write(" Front Node : " + q.peekFront());
Console.Write("\n Rear Node : " + q.peekRear());
}
}``````

#### Output

`````` Deque Element
6 5 2 1 3 4
Size : 6
Front Node : 6
Rear Node : 4
Size : 4
Deque Element
5 2 1 3
Front Node : 5
Rear Node : 3``````
``````<?php
/*
Php Program
Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
public \$element;
public \$next;
public \$prev;

function __construct(\$element)
{
\$this->element = \$element;
\$this->next = null;
\$this->prev = null;
}
}
// Implement Deque
class Deque
{
public \$front;
public \$rear;
public \$size;

function __construct()
{
\$this->front = null;
\$this->rear = null;
\$this->size = 0;
}
public	function isEmpty()
{
if (\$this->size == 0)
{
return true;
}
else
{
return false;
}
}
// Returns the number of elements in queue
public	function isSize()
{
return \$this->size;
}
// Add node at beginning of queue
public	function insertFront(\$element)
{
// Make a new Queue node
\$node = new QNode(\$element);
\$node->next = \$this->front;
if (\$this->front == null)
{
//  When inserting a first node of queue
\$this->front = \$node;
\$this->rear = \$node;
}
else
{
// Add node at beginning position
\$this->front->prev = \$node;
\$this->front = \$node;
}
\$this->size++;
}
// Add node at end of queue
public	function insertRear(\$element)
{
// Make a new Queue node
\$node = new QNode(\$element);
if (\$this->front == null)
{
//  When inserting a first node of queue
\$this->front = \$node;
\$this->rear = \$node;
}
else
{
// Add node at the end
\$this->rear->next = \$node;
\$node->prev = \$this->rear;
\$this->rear = \$node;
}
\$this->size++;
}
// Delete first node
public	function deleteFront()
{
if (\$this->isEmpty() == true)
{
return;
}
\$temp = \$this->front;
\$this->front = \$temp->next;
if (\$this->front == null)
{
\$this->rear = null;
}
else
{
\$this->front->prev = null;
}
\$this->size--;
\$temp = null;
}
// Delete last node
public	function deleteRear()
{
if (\$this->isEmpty() == true)
{
return;
}
\$temp = \$this->rear;
\$this->rear = \$temp->prev;
if (\$this->rear == null)
{
\$this->front = null;
}
else
{
\$this->rear->next = null;
}
\$this->size--;
\$temp = null;
}
// Returns the first element
public	function peekFront()
{
if (\$this->isEmpty() == true)
{
echo "\n Empty Deque \n";
return -1;
}
return \$this->front->element;
}
// Returns the last element
public	function peekRear()
{
if (\$this->isEmpty() == true)
{
echo "\n Empty Deque \n";
return -1;
}
return \$this->rear->element;
}
// Print the elements of Deque
public	function printDqueue()
{
\$node = \$this->front;
echo "\n Deque Element \n";
// Display node of from front to rear
while (\$node != null)
{
echo " ". \$node->element;
\$node = \$node->next;
}
echo "\n";
}
}

function main()
{
\$q = new Deque();
// Add node at beginning position
\$q->insertFront(1);
\$q->insertFront(2);
// Add node at last position
\$q->insertRear(3);
\$q->insertRear(4);
// Add node at beginning position
\$q->insertFront(5);
\$q->insertFront(6);
// Print inserted node
\$q->printDqueue();
echo " Size : ". \$q->isSize();
// Get first and last element
echo "\n Front Node : ". \$q->peekFront();
echo "\n Rear Node : ". \$q->peekRear();
// Remove queue element
\$q->deleteFront();
\$q->deleteRear();
// After delete element
echo "\n Size : ". \$q->isSize();
\$q->printDqueue();
// Get first and last element
echo " Front Node : ". \$q->peekFront();
echo "\n Rear Node : ". \$q->peekRear();
}
main();``````

#### Output

`````` Deque Element
6 5 2 1 3 4
Size : 6
Front Node : 6
Rear Node : 4
Size : 4
Deque Element
5 2 1 3
Front Node : 5
Rear Node : 3``````
``````/*
Node Js Program
Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
constructor(element)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
// Implement Deque
class Deque
{
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
isEmpty()
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Returns the number of elements in queue
isSize()
{
return this.size;
}
// Add node at beginning of queue
insertFront(element)
{
// Make a new Queue node
var node = new QNode(element);
node.next = this.front;
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at beginning position
this.front.prev = node;
this.front = node;
}
this.size++;
}
// Add node at end of queue
insertRear(element)
{
// Make a new Queue node
var node = new QNode(element);
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at the end
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
this.size++;
}
// Delete first node
deleteFront()
{
if (this.isEmpty() == true)
{
return;
}
var temp = this.front;
this.front = temp.next;
if (this.front == null)
{
this.rear = null;
}
else
{
this.front.prev = null;
}
this.size--;
temp = null;
}
// Delete last node
deleteRear()
{
if (this.isEmpty() == true)
{
return;
}
var temp = this.rear;
this.rear = temp.prev;
if (this.rear == null)
{
this.front = null;
}
else
{
this.rear.next = null;
}
this.size--;
temp = null;
}
// Returns the first element
peekFront()
{
if (this.isEmpty() == true)
{
process.stdout.write("\n Empty Deque \n");
return -1;
}
return this.front.element;
}
// Returns the last element
peekRear()
{
if (this.isEmpty() == true)
{
process.stdout.write("\n Empty Deque \n");
return -1;
}
return this.rear.element;
}
// Print the elements of Deque
printDqueue()
{
var node = this.front;
process.stdout.write("\n Deque Element \n");
// Display node of from front to rear
while (node != null)
{
process.stdout.write(" " + node.element);
node = node.next;
}
process.stdout.write("\n");
}
}

function main()
{
var q = new Deque();
// Add node at beginning position
q.insertFront(1);
q.insertFront(2);
// Add node at last position
q.insertRear(3);
q.insertRear(4);
// Add node at beginning position
q.insertFront(5);
q.insertFront(6);
// Print inserted node
q.printDqueue();
process.stdout.write(" Size : " + q.isSize());
// Get first and last element
process.stdout.write("\n Front Node : " + q.peekFront());
process.stdout.write("\n Rear Node : " + q.peekRear());
// Remove queue element
q.deleteFront();
q.deleteRear();
// After delete element
process.stdout.write("\n Size : " + q.isSize());
q.printDqueue();
// Get first and last element
process.stdout.write(" Front Node : " + q.peekFront());
process.stdout.write("\n Rear Node : " + q.peekRear());
}
main();``````

#### Output

`````` Deque Element
6 5 2 1 3 4
Size : 6
Front Node : 6
Rear Node : 4
Size : 4
Deque Element
5 2 1 3
Front Node : 5
Rear Node : 3``````
``````#  Python 3 Program
#  Deque implementation using doubly linked list

#  Queue Node
class QNode :

def __init__(self, element) :
self.element = element
self.next = None
self.prev = None

#  Implement Deque
class Deque :

def __init__(self) :
self.front = None
self.rear = None
self.size = 0

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

#  Returns the number of elements in queue
def isSize(self) :
return self.size

#  Add node at beginning of queue
def insertFront(self, element) :
#  Make a new Queue node
node = QNode(element)
node.next = self.front
if (self.front == None) :
#   When inserting a first node of queue
self.front = node
self.rear = node
else :
#  Add node at beginning position
self.front.prev = node
self.front = node

self.size += 1

#  Add node at end of queue
def insertRear(self, element) :
#  Make a new Queue node
node = QNode(element)
if (self.front == None) :
#   When inserting a first node of queue
self.front = node
self.rear = node
else :
#  Add node at the end
self.rear.next = node
node.prev = self.rear
self.rear = node

self.size += 1

#  Delete first node
def deleteFront(self) :
if (self.isEmpty() == True) :
return

temp = self.front
self.front = temp.next
if (self.front == None) :
self.rear = None
else :
self.front.prev = None

self.size -= 1
temp = None

#  Delete last node
def deleteRear(self) :
if (self.isEmpty() == True) :
return

temp = self.rear
self.rear = temp.prev
if (self.rear == None) :
self.front = None
else :
self.rear.next = None

self.size -= 1
temp = None

#  Returns the first element
def peekFront(self) :
if (self.isEmpty() == True) :
print("\n Empty Deque ")
return -1

return self.front.element

#  Returns the last element
def peekRear(self) :
if (self.isEmpty() == True) :
print("\n Empty Deque ")
return -1

return self.rear.element

#  Print the elements of Deque
def printDqueue(self) :
node = self.front
print("\n Deque Element ")
#  Display node of from front to rear
while (node != None) :
print(" ", node.element, end = "")
node = node.next

print(end = "\n")

def main() :
q = Deque()
#  Add node at beginning position
q.insertFront(1)
q.insertFront(2)
#  Add node at last position
q.insertRear(3)
q.insertRear(4)
#  Add node at beginning position
q.insertFront(5)
q.insertFront(6)
#  Print inserted node
q.printDqueue()
print(" Size : ", q.isSize(), end = "")
#  Get first and last element
print("\n Front Node : ", q.peekFront(), end = "")
print("\n Rear Node : ", q.peekRear(), end = "")
#  Remove queue element
q.deleteFront()
q.deleteRear()
#  After delete element
print("\n Size : ", q.isSize(), end = "")
q.printDqueue()
#  Get first and last element
print(" Front Node : ", q.peekFront(), end = "")
print("\n Rear Node : ", q.peekRear(), end = "")

if __name__ == "__main__": main()``````

#### Output

`````` Deque Element
6  5  2  1  3  4
Size :  6
Front Node :  6
Rear Node :  4
Size :  4
Deque Element
5  2  1  3
Front Node :  5
Rear Node :  3``````
``````#  Ruby Program
#  Deque implementation using doubly linked list

#  Queue Node
class QNode
# Define the accessor and reader of class QNode
attr_accessor :element, :next, :prev

def initialize(element)
self.element = element
self.next = nil
self.prev = nil
end

end

#  Implement Deque
class Deque
# Define the accessor and reader of class Deque
attr_accessor :front, :rear, :size

def initialize()
self.front = nil
self.rear = nil
self.size = 0
end

def isEmpty()
if (self.size == 0)
return true
else
return false
end

end

#  Returns the number of elements in queue
def isSize()
return self.size
end

#  Add node at beginning of queue
def insertFront(element)
#  Make a new Queue node
node = QNode.new(element)
node.next = self.front
if (self.front == nil)
#   When inserting a first node of queue
self.front = node
self.rear = node
else
#  Add node at beginning position
self.front.prev = node
self.front = node
end

self.size += 1
end

#  Add node at end of queue
def insertRear(element)
#  Make a new Queue node
node = QNode.new(element)
if (self.front == nil)
#   When inserting a first node of queue
self.front = node
self.rear = node
else
#  Add node at the end
self.rear.next = node
node.prev = self.rear
self.rear = node
end

self.size += 1
end

#  Delete first node
def deleteFront()
if (self.isEmpty() == true)
return
end

temp = self.front
self.front = temp.next
if (self.front == nil)
self.rear = nil
else
self.front.prev = nil
end

self.size -= 1
temp = nil
end

#  Delete last node
def deleteRear()
if (self.isEmpty() == true)
return
end

temp = self.rear
self.rear = temp.prev
if (self.rear == nil)
self.front = nil
else
self.rear.next = nil
end

self.size -= 1
temp = nil
end

#  Returns the first element
def peekFront()
if (self.isEmpty() == true)
print("\n Empty Deque \n")
return -1
end

return self.front.element
end

#  Returns the last element
def peekRear()
if (self.isEmpty() == true)
print("\n Empty Deque \n")
return -1
end

return self.rear.element
end

#  Print the elements of Deque
def printDqueue()
node = self.front
print("\n Deque Element \n")
#  Display node of from front to rear
while (node != nil)
print(" ", node.element)
node = node.next
end

print("\n")
end

end

def main()
q = Deque.new()
#  Add node at beginning position
q.insertFront(1)
q.insertFront(2)
#  Add node at last position
q.insertRear(3)
q.insertRear(4)
#  Add node at beginning position
q.insertFront(5)
q.insertFront(6)
#  Print inserted node
q.printDqueue()
print(" Size : ", q.isSize())
#  Get first and last element
print("\n Front Node : ", q.peekFront())
print("\n Rear Node : ", q.peekRear())
#  Remove queue element
q.deleteFront()
q.deleteRear()
#  After delete element
print("\n Size : ", q.isSize())
q.printDqueue()
#  Get first and last element
print(" Front Node : ", q.peekFront())
print("\n Rear Node : ", q.peekRear())
end

main()``````

#### Output

`````` Deque Element
6 5 2 1 3 4
Size : 6
Front Node : 6
Rear Node : 4
Size : 4
Deque Element
5 2 1 3
Front Node : 5
Rear Node : 3``````
``````/*
Scala Program
Deque implementation using doubly linked list
*/
// Queue Node
class QNode(var element: Int , var next: QNode , var prev: QNode)
{
def this(element: Int)
{
this(element, null, null);
}
}
// Implement Deque
class Deque(var front: QNode , var rear: QNode , var size: Int)
{
def this()
{
this(null, null, 0);
}
def isEmpty(): Boolean = {
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Returns the number of elements in queue
def isSize(): Int = {
return this.size;
}
// Add node at beginning of queue
def insertFront(element: Int): Unit = {
// Make a new Queue node
var node: QNode = new QNode(element);
node.next = this.front;
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at beginning position
this.front.prev = node;
this.front = node;
}
this.size += 1;
}
// Add node at end of queue
def insertRear(element: Int): Unit = {
// Make a new Queue node
var node: QNode = new QNode(element);
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at the end
this.rear.next = node;
node.prev = this.rear;
this.rear = node;
}
this.size += 1;
}
// Delete first node
def deleteFront(): Unit = {
if (this.isEmpty() == true)
{
return;
}
var temp: QNode = this.front;
this.front = temp.next;
if (this.front == null)
{
this.rear = null;
}
else
{
this.front.prev = null;
}
this.size -= 1;
temp = null;
}
// Delete last node
def deleteRear(): Unit = {
if (this.isEmpty() == true)
{
return;
}
var temp: QNode = this.rear;
this.rear = temp.prev;
if (this.rear == null)
{
this.front = null;
}
else
{
this.rear.next = null;
}
this.size -= 1;
temp = null;
}
// Returns the first element
def peekFront(): Int = {
if (this.isEmpty() == true)
{
print("\n Empty Deque \n");
return -1;
}
return this.front.element;
}
// Returns the last element
def peekRear(): Int = {
if (this.isEmpty() == true)
{
print("\n Empty Deque \n");
return -1;
}
return this.rear.element;
}
// Print the elements of Deque
def printDqueue(): Unit = {
var node: QNode = this.front;
print("\n Deque Element \n");
// Display node of from front to rear
while (node != null)
{
print(" " + node.element);
node = node.next;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var q: Deque = new Deque();
// Add node at beginning position
q.insertFront(1);
q.insertFront(2);
// Add node at last position
q.insertRear(3);
q.insertRear(4);
// Add node at beginning position
q.insertFront(5);
q.insertFront(6);
// Print inserted node
q.printDqueue();
print(" Size : " + q.isSize());
// Get first and last element
print("\n Front Node : " + q.peekFront());
print("\n Rear Node : " + q.peekRear());
// Remove queue element
q.deleteFront();
q.deleteRear();
// After delete element
print("\n Size : " + q.isSize());
q.printDqueue();
// Get first and last element
print(" Front Node : " + q.peekFront());
print("\n Rear Node : " + q.peekRear());
}
}``````

#### Output

`````` Deque Element
6 5 2 1 3 4
Size : 6
Front Node : 6
Rear Node : 4
Size : 4
Deque Element
5 2 1 3
Front Node : 5
Rear Node : 3``````
``````/*
Swift 4 Program
Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
var element: Int;
var next: QNode? ;
var prev: QNode? ;
init(_ element: Int)
{
self.element = element;
self.next = nil;
self.prev = nil;
}
}
// Implement Deque
class Deque
{
var front: QNode? ;
var rear: QNode? ;
var size: Int;
init()
{
self.front = nil;
self.rear = nil;
self.size = 0;
}
func isEmpty()->Bool
{
if (self.size == 0)
{
return true;
}
else
{
return false;
}
}
// Returns the number of elements in queue
func isSize()->Int
{
return self.size;
}
// Add node at beginning of queue
func insertFront(_ element: Int)
{
// Make a new Queue node
let node: QNode? = QNode(element);
node!.next = self.front;
if (self.front == nil)
{
//  When inserting a first node of queue
self.front = node;
self.rear = node;
}
else
{
// Add node at beginning position
self.front!.prev = node;
self.front = node;
}
self.size += 1;
}
// Add node at end of queue
func insertRear(_ element: Int)
{
// Make a new Queue node
let node: QNode? = QNode(element);
if (self.front == nil)
{
//  When inserting a first node of queue
self.front = node;
self.rear = node;
}
else
{
// Add node at the end
self.rear!.next = node;
node!.prev = self.rear;
self.rear = node;
}
self.size += 1;
}
// Delete first node
func deleteFront()
{
if (self.isEmpty() == true)
{
return;
}
var temp: QNode? = self.front;
self.front = temp!.next;
if (self.front == nil)
{
self.rear = nil;
}
else
{
self.front!.prev = nil;
}
self.size -= 1;
temp = nil;
}
// Delete last node
func deleteRear()
{
if (self.isEmpty() == true)
{
return;
}
var temp: QNode? = self.rear;
self.rear = temp!.prev;
if (self.rear == nil)
{
self.front = nil;
}
else
{
self.rear!.next = nil;
}
self.size -= 1;
temp = nil;
}
// Returns the first element
func peekFront()->Int
{
if (self.isEmpty() == true)
{
print("\n Empty Deque ");
return -1;
}
return self.front!.element;
}
// Returns the last element
func peekRear()->Int
{
if (self.isEmpty() == true)
{
print("\n Empty Deque ");
return -1;
}
return self.rear!.element;
}
// Print the elements of Deque
func printDqueue()
{
var node: QNode? = self.front;
print("\n Deque Element ");
// Display node of from front to rear
while (node  != nil)
{
print(" ", node!.element, terminator: "");
node = node!.next;
}
print(terminator: "\n");
}
}
func main()
{
let q: Deque = Deque();
// Add node at beginning position
q.insertFront(1);
q.insertFront(2);
// Add node at last position
q.insertRear(3);
q.insertRear(4);
// Add node at beginning position
q.insertFront(5);
q.insertFront(6);
// Print inserted node
q.printDqueue();
print(" Size : ", q.isSize(), terminator: "");
// Get first and last element
print("\n Front Node : ", q.peekFront(), terminator: "");
print("\n Rear Node : ", q.peekRear(), terminator: "");
// Remove queue element
q.deleteFront();
q.deleteRear();
// After delete element
print("\n Size : ", q.isSize(), terminator: "");
q.printDqueue();
// Get first and last element
print(" Front Node : ", q.peekFront(), terminator: "");
print("\n Rear Node : ", q.peekRear(), terminator: "");
}
main();``````

#### Output

`````` Deque Element
6  5  2  1  3  4
Size :  6
Front Node :  6
Rear Node :  4
Size :  4
Deque Element
5  2  1  3
Front Node :  5
Rear Node :  3``````
``````/*
Kotlin Program
Deque implementation using doubly linked list
*/
// Queue Node
class QNode
{
var element: Int;
var next: QNode ? ;
var prev: QNode ? ;
constructor(element: Int)
{
this.element = element;
this.next = null;
this.prev = null;
}
}
// Implement Deque
class Deque
{
var front: QNode ? ;
var rear: QNode ? ;
var size: Int;
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
fun isEmpty(): Boolean
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Returns the number of elements in queue
fun isSize(): Int
{
return this.size;
}
// Add node at beginning of queue
fun insertFront(element: Int): Unit
{
// Make a new Queue node
var node: QNode ? = QNode(element);
node?.next = this.front;
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at beginning position
this.front?.prev = node;
this.front = node;
}
this.size += 1;
}
// Add node at end of queue
fun insertRear(element: Int): Unit
{
// Make a new Queue node
var node: QNode ? = QNode(element);
if (this.front == null)
{
//  When inserting a first node of queue
this.front = node;
this.rear = node;
}
else
{
// Add node at the end
this.rear?.next = node;
node?.prev = this.rear;
this.rear = node;
}
this.size += 1;
}
// Delete first node
fun deleteFront(): Unit
{
if (this.isEmpty() == true)
{
return;
}
var temp: QNode ? = this.front;
this.front = temp?.next;
if (this.front == null)
{
this.rear = null;
}
else
{
this.front?.prev = null;
}
this.size -= 1;

}
// Delete last node
fun deleteRear(): Unit
{
if (this.isEmpty() == true)
{
return;
}
var temp: QNode ? = this.rear;
this.rear = temp?.prev;
if (this.rear == null)
{
this.front = null;
}
else
{
this.rear?.next = null;
}
this.size -= 1;

}
// Returns the first element
fun peekFront(): Int
{
if (this.isEmpty() == true)
{
print("\n Empty Deque \n");
return -1;
}
return this.front!!.element;
}
// Returns the last element
fun peekRear(): Int
{
if (this.isEmpty() == true)
{
print("\n Empty Deque \n");
return -1;
}
return this.rear!!.element;
}
// Print the elements of Deque
fun printDqueue(): Unit
{
var node: QNode ? = this.front;
print("\n Deque Element \n");
// Display node of from front to rear
while (node != null)
{
print(" " + node.element);
node = node.next;
}
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
var q: Deque = Deque();
// Add node at beginning position
q.insertFront(1);
q.insertFront(2);
// Add node at last position
q.insertRear(3);
q.insertRear(4);
// Add node at beginning position
q.insertFront(5);
q.insertFront(6);
// Print inserted node
q.printDqueue();
print(" Size : " + q.isSize());
// Get first and last element
print("\n Front Node : " + q.peekFront());
print("\n Rear Node : " + q.peekRear());
// Remove queue element
q.deleteFront();
q.deleteRear();
// After delete element
print("\n Size : " + q.isSize());
q.printDqueue();
// Get first and last element
print(" Front Node : " + q.peekFront());
print("\n Rear Node : " + q.peekRear());
}``````

#### Output

`````` Deque Element
6 5 2 1 3 4
Size : 6
Front Node : 6
Rear Node : 4
Size : 4
Deque Element
5 2 1 3
Front Node : 5
Rear Node : 3``````

## Resultant Output Explanation

The elements are inserted at the front and rear of the Deque, and the elements and size are printed. The front and rear elements are obtained and printed. After that, elements are deleted from both ends of the Deque, and the updated elements and size are printed again. The front and rear elements are once again obtained and printed.

## Time Complexity

1. Insertion (Front/Rear): O(1)
2. Deletion (Front/Rear): O(1)
3. Peek: O(1)
4. IsEmpty: O(1)
5. IsSize: O(1)

All operations in this Deque implementation have constant time complexity, making it efficient for real-world applications. This implementation provides a foundation for efficiently handling data using a Deque structure.

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

Categories
Relative Post