Deque Data Structure

1. What is Deque?

Deques are one of the many standard template library (STL) containers available in C++. Similar to queue, a Deque known as a double-ended queue, is an ordered collection of items in Data Structures. It is also often called a head tail linked list.

Figure: Representing Insertion and deletion in a Deque.

What makes a deque stand out is the unrestrictive nature of adding and removing items i.e. it allows fast insertion and deletion of elements at both ends of the queue.

2. Deque Applications

2.1 A-Steal Job Scheduling algorithm

This algorithm is used for implementing the task scheduling for multiple processors often called multiprocessor scheduling.

The processor takes the first element from the deque.

A thread can be accessed from another processor, when one of the processor completes execution of its own threads.

The last element from the deque of another processor is accessed by one of the processor which then executes it.

2.2 Undo Redo operations

The Deque can be implemented to achieve the functionality of Undo Redo operations in software application.

2.3 Palindrome Checker

A palindrome is a word or sequence which reads the same from any direction i.e. either backward or forward.

Reviver, Radar, Level are few examples of palindrome.

Figure: Showing palindrome checker using deque

3. Types of Deque

3.1 Input-restricted deque

In Input-restricted deque deletion can be performed at both the end of the deque, but insertion can be performed at one end only.

Figure: Insertion and deletion in input-restricted deque

3.2 Output-restricted deque

In Output-restricted deque insertion can be performed at both the end of the deque, but deletion can be performed at one end only.

Figure: Insertion and deletion in input-restricted deque

4. Deque Container Algorithm

The C++ STL i.e. Standard Template Library is a powerful set of C++ template classes to provide general purpose templates, classes and functions that implement popular algorithms and data structures such as vectors, queue, list and stack one of which is Deque container.

4.1 Creating a Deque

4.1.1 Header

{`To begin with deque in our programming, we must include its header .
#include 
using namespace std;
`}

4.1.2 Creating Deque objects

Let us create few deque objects for understanding deque creation in a better way.

Creating an empty deque:

{`Pseudo code:
deque deqA;
`}

Creating a deque with 10 empty elements

{`Pseudo code:
deque deqB(10);
`}

Creating a deque with 10 elements, each element having value equals to 2.

{`Pseudo code:
deque< double> deqC(10, 2);
`}

Creating a deque based on an array

{`Pseudo code:
int array[10] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677, 5.55, 8,99};
deque deqC(array, array + 10);
`}

4.1.3 Storing contents of Deque

Using copy constructor to copy the contents of deque ‘deqC’ into deque ‘deqCcopy’

{`Pseudo code:
deque deqCcopy(deqC);
`}

4.2 Displaying the elements of a deque

To display or print the elements of a deque, we can use the [] operator, the at() member function, and iterators.

4.2.1 Printing elements in the same order

Let us create the display() function for printing a deque:

{`
Pseudo code:
void display(deque< double> deqA, char * name)
{
deque< double>::iterator it;

cout << Printing << ": ";

for(it = deqA.begin(); it != deqA.end(); ++it)
cout << *it << " ";

cout << endl;
}
`}

4.2.2. Printing elements in the reverse order

Creating an array to print a deque in reverse order:

{`Pseudo code:
double array[10] = {2.33,5.43, 3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677};
deque< double> deq(array, array + 10);
print(deq, "deq");
// Displaying elements of a deque in reverse order
cout << "deq in reverse order: ";
deque< double>::reverse_iterator rit;
for(rit = deq.rbegin(); rit != deq.rend(); ++rit)
cout << *rit <<  " ";
`}

4.3 Inserting elements into a deque

To insert elements into a deque, we can use the functions push_back(), push_front(), and insert().

4.3.1 Using push_back() function

{`
Pseudo code:
deque< double> deq;
deque< double>::iterator it;
// add an element at the end of the deque
deq.push_back(6.67);
`}

4.3.2 Using push_front() function

{`
Pseudo code:
deq.push_front(4.56);
print(deq, "deq");
`}

4.3.3 Using insert() function

{`
Pseudo code:
it = deq.begin();
++it;
deq.insert(it, 40.04);
print(deq, "deq");
`}

4.4 Resizing a deque

To resize a deque, we can use the resize() function. Deque does not have the capacity()and reserve() member functions, unlike vectors.

4.4.1 Using resize() function

{`
Pseudo code:
deque< double> deq;
deq.push_back(3.45);
deq.push_back(19.26);
deq.push_back(3.517);

cout << "deq size is " << deq.size() << endl;
print(deq, "deq");

// case when new size <= size of vector
deq.resize(1);

cout << "deq size is " << deq.size() << endl;
print(deq, "deq");

// case when new size > size of vector
deq.resize(5);

cout << "deq size is " << deq.size() << endl;
print(deq, "deq");
`}

4.5 Removing elements from a deque

To remove elements from a deque, we can use the pop_back(), pop_front(), and erase() functions.

4.5.1 Using pop_back() function

{`
Pseudo code:
double array[10] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677, 10.25, 89.76};
deque deq(array, array + 10);
deque::iterator it;
print(deq, "deq");
// remove the last element of the deque
deq.pop_back();
print(deq, "deq");
`}

4.5.2 Using pop_front() function

{`
Pseudo code:
deq.pop_front();
print(deq, "deq");
`}

4.5.3 Using erase() function

{`
Pseudo code:
it = deq.begin();
it += 2;
deq.erase(it);
print(deq, "deq");
`}

4.5.4 Removing all elements from a deque

{`Psedo code:
deq.clear();
if(deq.empty())
cout << "deq is empty" << endl;
`}

5. Implementing Doubly Ended Queue in C++ Programming

Performing insert, delete and display operations on Dequeue in C++.

{`#include< iostream>
#include< conio.h>
#include< stdlib.h>
using namespace std;
class node
{
public:
int data;
class  node *next;
class node *prev;
};

class dqueue: public node
{
node *head,*tail;
int top1,top2;
public:
dqueue()
{
top1=0;
top2=0;
head=NULL;
tail=NULL;
}
void push(int x){
node *temp;
int ch;
if(top1+top2 >=5)
{
cout <<"dqueue overflow";
return ;
}
if( top1+top2 == 0)
{
head = new node;
head->data=x;
head->next=NULL;
head->prev=NULL;
tail=head;
top1++;
}
else
{
cout <<" Add element 1.FIRST 2.LAST\n enter ur choice:";
cin >> ch;
if(ch==1)
{
top1++;
temp=new node;
temp->data=x;
temp->next=head;
temp->prev=NULL;
head->prev=temp;
head=temp;
}
else
{
top2++;
temp=new node;
temp->data=x;
temp->next=NULL;
temp->prev=tail;
tail->next=temp;
tail=temp;
}
}
}
void pop()
{
int ch;
cout <<"Delete 1.First Node 2.Last Node\n Enter ur choice:";
cin >>ch;
if(top1 + top2 <=0)
{
cout <<"\nDqueue under flow";
return;
}
if(ch==1)
{
head=head->next;
head->prev=NULL;
top1--;
}
else
{
top2--;
tail=tail->prev;
tail->next=NULL;
}
}

void display()
{
int ch;
node *temp;
cout <<"display from 1.Staring 2.Ending\n Enter ur choice";
cin >>ch;
if(top1+top2 <=0)
{
cout <<"under flow";
return ;
}
if (ch==1)
{
temp=head;
while(temp!=NULL)
{
cout << temp->data <<" ";
temp=temp->next;
}
}
else
{
temp=tail;
while( temp!=NULL)
{
cout << temp->data << " ";
temp=temp->prev;
}
}
}
};

main()
{
dqueue d1;
int ch;
while (1){
cout <<"1.INSERT  2.DELETE  3.DISPLAU  4.EXIT\n Enter ur choice:";
cin >>ch;
switch(ch)
{
case 1:     cout <<"enter element";
cin >> ch;
d1.push(ch); break;
case 2: d1.pop(); break;
case 3: d1.display(); break;
case 4: exit(1);
}  }}
`}

6. Implementing Doubly Ended Queue in JAVA Programming

Performing insert, delete and display operations on Dequeue in JAVA.

{`
/*
Java program to implement dequeue.
*/

import java.io.*;
class dequeue
{
int DQ[] = new int[100];
int n;
int front, rear;
static BufferedReader br = new BufferedReader(newInputStreamReader(System.in));
public dequeue(int nn)
{
n = nn;
front = rear = 0;
}
public void pushrear(int v)
{
if((rear+1)< n)
{
rear++;
DQ[rear] = v;
}
else
System.out.println("Overflow from rear !");
}
public void pushfront(int v)
{
if(front>=0)
{
DQ[front] = v;
front--;
}
else
System.out.println("Overflow from front !");
}
public int popfront()
{
int v;
if(front!=rear)
{
front++;
v = DQ[front];
return v;
}
else
return -9999;
}
public int poprear()
{
int v;
if(front!=rear)
{
v = DQ[rear];
rear--;
return v;
}
else
return -9999;
}
public void display()
{
if(front!=rear)
{
for(int i=front+1;i<=rear;i++)
System.out.println(DQ[i]);
}
else
System.out.println("No element in queue !");
}
public static void main() throws IOException
{
System.out.print("Enter the size of the queue : ");
int size = Integer.parseInt(br.readLine());
dequeue call = new dequeue(size);
int choice;
boolean exit = false;
while(!exit)
{
System.out.print("\n1 : Push from Front\n2 : Push from
Rear\n3 : Delete from Front\n4 : Delete from Rear\n5 : Display\n6 :
Exit\n\nYour Choice : ");
choice = Integer.parseInt(br.readLine());
switch(choice)
{
case 1 :
System.out.print("\nEnter number to be added : ");
int num = Integer.parseInt(br.readLine());
call.pushfront(num);
break;
case 2 :
System.out.print("\nEnter number to be added : ");
int num2 = Integer.parseInt(br.readLine());
call.pushrear(num2);
break;
case 3 :
int popped = call.popfront();
if(popped != -9999)
System.out.println("\nDeleted : " +popped);
break;
case 4 :
int popped2 = call.popfront();
if(popped2 != -9999)
System.out.println("\nDeleted : " +popped2);
break;
case 5 :
call.display();
break;
case 6 :
exit = true;
break;
default :
System.out.println("\nWrong Choice !");
break;
}
}
}
}
`}

7. Implementing Doubly Ended Queue in PYTHON Programming

Performing insert at right hand and left hand, delete at right hand and left hand and display operations on Dequeue in PYTHON.

{`
# importing "collections" for deque operations
import collections
# initializing deque
de = collections.deque([1,2,3])

# using append() to insert element at right end
# inserts 4 at the end of deque
de.append(4)

# printing modified deque
print ("The deque after appending at right is : ")
print (de)

# using appendleft() to insert element at right end
# inserts 6 at the beginning of deque
de.appendleft(6)

# printing modified deque
print ("The deque after appending at left is : ")
print (de)

# using pop() to delete element from right end
# deletes 4 from the right end of deque
de.pop()

# printing modified deque
print ("The deque after deleting from right is : ")
print (de)

# using popleft() to delete element from left end
# deletes 6 from the left end of deque
de.popleft()

# printing modified deque
print ("The deque after deleting from left is : ")
print (de)
`}

8. Deque Vs. Queue

Queue

Queue is an abstract data structure which keeps an order of elements in it. We can add element to the end of a sequence and remove element from the head of the sequence in a queue. Queue can be referred as FIFO (First in First out). This means retrieving elements from a queue happens in the same order as they were put in it.

Deque

Deque or dequeue is double-ended queue. We can add and remove elements to and from both ends of a sequence.

Note

Both Queue and Deque does not specify access to elements between their ends. So, implementation of queue or dequeue may or may not provide operations for accessing elements others than current ends of the sequence. Also Queue and Deque may provide such operations with a very different efficiency.

9. Deque Vs. Vector

Vector

Vector provides insertion and deletion at middle and end of the list only. Also, it provides good performance while insertion and deletion at end and somewhat poor performance while performing insertion and deletion at middle. In case of performance of addition and deletion at end for vector is better than deque.

Deque

Deque provides operations for insertion at front, middle and end. Apart from push_back() and pop_back() APIs like vector, deque also has push_front() and pop_front() API to add and delete elements from front of the list. Both deque and vector provides samekind of performance for insertion & deletion at end and middle. Also, deque provides good performance for insertion and deletion at front also.

Note

One should prefer deque over vector in case of adding or deleting from both the ends like implementing a Queue. The vector should be chosen if insertion or deletions are required mostly in end like implementing a Stack.

10. Deque Vs. List

List

A list holds data in blocks of memory which are individually allocated. A List data structure is quick to insert or delete in the beginning of the list, end or in the middle. It contains only sequential iterators and hence random access is not granted.

Deque

A deque holds data in blocks of allocated memory. It is quick to insert or delete in the beginning or end, but deletion or insertion in the middle is slow. Unlike vectors it has random access and therefore contains random access iterators.

Note

Deque allocates memory in chunks rather than allocating each time for one node. The standard templates are optimized for speed not size or efficiency.

A list should be used when lot of nodes are present that are processing in a largely sequential manner and vector when the processing is more random in nature. Otherwise, a deque should be preferred.

11. Time Complexity – Deque

The time complexity or efficiency of common operations on deques can be summarized as follows:

• Random access - constant O(1)
• Insertion or removal of elements at the end or beginning - constant O(1)
• Insertion or removal of elements - linear O(n)

BIBLIOGRAPHY

[1] Sathasivam R , December 11th, 2014. Deque and its Applications. http://www.slideshare.net/sathasivamr1/team-6-42605244
[2] Cristitomi, October 21st, 2007. The complete guide to STL: Part 3 - Deque. https://www.codeproject.com/Articles/20965/The-complete-guide-to-STL-Part-Deque