Updated March 20, 2023
What is Deque in C++?
Deque is a standard acronym for the double-ended queue which is basically a dynamic size sequence container. Dynamic size refers here for the contraction and expansion of a queue at both ends. It’s an alternative of vectors because it allows us to insert or delete elements at both front and back. Vector doesn’t provide this feature of insertion and deletion on both ends. Deque is basically an implementation of data structure. Double Ended Queue is more efficient and faster than any other queue when it comes to insertion and deletion of elements on both ends of any queue.
Syntax:
deque < object_type > deque_name ;The object type can be int, etc. then name as per your choice!
How Does a Deque Work in C++?
Now we will see how does a Deque actually work in the C++ programming language. Basically there are two classifications of deque:
- Output-Restricted Deque: In this classification, you can insert elements from both ends but deletion is only possible at the front end of the queue.
- Input-Restricted Deque: In this classification, you can delete elements from both the ends but insertion is only possible at the rear end of the queue.
For deque implementation in your code, we need to understand the basic member functions of the deque. Below are the functions we need to use:
1. push_back (element p): This member function of the deque allows a user to insert an element p at the end of the deque.
2. push_front (element p): This member function of the deque allows a user to insert an element p at the front of the deque.
3. insert(): This member function of the deque allows a user to insert an element in the deque. Where and how you want to insert is depend on the argument you are going to pass because this insert member function has three variations. Let’s have a look at them:
- Insert( iterator x, element p): This method allows a user to insert element p at the position pointed by iterator x in the deque.
- Insert( iterator x, int count, element p): This method allows a user to insert element p at the position pointed by iterator x in the deque while counting the number of times the position pointed by x in the deque.
- Insert( iterator x, iterator first, iterator last): This method allows a user to insert elements in the range of [first, last] at the position pointed by iterator x in the deque.
Example to Implement Deque in C++
As an example, we will see a C++ programming language code to implement the deque feature in our code.
Code:
#include<iostream>
using namespace std;
#define SIZE 10
class dequeue {
int a[20], fr ,re;
public:
dequeue();
void insert_starting(int);
void insert_ending(int);
void delete_front();
void ddelete_rear();
void display();
};
dequeue::dequeue() {
fr = -1;
re = -1;
}
void dequeue::insert_ending(int i) {
if ( re>=SIZE-1 ) {
cout << " \n insertion is not possible, overflow!!!! ";
} else {
if ( fr==-1 ) {
fr++;
re++;
} else {
re = re+1;
}
a[re] = i;
cout << " \nInserted item is " << a[re];
}
}
void dequeue::insert_starting(int i) {
if ( fr == -1 ) {
fr = 0;
a[++re] = i;
cout << " \n inserted element is: " << i;
} else if ( fr != 0 ) {
a[--fr] = i;
cout << " \n inserted element is: " << i;
} else {
cout << " \n insertion is not possible, overflow !!! ";
}
}
void dequeue::delete_front() {
if ( fr == -1 ) {
cout << " deletion is not possible :: dequeue is empty ";
return;
}
else {
cout << " the deleted element is: " << a[fr];
if ( fr == re ) {
fr = re = -1;
return;
} else
fr = fr+1;
}
}
void dequeue::ddelete_rear() {
if ( fr == -1 ) {
cout << " deletion is not possible::dequeue is empty ";
return;
}
else {
cout << " the deleted element is: " << a[re];
if ( fr == re ) {
fr = re = -1;
} else
re = re-1;
}
}
void dequeue::display() {
if ( fr == -1 ) {
cout << " Dequeue is empty ";
} else {
for ( int i = fr; i <= re; i++ ) {
cout << a[i]<< " ";
}
}
}
int main () {
int c,i;
dequeue d;
do{
cout << " \n 1.insert element at the beginning ";
cout << " \n 2.insert element at the end ";
cout << " \n 3.displaying the elements ";
cout << " \n 4.deletion of elements from front ";
cout << " \n 5.deletion of elements from rear ";
cout << " \n 6.exiting the queue ";
cout << " \n Please enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout << " Please enter the element to be inserted ";
cin>>i;
d.insert_starting(i);
break;
case 2:
cout << " Please enter the element to be inserted ";
cin >> i;
d.insert_ending(i);
break;
case 3:
d.display();
break;
case 4:
d.delete_front();
break;
case 5:
d.ddelete_rear();
break;
case 6:
exit(1);
break;
default:
cout << " invalid choice, Please enter valid choice ";
break;
}
} while (c!=7);
}Output:
First, it shows the number of choices to select.
Here we have enter 1 to add the element at the beginning. In the below snapshot, you can see that we added 3 as an element.
Then we select the second choice to enter the element at the end and added 6 at the end.
Then we chose the third choice to display the elements in the queue. It shows 3 and 6.
Then we enter the fourth choice to delete the element from the front.
Again we chose option 3 to check whether the element is deleted from the front or not. It shows only one element i.e 6. This means that the front element is deleted.
Then we chose 5 to delete the element from the rear.
Again we chose 3 to check whether the element is deleted from the queue or not. It shows that the dequeue is empty. Then we enter 6 to exit the queue.
Conclusion
In Conclusion, for operations involving insertion and deletion of elements frequently in your program at the beginning and end of the queue then Deque is the best feature you can use as it is faster and will help in making code perform faster. For log sequences, the deque performs better.
Recommended Articles
This is a guide to Deque in C++. Here we discuss how does a Deque work in C++ programming language with sample code to implement the deque feature in our code. You can also go through our other related articles to learn more –
