C++ Tutorial Index

C++ Tutorial C++ History C++ Installation C++ First Program C++ cin and cout C++ Data type C++ Variable C++ operator C++ Keywords

C++ Control Statements

C++ If C++ Nested if C++ If-else C++ If-else-if C++ Switch C++ Break C++ Continue C++ Goto C++ For loop C++ While loop C++ Do while loop

C++ Functions

C++ Call by Value C++ Call by Reference C++ Recursion Function C++ Inline function C++ Friend function

C++ Arrays

Single dimension array Two dimension array

C++ Strings

C++ Strings

C++ Inheritance

C++ Inheritance Single level Inheritance Multilevel Inheritance Multiple Inheritance Hierarchical Inheritance Hybrid Inheritance

C++ Polymorphism

C++ Polymorphism C++ Overloading C++ Overriding C++ Virtual Function

C++ Pointers

C++ Pointers C++ this pointer

C++ Exception Handling

C++ Exception Handling

C++ Constructors

C++ Constructors Default Constructor Parameterize Constructor Copy constructor Constructor Overloading Destructor

C++ File Handling

C++ File Handling C++ Writing to file C++ Reading file C++ Close file

Miscellaneous

C Vs C++ C++ Comments C++ Data Abstraction C++ Identifier C++ Memory Management C++ Storage Classes C++ Void Pointer C++ Array To Function C++ Expressions C++ Features C++ Interfaces C++ Encapsulation std::min in C++ External merge sort in C++ Remove duplicates from sorted array in C++ Precision of floating point numbers Using these functions floor(), ceil(), trunc(), round() and setprecision() in C++ C++ References C++ Friend Functions C++ Mutable keyword Unary Operators in C++ Initialize Array of objects with parameterized constructors in C++ Differences between #define & const in C/C++ C++ Program to Implement Shell Sort C++ Program to Implement Merge Sort Storage Classes in C Vector resize() in C++ Passing by Reference Vs. Passing by the pointer in C++ Free vs delete() in C++ goto statement in C and C++ C++ program to read string using cin.getline() C++ String Concatenation Heap Sort in C++ Swap numbers in C++ Input Iterators in C++ Fibonacci Series in C++ C ++ Program: Alphabet Triangle and Number Triangle C++ Program: Matrix Multiplication C++ Program to Print Fibonacci Triangle Stack in C++ Maps in C++ Queue in C++ C++ Bitset C++ Algorithms Priority Queue in C++ C++ Multimap C++ Deque Function Pointer in C++ Sizeof() Operators in C++ C++ array of Pointers free() Vs delete in C Timsort Implementation Using C++ CPP Templates C++ Aggregation C++ Enumeration C++ Math Functions C++ Object Class C++ Queue Initialize Vector in C++ Vector in C++ C++ STL Components Function overloading in C++ C++ Maximum Index Problem C++ find missing in the second array C++ Program to find the product array puzzle C++ Program To Find Largest Subarray With 0 Sum C++ Program To Move All Zeros To The End Of The Array C++ Program to find the element that occurs once C++ Program to find the largest number formed from an array Constructor Vs Destructor C++ Namespaces C++ OOPs Concept C++ Static C++ Structs C++ Try-Catch C++ User Defined Exceptions C++ Virtual Destructor C++ vs C# Malloc() and new in C++ Palindrome Number Program in C++ Snake Code in C++ Splitting a string in C++ Structure Vs Class in C++ Virtual Function Vs Pure Virtual Function C++ Bidirectional Iterators C++ Forward Iterators C++ Iterators C++ Output Iterators C++ Range-based For Loop Converting string into integer in C++ LCM Program in C++ Type conversion in C++ Add two numbers using the function in C++ Advantage and disadvantage friend function C++ Armstrong Number Program in C++ ATM machine program in C++ using functions Binary to Decimal in C++ Bit Manipulation in C++ C++ Constructor C++ Dijkstra Algorithm Using the Priority Queue C++ int into String C++ Signal Handling Decimal to Binary in C++ Decimal to Hexadecimal in C++ Decimal to Octal in C++ Factorial Program in C++ Function in C++ Hexadecimal to Decimal in C++ Octal to Decimal in C++ Reverse a Number in C++ Structure Vs Class in C++ C++ Forward Iterators C++ Output Iterators C++ Prime number program Char Array to String in C++ Constructor Overloading in C++ Default arguments in C++ Different Ways to Compare Strings in C++ Dynamic Binding in C++ Program to convert infix to postfix expression in C++ SET Data Structure in C++ Upcasting and Downcasting in C++ Reverse an Array in C++ Fast Input and Output in C++ Delete Operator in C++ Copy elision in C++ C++ Date and Time C++ Bitwise XOR Operator Array of sets in C++ Binary Operator Overloading in C++ Binary Search in C++ Implementing the sets without C++ STL containers Scope Resolution Operator in C++ Smart pointers in C++ Types of polymorphism in C++

C++ Deque

Definition:

Deque or the Doubly ended queue is a data structure or operation performed under queue where insertion and deletion are allowed at both ends.

A deque is an ordered collection of items similar to that of a queue. It has a front, a rear and the items can be positioned from both ends allowing it to provide a hybrid linear structure with all the capabilities of stacks and queues in a single frame.

There are various operations performed on deque. The four common operations are:

  1. insertFront(): Front item is added in the deque.
  • insertLast(): Rear item is added in the deque.
  • deleteFront(): It deletes the first item from the deque.
  • deleteLast(): It deletes the last rear item from the deque.

There are still many additional functions associated with the deque. Some of them are listed below.

  1. getFront(): Fetches the first item from the deque.
  • getRear(): Fethes the last item from the deque.
  • isEmpty(): Checks for empty or existence.
  • isFull(): Checks whether the deque is full or not.

Let us now move forward with the implementation of the deque.

Deque is most commonly implemented using a doubly linked-list or a circular array. One advantage of this implementation is that both implementations take O(1) complexity.

Let us see coding examples to visualize the implementation techniques.

Example 1: Using Circular Array

 #include<bits/stdc++.h>
 using namespace std;
 #define MAX 100
 class Deque
 {
     int  arr[MAX];
     int  front;
     int  rear;
     int  size;
 public :
     Deque(int size)
   {
         front = -1;
         rear = 0;
         this->size = size;
     }
     void  insertfront(int key);
     void  insertrear(int key);
     void  deletefront();
     void  deleterear();
     bool  isFull();
     bool  isEmpty();
     int  getFront();
     int  getRear();
 };
 bool Deque::isFull()
 {
     return ((front == 0 && rear == size-1)||
             front == rear+1);
 }
 bool Deque::isEmpty ()
 {
     return (front == -1);
 }
 void Deque::insertfront(int key)
 {
     if (isFull())
   {
         cout << "Overflow condition\n" << endl;
         return;
    }
     if (front == -1)
  {
         front = 0;
         rear = 0;
  }
     else if (front == 0)
         front = size - 1 ;
         front = front-1;
     arr[front] = key ;
 }
 void Deque ::insertrear(int key)
 {
     if (isFull())
 {
         cout << " Overflow\n " << endl;
         return;
 }
     if (front == -1)
     {
         front = 0;
         rear = 0;
    }
     else if (rear == size-1)
         rear = 0;
     else
         rear = rear+1;
     arr[rear] = key ;
 }
 void Deque ::deletefront()
 {
     if (isEmpty())
  {
         cout << "Queue Underflow\n" << endl;
         return ;
  }
     if (front == rear)
  {
         front = -1;
         rear = -1;
  }
     else
         if (front == size -1)
             front = 0;
         else
             front = front+1;
 }
 void Deque::deleterear()
 {
     if (isEmpty())
     {
         cout << " Underflow\n" << endl ;
         return ;
    }
     if (front == rear)
   {
         front = -1;
         rear = -1;
   }
     else if (rear == 0)
         rear = size-1;
     else
         rear = rear-1;
 }
 int Deque::getFront()
 {
     if (isEmpty())
     {
         cout << " Underflow\n" << endl;
         return -1 ;
     }
     return arr[front];
 }
 int Deque::getRear()
 {
     if(isEmpty() || rear < 0)
    {
         cout << " Underflow\n" << endl;
         return -1 ;
    }
     return arr[rear];
 }
 int main()
 {
     Deque dq(5);
     cout << "Inserting element at rear : 5 \n";
     dq.insertrear(5);
     cout << "inserting element at rear : 10 \n";
     dq.insertrear(10);
     cout << "The rear end is now:  " << " "
          << dq.getRear() << endl;
     dq.deleterear();
     cout << "After deletion, value of rear end: "
          << " becomes " << dq.getRear() << endl;
     cout << "After inserting front end element:  \n";
     dq.insertfront(15);
     cout << "Front elemen now:  " << " "
          << dq.getFront() << endl;
     dq.deletefront();
     cout << "After deletion, front new "
        << "front becomes " << dq.getFront() << endl;
     return 0;
 } 

Output:

C++ Deque

Explanation:

The above code is an implementation of deque using the circular array. The following steps are followed:

Algorithm:

  1. Construct array 'arr' of size 'n'

Assign front = -1 , rear = 0

Inserting value in rear and front means the same in the deque.

After insertion operation:

Front = 0 and Rear = 0

Now, insert rear elements.

a). Check queue is full or not

b). IF Rear == Size-1

       Assign rear= 0 ;

Assign rear=rear+1;

Insert or push rear into Arr[ rear ] = key

The front remains the same.     

  • Inserting front element

a). Check if the deque is full or not.

b). IF Front == 0 or at starting position

            OR

 The front element points to the last, then

       front = size - 1

Else

   Decrement front by 1 and push the array.

The rear remains the same.

  • Delete Element From Rear end :

a). first Check deque is Empty or Not

b). If there is only one element in the deque

     Assign front = -1 ; rear =-1 ;

Else

Check if the front points to the last index or not.

If it points, it means the array has no elements.

Assign front =0;

    Else || increment Front by '1' 

            front = front+1;

Otherwise,

         Front=front+1;

There is another approach to implement deque which is done using a doubly linked-list. The approach is quite similar with some minor changes and those minor changes can be implemented using the following pseudo-code below.

Example 2: Using Double linked-list

 #include<iostream>
 using namespace std;
 class node
 {
     public:
         int data;
         node* next;
         node* prev;
 };
 class Dequey{
 public:
         node* newnode;
         node* temp;
         node* head;
         node* tail;
         int i,n;
     void create_node(){
         node* newnode = new node();
         cin>>newnode->data;
         newnode->next = NULL;
         newnode->prev = NULL;
  }
     void init(){
         head = NULL;
         tail = NULL;
         cout<<"Please enter the first node data"<<endl;
         create_node();
         head = newnode;
         tail = newnode;
 }
     void insertion_beg(){
         create_node();
         newnode->next = head;
         head->prev= newnode;
         head = head->prev;
     }
     void insertion_end(){
         create_node();
         newnode->prev = tail;
         tail->next = newnode;
         tail = tail->next;
     }
     void deletion_beg(){
         head = head->next;
   }
     void deletion_end(){
         tail = tail->prev;
         tail->next = NULL;
     }
     void display()
     {
         temp = head;
         while(temp != tail){
             cout<<temp->data<<" ";
             temp = temp->next;
         }
     }
 };
 int main(){
     Dequey d;
     int choice=0,flag=0;
     d.init();
 while(1)
 {
         cout<<endl<<"1. Insertion at Beginning \n2. Insertion at End \n3. Deletion at Beginning \n4. Deletion at End \n5. EXIT"<<endl;
         cin>>choice;
         if(choice==5)
             break;
         switch(choice)
 {
         case 1:
             d.insertion_beg();
             break;
         case 2:
             d.insertion_end();
             break;
         case 3:
             d.deletion_beg();
             break;
         case 4:
             d.deletion_end();
             break;
         case 5:
             flag = 1;
             break;
  }
   }
     d.display();
     return 0;
 } 

Output:

C++ Deque

Explanation:

The above code is the illustration of deque served with the Doubly linked list. We already know that in a Doubly linked-list, each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list.

Using this approach, we have assigned the switch cases so that the insertion and deletion can take place at the ends whenever the pointer points to the first link, then the second, and so on to the next node in the list. This ensures that irrespective of the differences in the memory addresses assigned, the links keep pointing consistently and store data with the help of those two links.



ADVERTISEMENT
ADVERTISEMENT