Double Ended Queue (Deque) In C++ With Examples

An In-depth Tutorial on Deque or Double-ended Queue in C++. Tutorial explains What is Deque, Basic Operations, C++ & Java Implementation and Applications:

Double ended queue or simply called “Deque” is a generalized version of Queue.

The difference between Queue and Deque is that it does not follow the FIFO (First In, First Out) approach. The second feature of Deque is that we can insert and remove elements from either front or rear ends.

=> Read Through The Easy C++ Training Series

Double Ended Queue Classification

Deque can be classified as follows:

Input-restricted Deque: In input-restricted, deletion can be done from both the ends but insertion can be done only at the rear end of the queue.

Output-restricted Deque: In the output-restricted queue, insertion can be done from both the ends but deletion is done only at one end i.e. the front end of the queue.

We can also implement stacks and queues using deque.

Basic Deque Operations

The following are the basic operations that can be performed on deque.

• insert front: Insert or add an item at the front of the deque.
• insertLast: Insert or add an item at the rear of the deque.
• deleteFront: Delete or remove the item from the front of the queue.
• delete last: Delete or remove the item from the rear of the queue.
• getFront: Retrieves the front item in the deque.
• getLast: Retrieves the last item in the queue.
• isEmpty: Checks if the deque is empty.
• isFull: Checks if the deque is full.

Deque Illustration

An empty deque is represented as follows:

Next, we insert element 1 at the front.

Now, we insert element 3 at the rear.

Next, we add element 5 to the front and when incremented the front points to 4.

Then, we insert elements 7 at the rear and 9 at the front. The deque will look as shown below.

Next, let us remove an element from the front.

Thus, we see that when the elements are inserted at the front, the front position is decremented while it is incremented when an element is removed. For the rear end, the position is incremented for insertion and decremented for removal.

Deque Implementation

C++ Deque Implementation

We can implement a deque in C++ using arrays as well as a linked list. Apart from this, the Standard Template Library (STL) has a class “deque” which implements all the functions for this data structure.

The array implementation of the deque has been given below. As it’s a double-ended queue we have used circular arrays for implementation.

#include<iostream> 
using namespace std; 
  
#define MAX_size 10 	// Maximum size of array or Dequeue 
  
// Deque class 
class Deque 
{ 
int  array[MAX_size]; 
int  front; 
int  rear; 
int  size; 
public : 
Deque(int size) { 
front = -1; 
rear = 0; 
this->size = size; 
    } 
  
    // Operations on Deque: 
void  insertfront(int key); 
void  insertrear(int key); 
void  deletefront(); 
void  deleterear(); 
int  getFront(); 
int  getRear(); 
    
    // Check if Deque is full
bool  isFull(){
return ((front == 0 && rear == size-1)||front == rear+1);    
    } 
    // Check if Deque is empty 
bool  isEmpty(){
return (front == -1);  
    }
}; 
  
// Insert an element at front of the deque
void Deque::insertfront(int key) 
{ 
if (isFull())  { 
cout << "Overflow!!\n" << endl; 
return; 
    } 
  
    // If queue is initially empty,set front=rear=0; start of deque 
if (front == -1)  { 
front = 0; 
rear = 0; 
    } 
else if (front == 0) 		      // front is first position of queue 
front = size - 1 ; 
else // decrement front 1 position 
front = front-1; 
  
array[front] = key ; 			// insert current element into Deque
} 
  
// insert element at the rear end of deque 
void Deque ::insertrear(int key) 
{ 
if (isFull()) { 
cout << " Overflow!!\n " << endl; 
return; 
    } 
  
    //  If queue is initially empty,set front=rear=0; start of deque 
if (front == -1) { 
front = 0; 
rear = 0; 
    } 
else if (rear == size-1) 			   // rear is at last position of queue
rear = 0; 
else						    // increment rear by 1 position 
rear = rear+1; 
  
array[rear] = key ; 		// insert current element into Deque
} 
  
// Delete element at front of Deque 
void Deque ::deletefront() 
{ 
if (isEmpty()) 
   { 
cout << "Queue Underflow!!\n" << endl; 
return ; 
    } 
  
    // Deque has only one element 
 if (front == rear) 
    { 
front = -1; 
rear = -1; 
    } 
else
        // back to initial position 
if (front == size -1) 
front = 0; 
  
else // remove current front value from Deque;increment front by 1
front = front+1; 
} 
  
// Delete element at rear end of Deque 
void Deque::deleterear() 
{ 
if (isEmpty()) 
    { 
cout << " Underflow!!\n" << endl ; 
return ; 
    } 
  
    // Deque has only one element 
if (front == rear) 
    { 
front = -1; 
rear = -1; 
    } 
else if (rear == 0) 
rear = size-1; 
else
rear = rear-1; 
} 
// retrieve front element of Deque 
int Deque::getFront() 
{ 
if (isEmpty())   { 
cout << " Underflow!!\n" << endl; 
return -1 ; 
    } 
return array[front]; 
} 
  
// retrieve rear element of Deque 
int Deque::getRear() 
{ 
if(isEmpty() || rear < 0)  { 
cout << " Underflow!!\n" << endl; 
return -1 ; 
    } 
return array[rear]; 
} 
  
//main program
int main() 
{ 
    Deque dq(5); 
cout << "Insert element 1 at rear end \n"; 
dq.insertrear(1); 
  
cout << "insert element 3 at rear end \n"; 
dq.insertrear(3); 
  
cout << "rear element of deque " << " " << dq.getRear() << endl; 
  
dq.deleterear(); 
cout << "After deleterear, rear = " << dq.getRear() << endl; 
  
cout << "inserting element 5 at front end \n"; 
dq.insertfront(5); 
  
cout << "front element of deque " << " "
<< dq.getFront() << endl; 
  
dq.deletefront(); 
  
cout << "After deletefront, front = " << dq.getFront() << endl; 
return 0; 
}

Output:

Insert element 1 at rear end

insert element 3 at rear end

rear element of deque  3

After deleterear, rear = 1

inserting element 5 at the front end

front element of deque  5

After deletefront, front = 1

Java Deque Implementation

The deque interface in Java, “java.util.Deque” is derived from “java.util.Queue” interface. Deque can be used as a queue (First In, First Out) or a stack (Last In, First Out). These implementations work faster than the linked list.

Given below is the hierarchy for the Deque interface in Java.

We need to remember a few points about the Deque interface in Java:

• The implementation is not thread-safe as there is no external synchronization.
• Deque does not support concurrency by multiple threads.
• Deque’s implemented using arrays do not allow the use of NULL elements.
• Arrays are allowed to grow as per the requirements, with restriction-free capacity and resizable array support being the two most important features.

Following are the various methods supported by the Deque interface:

The following Java implementation demonstrates the various operations discussed above.

import java.util.*; 
  
class Main 
{ 
public static void main(String[] args) 
    { 
        Deque<Integer>deque = new LinkedList<Integer>(); 
  
        // We can add elements to the queue in various ways 
deque.add(1); // add to tail 
deque.addFirst(3); 
deque.addLast(5); 
deque.push(7); //add to head 
deque.offer(9); 
deque.offerFirst(11); 
deque.offerLast(13); 
  
System.out.println("The deque : " + deque + "\n"); 
  
        // Iterate through the queue elements. 
System.out.println("Standard Iterator"); 
        Iterator iterator = deque.iterator(); 
while (iterator.hasNext()) 
System.out.print(" " + iterator.next()); 
  
          // Reverse order iterator 
        Iterator reverse = deque.descendingIterator(); 
System.out.println("\nReverse Iterator"); 
while (reverse.hasNext()) 
System.out.print(" " + reverse.next()); 
  
     
   // Peek returns the head, without deleting 
        // it from the deque 
System.out.println("\n\nPeek " + deque.peek()); 
System.out.println("After peek: " + deque); 
  
        // Pop returns the head, and removes it from 
        // the deque 
System.out.println("\nPop " + deque.pop()); 
System.out.println("After pop: " + deque); 
  
        // We can check if a specific element exists 
        // in the deque 
System.out.println("\nContains element 3?: " + 
deque.contains(3)); 
  
        // We can remove the first / last element. 
deque.removeFirst(); 
deque.removeLast(); 
System.out.println("Deque after removing " + "first and last elements: " + deque); 
  
    } 
}

Output:

The deque : [11, 7, 3, 1, 5, 9, 13]

Standard Iterator
11 7 3 1 5 9 13
Reverse Iterator
13 9 5 1 3 7 11

Peek 11
After peek: [11, 7, 3, 1, 5, 9, 13]

Pop 11
After pop: [7, 3, 1, 5, 9, 13]

Contains element 3?: true

Deque after removing first and last elements: [3, 1, 5, 9]

In the above program, we have used the Deque interface of Java and we defined a deque of integer elements. Then we performed various operations on this deque and output the results of these operations are displayed.

Applications

Deque can be used in some of the following applications.

#1) Scheduling Algorithm: A scheduling algorithm, “A-steal scheduling algorithm” implements task scheduling for various processors in the multiprocessor system. This implementation uses deque and the processor gets the first element from the deque for execution.

#2) Undo List Of Activities: In software applications, we have many actions. One is “undo”. When we have performed undo action many times, all these actions are stored in a list. This list is maintained as a deque so that we can readily add/remove entries from any end.

#3) Remove The Entries After Some Time: Apps refresh entries in their list like apps listing the stock entries, etc. These apps remove the entries after some time and also insert new entries. This is done using a deque.

Conclusion

Deque is a double-ended queue that allows us to add/remove elements from both the ends i.e. front and rear, of the queue. Deque can be implemented using arrays or linked lists. However, we also have a Standard Template Library (STL) class which implements the various operations of the Deque.

In Java, we have a Deque interface that is inherited from the queue interface to implement Deque. Apart from the basic standard operations of the Deque, this interface supports various other operations that can be carried out on Deque.

Deque is generally used for applications that require adding/removing elements from both the ends. It is also mostly used in the scheduling of processors in multi-processor systems.

=> Check Out The Complete C++ Training Series