Use Deque in C++ STL

Reading time: 20 minutes

The deque in the STL of C++ is a dynamically resizing container to implement a double-ended queue data structure. Double ended queues are a special case of queues where insertion and deletion operations are possible at both the ends.

Definition in <deque>

std::deque is defined as follows under <deque> header file:

template <class T, class Allocator = std::allocator<T>> class deque;

Declaration

A deque with name a storing integers is declared as follows:

deque<int> a;

Functions

Assume deque a to be:

and deque b to be:

Some of the prominent functions under the <deque> header file are:

• a.size(): Returns an integer indicating the size of the deque a.

  For the above deque a, the function returns the integer 4.

• a.swap(b): Swaps the contents of priority queue a with priority queue b.

  For the above example, if the function is called, deque a becomes:

  and b becomes:

• a.push_back(x): Inserts the element x at the back of deque a.

  For the deque a, if the function a.push_back(6) is called, a becomes:

• a.push_front(x): Inserts the element x at the front of deque a.

  For the deque a, if the function a.push_front(6) is called, a becomes:

• a.pop_back(): Removes the element at the back of deque a.

  For the deque a, if the function a.pop_back() is called, a becomes:

• a.pop_front(): Removes the element at the front of deque a.

  For the deque a, if the function a.pop_front() is called, a becomes:

Note

• All pop and push operations are ```O(1)``` operations.

Illustration of Deque

#include <iostream> 
#include <deque> 
  
using namespace std; 
  
void display(deque <int> x) 
{ 
    deque <int> :: iterator it; 
    for (it = x.begin(); it != x.end(); ++it) 
        cout << ' ' << *it; 
    cout << '\n'; 
} 
  
int main() 
{ 
    deque<int> a; 
    a.push_back(10); 
    a.push_front(20); 
    a.push_back(30); 
    a.push_front(15); 
    cout << "The deque a is : "; 
    display(a); 
  
    cout << "\na.size() : " << a.size(); 
    cout << "\na.front() : " << a.front(); 
    cout << "\na.back() : " << a.back(); 
  
    cout << "\na.pop_front() : "; 
    a.pop_front(); 
    display(a); 
  
    cout << "\na.pop_back() : "; 
    a.pop_back(); 
    display(a); 
  
    return 0; 
} 

\\Console output
The deque a is :     15    20    10    30

a.size() : 4
a.front() : 15
a.back() : 30
a.pop_front() :     20    10    30

a.pop_back() :     20    10

Question