×

Deque in Data Structure

Deque

A deque referred as “Double-Ended Queue”, is a linear collection of data items same like queue data structure. deque has two ends, front end and rear end, deque is the unrestricted type of data structure, data item can be added into it either front or rear and also data item can be removed or deleted from it either front or rear. Thus, it doesn’t follow first in first out rule. So we can say deque is the hybrid linear structure who provides the functionality of queue and stack in a single data structure.

Deque in Data Structure

Sub types of Deque

  • An input-restricted deque is the queue where deletion of data item can be done from both ends, but insertion can be done at one end only.
  • An output-restricted deque is the queue where insertion can be done at both end, but deletion can be done from one end only.

Language Support:-

  • In C++ provides implemention of deque as std::deque .
    • In java provides deque interface in collections module.
    • In python we can import deque from collections module.

Operations on Deque:-

  • Deque() creates a new deque that is empty. It doesn’t take any parameters and it returns an empty deque.
  • add_Front(data) adds a new data item in to the front of deque. We give data item as parameter and it returns nothing.
  • delete_Front() removes the data item from the front of the deque, returns the data item and it will be modified.
  • add_Rear(data) adds a new data item in to the end of deque, needs to take data as parameter and returns nothing.
  • delete_Rear() removes the data item from the end of deque,

returns the data item and it will be modified.

  • is_Empty() checks to see if the deque is empty and return boolean value.
  • Size() returns the number of items in the deque and return an integer.

Implementation of Deque in C langauge

1. By Circular Array

#include <stdio.h>
 #define MAX 10
 void add_Front(int *, int, int *, int *);
 void add_Rear(int *, int, int *, int *);
 void del_Front(int *, int *, int *);
 void del_Rear(int *, int *, int *);
 void display(int *,int *, int *);
 int main()
 {
 int deque[MAX];
             int front, rear, data,n;
             front = rear = -1;
             for (int i = 0; i < MAX; i++)
             {
                          deque[i] = 0;
             }
              add_Front(deque, 20, &front, &rear);
              add_Rear(deque, 4, &front, &rear);
             add_Front(deque, 7, &front, &rear);
             printf("\nElements in a deque: ");
             display(deque, &front, &rear);
             del_Front(deque, &front, &rear);
             printf("\nElements in a deque after Removing: ");
             display(deque, &front, &rear);
             add_Rear(deque, 54, &front, &rear);
             add_Rear(deque, 76, &front, &rear);
             printf("\nElements in a deque after Addition: ");
             display(deque, &front, &rear);
             del_Rear(deque, &front, &rear);
             printf("\nElements in a deque after Removing: ");
             display(deque, &front, &rear);
 }
 void add_Front(int * deque, int data, int *front, int *rear)// For adding an element at the front of deque
 {
       if ((*front == 0 && *rear == MAX-1) || *front == (*rear)+1)// For checking deque is full or not
             {
                          printf("\nDeque is full.\n");
                          return;
             }
 else if (*front == -1 && *rear==-1)
             {
                          *front = *rear = 0;
                           deque[*front] = data;
                              return;
              }
 else if(*front==0)
 {
                          *front=MAX-1;
                          deque[*front] = data;
                          return;
             }
             else
 {
                          (*front)--;
                         deque[*front]=data;
                         return;
             }
 }
 void add_Rear(int * deque, int data, int *front, int *rear)// For adding an element at the end of deque
 {
             if (*front == 0 && *rear == MAX-1 || *front== (*rear)+1 )
             {
                          printf("\nDeque is full.\n");
                          return;
             }
 else if (*front == -1 && *rear==-1)
             {
                          *front = *rear = 0;
                           deque[*rear] = data;
                          return;
              }
 else if(*rear==MAX-1)
 {
                          *rear=0;
                          deque[*rear] = data;
                          return;
             }
             else
 {
                          (*rear)++;
                         deque[*rear]=data;
                         return;
             }
 }
 void del_Front(int *deque,int *front, int *rear)// For removing an element from the front of deque
 {
             if(*front == -1 && *rear==-1)
             {
                          printf("\nDeque is Empty.\n");
                          return;
             }
             else if(*front==*rear)
             {
                         printf("\nRemoved Data_item: %d", deque[*front]);
                         *front=*rear=-1;
                         return;
             }
             else if(*front==MAX-1)
             {
                         printf("\nRemoved Data_item: %d", deque[*front]);
                         *front=0;
                         return;
             }
             else
             {
                         printf("\nRemoved Data_item: %d", deque[*front]);
                         (*front)++;
                         return;
             }
 }
 void del_Rear(int * deque,int *front, int *rear)// For removing an element from the end of deque
 {
             if(*front == -1 && *rear==-1)// For checking deque is empty or not
             {
                          printf("\nDeque is Empty.\n");
                          return;
             }
             else if(*front==*rear)
             {
                         printf("\nRemoved Data_item: %d", deque[*rear]);
                         *front=*rear=-1;
                         return;
             }
             else if(*rear==0)
             {
                         printf("\nRemoved Data_item: %d", deque[*rear]);
                         *rear=MAX-1;
                         return;
             }
             else
             {
                         printf("\nRemoved Data_item: %d", deque[*rear]);
                         (*rear)--;
                         return;
             }
 }
 void display(int *deque, int *front, int *rear)// For printing the elements of the deque
 {
             int i=*front;
             printf("\nFront: ");
             while(i!=*rear)
             {
                         printf("%d ",deque[i]);
                         i=(i+1)%MAX;
             }
             printf("%d",deque[*rear]);
             printf(" :Rear");
 } 

Output:-

Deque in Data Structure

2. By Doubly Linked list

#include<stdio.h>
 #include<stdlib.h>
 struct node//
 {
 int info;
 struct node *next;
 struct node *back;
 };
 struct node *start = NULL;
 struct node *uni = NULL;
 void add_Front(int item) // For adding an element at the front of deque
 {
             struct node *p,*t,*k;
              if(start == NULL)
              {
              p=start;
              t=(struct node *)malloc(sizeof(struct node ));
              start = t;
              start->info=item;
              start->next=p;
              start->back=NULL;
             }
              else
              {
              k=start->back;
              p=start;
              t=(struct node *)malloc(sizeof(struct node ));
              start=t;
              start->info=item;
              start->next=p;
              start->back=NULL;
              k=start;
              }
 }
 void add_Rear(int item) // For adding an element at the end of deque
 {
 struct node *t,*p;
 t=(struct node *)malloc(sizeof(struct node ));
 if(start==NULL)
 {
 start=t;
 start->info=item;
 start->next=NULL;
 start->back=NULL;
 return;
 }
 else
 {
 struct node *p=start,*k;
 while(p->next!=NULL)
 {
 p=p->next;
 }
 k=p;
 p->next=t;
 p=p->next;
 p->info=item;
 p->next=NULL;
 p->back=k;
 uni=p;
 }
 }
 void del_Front()// For removing an element from the front of deque
 {
              struct node *t,*p;
              if(start==NULL)
              {
                         printf("Deque is Empty\n");
              }
              else if(start->next==NULL)
              {
                         printf("Removed Elements is %d\n",start->info);
                         start = NULL;
              }
              else
              {
                          p =start;
                          t = start->next;
                         start = t;
                          start->back = NULL;
                          printf("Removed Elements is %d\n",p->info);
                          free(p);
              }
 }
 void del_Rear()// For removing an element from the end of deque
 {
              struct node *t;
              if(start==NULL)//For checking the deque is empty or not
              {
                         printf("Deque is Empty\n");
              }
              else if(start->next==NULL)
              {          
                         printf("Removed Elements is %d\n",start->info);
                         start = NULL;
              }
              else
              {
                          t=start;
                          while(t->next->next! = NULL)
                          {
                                      t=t->next;
                          }
                         printf("Removed Elements is %d\n",t->next->info);
                          t->next=NULL;
                          return;
              }
 }
 void traverse(struct node * t) // For printing the elements of the deque
 {
 if(t==NULL)
 {
                         printf(" Deque is empty\n");
             }
             while(t->next!=NULL)
             {
                         printf("%d<->",t->info);
                         t=t->next;
             }
             printf("%d\n",t->info);
 }
 void main()//Driver code
 {
 int n,data,i,item,pos;
 while(1)
 {          
 printf(" 1. Add at Front");
 printf("\n 2. Add at Rear");
 printf("\n 3. Delete from Front");
 printf("\n 4. Delete from Rear");
 printf("\n 5. Traverse the Deque");
 printf("\n 6. Exit\n");
 printf("Enter the choice:-\n");
 scanf("%d",&n);
 switch(n)
 {
 case 1:
                                                  printf("Enter the item which do you wanna insert at Front:-\n");
                          scanf("%d",&item);
                                                  add_Front(item);
                                                  break;
 case 2:
                                                  printf("Enter the item which do you wanna insert at Rear:-\n");
                                                  scanf("%d",&item);
                                                  add_Rear(item);
                                                  break;
 case 3:
                                                  del_Front();
                                                  break;
 case 4:
                                                  del_Rear();
                                                  break;
 case 5:
                                                  printf("Elements in deque is:");
                                                  traverse(start);
                                                  break;
 case 6:
                                                  exit(0);
 }
 }
 } 

Output:-

Deque in Data Structure
Deque in Data Structure

Deque implementation in python:-

We can use deque directly in python which will import deque from collections module. For practice purposes, we do possible implementation below of a deque using python list.

                Class Deque(object):
                                 def_init_(self):
                                                 Self.items=[]
                                def is_Empty(self):
                                                 Return self.items==[]
                                 def add_Front(self, data):
                                                 self.itmes.insert(0,data)
                                 def add_Rear(self, data):
                                                 self.items.append(data)
                                 def delete_Front(self):
                                                 return self.items.pop(0)
                                 def delete_Rear(self):
                                                 return self.items.pop()
                                 def size(self):
                                                 return len(self.items) 

In add_front  we use the insert() method with position 0. So data item add 0th place of the list and if we want add data item in rear so we need to use append() method so data item can be added to the end of the list. Likely for removing data item from the queue we use pop() method with 0th position for remove  data item from the front of list and simple use pop() method for remove data item from the end of the list.

Time Complexity of Deque Operations

 The time complexity of deque operations like add_front(),add_Rear(),delete_front(),delete_Rear() is contant which is o(1) by Circular Array or Doubly Linked List.

In the above example, we have implemented various operations on deque assume as d and currently empty in the table given below:

  Deque Operation              Deque Contents                            Retrun Value
    d.is_Empty                                                                     []                                True
    d.add_front(“cat”)                   [“cat”]               
    d.add_Rear(2)                   [“cat”, 2] 
    d.delete_Front()                   [2]                                “cat”
    d.add_Rear(“dog”)                   [2, ”dog”] 
    d.add_Front(“tiger”)                   [“tiger”, 2 ,”dog”] 
    d.size()                   [“tiger” ,2, ”dog”]                                    3
    d.is_Empty()                   [“tiger” ,2, ”dog”]                                 False
    d.delete_Rear()                   [“tiger”, 2]                                 “dog”
    d.add_Front(10)                   [10, ”tiger”, 2]      
    d.delete_Front()                   [ ”tiger”, 2]                                        10
    d.size()                   [“tiger”, 2]                                    2

Applications of Deque

  • In the internet browser’s history we use deque for recently visited URL’s as to the front of the queue.
  • In computer application undo operation uses deque for storing application’s list.
  • As deque supports both stack and queue operation, so it can be used as both.

Standard problem on Deque

An interesting problem that can be solved by deque data structure easily is palindrome problem. A Palindrome is a string if we read this string from both ends of it then it would be same like madam, radar etc. we will try to make solution so we can check the string whether it is a palindrome or not.

The solution of this problem we store the characters of string in deque from left to right like ordinary queue so front end will hold the first character of string and rear end will hold the last character of string after that we will remove the characters from front as well as rear end simultaneously and check them if they match to each other continuously then string is palindrome otherwise not.


Related Topics

Finding Rank in a Binary Search Tree

Implementation // writing a C++ program to find out the rank and element in the program.  #include <bits/stdc++.h> using namespace std; struct __nod { int record; __nod *Lft, *Rt; int LftSize; }; __nod* new__nod(int record) { __nod *temp = new __nod; temp->record...

6 minutes read.

Binary Tree Implementation Using Arrays

Implementation Converting a binary tree into a list of arrays is one interesting problem. Let us see that in depth. In this section, we will see the implementation of the binary Trees...

4 minutes read.

Queue Data Structure

Queue in DS: The queue is a non-primitive and linear data structure. It works on the principle of FIFO (First In First Out). That is, the element that is added...

4 minutes read.

Find the fractional (n/kth) node in the linked list

Find the fractional (n/kth) node in the linked list In this problem, we have given a singly linked list and a number k. Here we need to find the (n/k)th element...

2 minutes read.

Detect and Remove Loop in a Linked List

Create a function called detectAndRemovetheLoop() that verifies whether a given Linked List has a loop, eliminates the loop if it does, and returns true if it does. It returns false...

6 minutes read.

Advantages and Disadvantages of Linked List

Advantages of Linked List The linked list is a dynamic data structure.You can also decrease and increase the linked list at run-time. That is, you can allocate and deallocate memory at...

3 minutes read.

Circular Linked List

Circular Linked List A circular linked list where all nodes are connected to their next node and last node is connected to the starting node or we can say all nodes...

5 minutes read.

Reverse the Singly Linked List in C

Reverse the Singly Linked List in C This article has given a singly linked list and will reverse the linked list by changing the links between nodes. Example:                         Input:  2 -> 4...

3 minutes read.

What is B tree?

What do you mean by B Tree in Data Structures? In the technological world, a B tree is simply a well-managed and coordinated tree and an integral part of the data...

6 minutes read.

What is a Sparse Matrix in Data Structure?

Definition A matrix in which a few non-zero elements are present is called a Sparse matrix. In a Sparse matrix, almost all the matrices are filled with zero (0). A matrix...

5 minutes read.

Insertion sort

Insertion sort is a simple sorting technique. It is best suited for small data sets, but it does not suitable for large data sets. In this technique, we pick an...

4 minutes read.

Radix Sort

Radix Sort: The radix sort is a non-comparative integer sorting algorithm that sorts the elements by grouping the individual digits of the same location. It shares the same significant position...

4 minutes read.

Heap Sort vs Merge Sort

In this article, we are going to discuss the Heap Sort, Merge sort and the difference between them. What is Heap Sort? Heap – A heap is an abstract data type categorised...

7 minutes read.

Deletion Operation from A B Tree

This article will show the deletion operation through the b tree in C++ programming language. Implementation #include <iostream> using namespace std; class B_TreeNod {   int *kys;   int m;   BTreeNod **C;   int j;   bool leaf;  ...

5 minutes read.

Lowest common ancestor in a binary search tree

Suppose you have given two values of nodes in a binary search tree. You have to find out the lowest common ancestor between the nodes. Let’s take an example tree- For the...

4 minutes read.

Data Structure Infix to Postfix Conversion

Infix to Postfix Conversion The infix expression is easy to read and write by humans. In present time, we use the infix expression in our daily life but the computers are...

4 minutes read.

Types of Linked list

Single linked list  A single linked list is a linked list in which all nodes are connected with each other in sequence. Each node of a singly linked list has two...

7 minutes read.

Function to Insert a Node in a Binary Search Tree

Implementation // writing C++ code that will help us in implementing the insertion operation in a binary search tree. #include <bits/stdc++.h> using namespace std; // creating a new binary search tree node struct __nod { int...

8 minutes read.

Introduction and Implementation of Bloom Filter

It often happens with many of us that when we create an account on some applications like Github, it shows us that the username already exists. You can add some...

4 minutes read.

Bitonical Sort

Arranging an unordered collecttion of things into asignificant order. •Comparision Based Model: Bubble Sort, Selection Sort -->Non-Comparison Based. Model: Bucket Sort or on the other hand a Count Sort Bitonic Sort: Bitonic sort Algorithm was made...

5 minutes read.