What is std::deque and how Deque works Internally.

Deque :

Double-ended queues are sequence containers that can expand and contract on both ends.
They are similar to vectors but more effective in terms of element insertion and deletion. Contiguous capacity allocation, unlike vectors, can not be guaranteed.
Double Ended Queues are essentially a data structure implementation of the double ended queue. A queue data structure only allows insertion at the end and deletion from the beginning. This is similar to a real-life queue in which people are transferred from the front to the back. Double-ended queues are a type of queue that allows insertion and deletion operations at both ends.

In this article, we will define a deque and explain how it functions internally.

Header file:

#include <deque>

1)Adding element in front of deque

We can insert element in front of deque by using push_front.

Syntax:

given_deque.push_front(ele);

The element ele is added to the front of the deque.

Examples:

sampledeque.push_front(12);

sampledeque.push_front(73);

2)Adding element in back of deque

We can insert element in back of deque by using push_back.

Syntax:

given_deque.push_back(ele);

The element ele is added to the back/end of the deque.

Examples:

sampledeque.push_back(12);

sampledeque.push_back(73);

3)Deleting element in front of deque

We can delete element in front of deque by using pop_front.

Syntax:

given_deque.pop_front(ele);

The element ele is deleted to the front of the deque.

Examples:

sampledeque.pop_front(12);

sampledeque.pop_front(73);

4)Deleting element in back of deque

We can delete element in back of deque by using pop_back.

Syntax:

given_deque.pop_back(ele);

The element ele is deleted to the back/end of the deque.

Examples:

sampledeque.pop_back(12);

sampledeque.pop_back(73);

5)Internal Working of Deque

A deque is typically implemented as a series of memory blocks. These memory blocks store the elements in contiguous locations.

When we build a deque entity, it internally allocates a memory block to store the elements in contiguous locations.

When we insert an element at the end, it stores it in the allocated memory block until it is complete, at which point it allocates a new memory block and connects it to the end of the previous memory block. This new memory block now stores any additional inserted elements in the back.
When we insert an element in front, a new memory block is allocated and linked to the front of the previous memory block. Further elements placed in the front are now stored in this new memory block until it is complete.
Consider deque a linked list of vectors i.e. each node of that linked list is a storage block which stores elements in the memory and links each of them with its previous and next memory block nodes. The deque is a linked list of vectors.

As a result, insertion at front is faster than vector because it does not require the elements in the current memory block to move by one to create room at front. It simply checks to see if there is any space to the left of the first element in the current memory block, and if not, it allocates a new memory block.

Below is the implementation:

#include <bits/stdc++.h>
#include <deque>
using namespace std;
int main()
{ // creating  a deque
    deque<int> sample_deque;
    // adding elements to back of deque
    sample_deque.push_back(23);
    sample_deque.push_back(67);
    // printing the elements of deque
    for (int i = 0; i < sample_deque.size(); i++)
        cout << sample_deque[i] << " ";
    cout << endl;
    // adding elements to front of deque
    sample_deque.push_front(47);
    sample_deque.push_front(72);
    // printing the elements of deque
    for (int i = 0; i < sample_deque.size(); i++)
        cout << sample_deque[i] << " ";
    cout << endl;
    // deleting element from back of deque
    sample_deque.pop_back();
    // printing the elements of deque
    for (int i = 0; i < sample_deque.size(); i++)
        cout << sample_deque[i] << " ";
    cout << endl;
    // deleting element from front of deque
    sample_deque.pop_front();
    // printing the elements of deque
    for (int i = 0; i < sample_deque.size(); i++)
        cout << sample_deque[i] << " ";
    cout << endl;
    return 0;
}

Output: