Deque in C++

In this tutorial we will learn how we can implement dequeue with C++. We will learn step by step to create a basic dequeue structure and other methods provided by dequeue to perform various functions.

Create Deque in C++:

Step 1: At first we need to include the necessary header file:

#include <iostream>
#include <deque>

Step 2: Then we declare a deque object:

deque<int> myDeque;

Step 3: Add elements to the deque:

myDeque.push_back(10);  // Add 10 to the back of the deque
myDeque.push_front(5);  // Add 5 to the front of the deque
myDeque.push_back(15);  // Add 15 to the back of the deque

Step 4: Print the deque after performing operations:

for (const auto& element : myDeque) {
   \cout << element << " ";
}
cout << endl;

In this loop, the variable num is declared as an int, which will be used to iterate over each element in the myDeque deque. For each iteration of the loop, the value of the current element is assigned to the variable num, and the statement std::cout << num << ", "; is executed. The loop continues until all elements in myDeque have been traversed. For example, if the deque contains the elements [10, 5, 15], the output would be 10, 5, 15.

#include <iostream>
#include <deque>

using namespace std;

int main() {
   deque<int> myDeque;

    myDeque.push_back(10);
    myDeque.push_front(5);
    myDeque.push_back(15);


cout << "the deque is: ";
    for (int num : myDeque) {
    cout << num << ", ";
  }

    cout << endl;

    return 0;
}

Output:

the deque is: 5, 10, 15 

Functions in Deque:

There are some functions in Deque which provide essential operations to manipulate and access elements in a deque. These are described below:

Insertion in Deque:

We can insert elements in deque using the following functions:

C++ implementation:

#include <iostream>
#include <deque>
using namespace std;


int main() {
   deque<int> myDeque;

    // Using push_back() to insert elements at the end
    myDeque.push_back(10);
    myDeque.push_back(20);
    myDeque.push_back(30);

    // Using push_front() to insert elements at the beginning
    myDeque.push_front(5);
    myDeque.push_front(2);
    myDeque.push_front(1);

cout<<"the deque is: ";
    // Printing the elements of the deque
    for (const auto& element : myDeque) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

Output:

the deque is: 1 2 5 10 20 30 

In this example using the push_back() function, the elements 10, 20, and 30 are inserted at the end of the deque. This means they will be placed at the back.

Using the push_front() function, the elements 5, 2, and 1 are inserted at the beginning of the deque. This means they will be placed at the front.

Removing elements in Deque

We can remove elements in deque using the following functions:

C++ implementation:

#include <iostream>
#include <deque>
using namespace std;


int main() {
   deque<int> myDeque;

    myDeque.push_back(10);
    myDeque.push_front(5);
    myDeque.push_back(15);

    std::cout << "Original deque: ";
    for (const auto& element : myDeque) {
        cout << element << " ";
    }
   cout << std::endl;

    myDeque.pop_back();
    myDeque.pop_front();

    std::cout << "Updated deque after pop_back() and pop_front(): ";
    for (const auto& element : myDeque) {
        cout << element << " ";
    }
   cout << endl;

    return 0;
}

Output:

Original deque: 5 10 15 
Updated deque after pop_back() and pop_front(): 10 

In this example, we create a deque (myDeque) and add elements 10, 5, and 15 using push_back() and push_front() functions. Then, we print the original deque.

Next, we use pop_back() to remove the last element (15) from the deque, and pop_front() to remove the first element (5) from the deque. Finally, we print the updated deque after performing the operations.

Accessing elements in Deque

We can access elements in deque using the following functions:

C++ implementation:

#include <iostream>
#include <deque>
using namespace std;

int main() {
  deque<int> myDeque;
    
    myDeque.push_back(10);
    myDeque.push_back(20);
    myDeque.push_back(30);

    // Accessing the first element using front()
    int firstElement = myDeque.front();
    cout << "First element: " << firstElement <<endl;

    // Accessing the last element using back()
    int lastElement = myDeque.back();
    cout << "Last element: " << lastElement << endl;

    // Accessing an element at a specific index using at()
    int index = 1;
    int elementAtIndex = myDeque.at(index);
   cout << "Element at index " << index << ": " << elementAtIndex <<endl;

    return 0;
}

Output:

First element: 10
Last element: 30
Element at index 1: 20

Finding size of Deque

We can find size of the Deque in folowing way:

C++ implementation:

#include <iostream>
#include <deque>
using namespace std;



int main() {
   deque<int> myDeque;

    myDeque.push_back(10);
    myDeque.push_front(5);
    myDeque.push_back(15);

   cout << "Size of the deque: " << myDeque.size() << endl;

    return 0;
}

Output:

Size of the deque: 3

In this example, we create a deque (myDeque) and add elements 10, 5, and 15 using push_back() and push_front() functions. Then, we use the size() function to determine the size of the deque.

Checking if the deque is empty

C++ implementation:

#include <iostream>
#include <deque>
using namespace std;


int main() {
    deque<int> myDeque;

    myDeque.push_back(10);
    myDeque.push_front(5);
    myDeque.push_back(15);

    if (myDeque.empty()) {
        cout << "The deque is empty." << endl;
    } else {
        cout << "The deque is not empty." << endl;
    }

    return 0;
}

Output:

The deque is not empty.

In this example, we create a deque (myDeque) and add elements 10, 5, and 15 using push_back() and push_front() functions. Then, we use the empty() function to check if the deque is empty. The output indicates that the deque is not empty, as it contains elements. 

Time Complexity: