C++ Standard Template Library (STL) – [Deque]

Deque

Deque is a double-ended queue that provides dynamic resizing and efficient insertion and deletion of elements from both ends. It is implemented as a sequence container in the C++ Standard Template Library (STL) and provides constant time access to the beginning and end, as well as constant time random access to elements in the queue.

To use STL built-in deque, you need to include <deque> header.

Also read: C++ Standard Template Library (STL) – [Stack and Queue]

Member functions

Constructors
Deque provides several constructors to initialize its elements.

Usage

std::deque<int> d1;                         // Empty deque
std::deque<int> d2(5, 10);                  // Deque with 5 elements, each initialized to 10
std::deque<int> d3(d2.begin(), d2.end());   // Deque initialized from another deque's range
std::deque<int> d4 = {1, 2, 3, 4, 5};       // Deque initialized using initializer list

Access element
deque::at and deque::operator[]
Both at and operator[] are used to access elements at a specific position in the deque.

Usage
at performs bounds checking and throws an out_of_range exception if the specified position is out of bounds.
operator[] does not perform bounds checking and may lead to undefined behavior if the position is invalid.

std::deque<int> d = {1, 2, 3, 4, 5};
int x = d.at(2);      // Accesses element at index 2
int y = d[3];         // Accesses element at index 3

Insert/Remove element at beginning
deque::emplace_front, deque::push_front, deque::pop_front
These functions are used to add or remove elements from the front of the deque.

Usage
emplace_front constructs and inserts a new element at the beginning using forwarded arguments.
push_front inserts a copy of the given element at the beginning.
pop_front removes the element from the beginning.

std::deque<int> d = {2, 3, 4};
d.emplace_front(1);   // Adds 1 to the beginning
d.push_front(0);      // Adds 0 to the beginning
d.pop_front();        // Removes the first element (0)

Note: Forwarded arguments, also known as forwarding references, are a feature in C++ that enable perfect forwarding of arguments to another function. Using forwarding references enable efficient forwarding of arguments without unnecessary copies or moves.

Insert/Remove element at end
deque::emplace_back, deque::push_back, deque::pop_back
These functions are used to add or remove elements from the back of the deque.

Usage
emplace_back constructs and inserts a new element at the end using forwarded arguments.
push_back inserts a copy of the given element at the end.
pop_back removes the element from the end.

std::deque<int> d = {1, 2, 3};
d.emplace_back(4);   // Adds 4 to the end
d.push_back(5);      // Adds 5 to the end
d.pop_back();        // Removes the last element (5)

• push_back: Copies the provided element and inserts it at the end of the deque.
• emplace_back: Constructs the element in-place at the end of the deque using forwarded arguments, avoiding unnecessary copies.

Example

std::deque<std::string> d;
d.push_back("hello");        // Copies the string
d.emplace_back("world");     // Constructs the string in-place

Code Implementation

//
//  main.cpp
//  Deque
//
//  Created by Himanshu on 20/03/24.
//
 
 
#include <iostream>
#include <deque>
using namespace std;
 
int main () {
     
    deque<int> dq;
    deque<int> d1 = {1, 2, 3, 4, 5};
    deque<int> d2(5, 10);
     
    cout << "Enqueue(x) {10, 20, 30, 40, 50}" << endl;
    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);
    dq.push_back(40);
    dq.push_back(50);
 
    cout << "Deque-Empty(): ";
    if (dq.empty()) {
        cout << "Deque is empty" << endl;
    } else {
        cout << "Deque is not empty" << endl;
    }
     
    cout << "Access Deque Element at position 0: ";
    cout << dq.at(0) << endl;
    
    cout << "Access Deque Element at position 1: ";
    cout << dq[1] << endl;
    
    cout << "Dequeue() elements from front..." << endl;
    while (!dq.empty()) {
        cout << dq.front() << " ";
        dq.pop_front();
    }
    cout << endl << endl;
     
    cout << "Dequeue() (d1) elements from back..." << endl;
    while (!d1.empty()) {
        cout << d1.back() << " ";
        d1.pop_back();
    }
    cout << endl;
    
    cout<<"Deque-Empty(): ";
    if (d1.empty()) {
        cout << "Deque is empty" << endl;
    } else {
        cout << "Deque is not empty" << endl;
    }
     
    return 0;
}

Output

Enqueue(x) {10, 20, 30, 40, 50}
Deque-Empty(): Deque is not empty
Access Deque Element at position 0: 10
Access Deque Element at position 1: 20
Dequeue() elements from front...
10 20 30 40 50 

Dequeue() (d1) elements from back...
5 4 3 2 1 
Deque-Empty(): Deque is empty