Deque in C++ STL

Double ended queues are sequence containers with the feature of expansion and contraction (fast insertion and deletion) on both the ends.
Double Ended Queues are basically an implementation of the data structure double ended queue.
Although we can also use vector container for the insertion and deletion at both of its ends, but insertion and deletion at the front of the array is costlier than at the back because it has a contiguous storage allocation.
deques are a little more complex internally than vectors, but this allows them to grow more efficiently under certain circumstances, especially with very long sequences, where reallocations become more expensive.

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.

Deque Operations

Iterators:
begin : Return iterator to beginning (public member function )
end : Return iterator to end (public member function )
rbegin : Return reverse iterator to reverse beginning (public member function )
rend : Return reverse iterator to reverse end (public member function )
cbegin : Return const_iterator to beginning (public member function )
cend : Return const_iterator to end (public member function )
crbegin : Return const_reverse_iterator to reverse beginning (public member function )
crend : Return const_reverse_iterator to reverse end (public member function )

Capacity:
size : Return size (public member function )
max_size : Return maximum size (public member function )
resize : Change size (public member function )
empty : Test whether container is empty (public member function )
shrink_to_fit : Shrink to fit (public member function )

Element access:
operator[] : Access element (public member function )
at : Access element (public member function )
front : Access first element (public member function )
back : Access last element (public member function )

Modifiers:
assign : Assign container content (public member function )
push_back : Add element at the end (public member function )
push_front : Insert element at beginning (public member function )
pop_back : Delete last element (public member function )
pop_front : Delete first element (public member function )
insert : Insert elements (public member function )
erase : Erase elements (public member function )
swap : Swap content (public member function )
clear : Clear content (public member function )
emplace : Construct and insert element (public member function )
emplace_front : Construct and insert element at beginning (public member function )
emplace_back : Construct and insert element at the end (public member function )

Allocator:
get_allocator : Get allocator (public member function )

Deque Representation

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.

// program to show the working of some functions of deque
#include <iostream>
#include <deque>
using namespace std;
void showdq(deque <int> dq)
{
	deque <int> :: iterator it;
	for (it = dq.begin(); it != dq.end(); ++it)
		cout << '\t' << *it;
	cout << '\n';
}

int main()
{
	deque <int> tsp_dq;
	tsp_dq.push_back(10);
	tsp_dq.push_front(20);
	tsp_dq.push_back(30);
	tsp_dq.push_front(15);
	cout << "The deque tsp_dq is : ";
	showdq(tsp_dq);
	cout << "\ntsp_dq.size() : " << tsp_dq.size();
	cout << "\ntsp_dq.max_size() : " << tsp_dq.max_size();
	cout << "\ntsp_dq.at(2) : " << tsp_dq.at(2);
	cout << "\ntsp_dq.front() : " << tsp_dq.front();
	cout << "\ntsp_dq.back() : " << tsp_dq.back();
	cout << "\ntsp_dq.pop_front() : ";
	tsp_dq.pop_front();
	showdq(tsp_dq);
	cout << "\ntsp_dq.pop_back() : ";
	tsp_dq.pop_back();
	showdq(tsp_dq);
	return 0;
}

/*
Output : 
The deque tsp_dq is :     15    20    10    30

tsp_dq.size() : 4
tsp_dq.max_size() : 4611686018427387903
tsp_dq.at(2) : 10
tsp_dq.front() : 15
tsp_dq.back() : 30
tsp_dq.pop_front() :     20    10    30

tsp_dq.pop_back() :     20    10
*/