C++ Deque

In C++, the deque (Double-Ended Queue) is a queue in which elements can be added and removed from the front and back. It supports both FIFO and LIFO operations, which offers greater flexibility than queues. In C++ , the STL deque is a sequential container that allows for efficient insertion and deletion of elements from both the front and back.

Unlike a regular queue , which only allows for insertion at the back and removal from the front, a deque provides more flexibility by enabling operations at both ends. It also allows element access using index positions, which makes it suitable for scenarios where random access and dynamic resizing are necessary. If we want to work with a deque container, we have to include a <deque> header file.

Syntax

It has the following syntax:

deque<object_type> deque_name;

In this syntax,

• ✅ objecttype: The objecttype parameter determines the type of components that the deque will store, such as int, string, and custom class.
• ✅ deque_name: It represents the name of the identifier and variable that is assigned to deque.
• ✅ ;: It ends the statement according to C++ syntax instructions.

Simple C++ Deque Example

Let us take an example to illustrate the deque in C++.

Example

#include <iostream>

#include <deque>  //using deque header file

using namespace std; //using standard namespace

int main() {  //Main Function

    

    // Creating a deque of 5 elements

    deque<int> dq = {7, 8, 5, 1, 2, 9};

    

    for (auto a: dq)

        cout << a << " "; //prints the deque elements

    return 0;

}

Output:

7 8 5 1 2 9

Explanation

In this example, we create a deque of integers initialized with six elements: {7, 8, 5, 1, 2, 9}. Using a range-based for loop, it iterates through the deque and prints each element separated by a space. After that, the deque allows fast insertions and deletions from both ends, which makes it more flexible than arrays or vectors in certain scenarios.

Basic operations on Deque

Several operations are performed on deque in C++. Some of them are as follows:

1) Creating and Inserting Elements in a Deque:

In order to declare a deque, use the deque keyword followed by the data type wrapped in angle brackets (< >), and the variable name. The Standard Template Library (STL) provides the deque as a container that enables fast insertions and deletions at both ends.

In C++ deque, we can perform the insertion and deletion operation at either end using the pushback and pushfront functions. If we want to insert an element at a specific position, we can use the insert method.

Example of Creating and Inserting Element on Deque

Let us take an example to create and insert elements on deque in C++.

Example

#include <iostream>

#include <deque>  // for deque container

using namespace std;  //using standard namespace

int main() {  //main function

    // Creating an empty deque of integers

    deque<int> dq;

    // Inserting elements at the back

    dq.push_back(15);

    dq.push_back(18);

    // Inserting elements at the front

    dq.push_front(7);

    dq.push_front(5);

    // Using emplace_back

    dq.emplace_back(27);

    // Using emplace_front

    dq.emplace_front(1);

    cout << "Deque elements are: ";  //Print the deque elements

    for (int a : dq) {

        cout << a << " ";

    }

    return 0;

}

Output:

Deque elements are: 1 5 7 15 18 27

Explanation

In this example, we have taken the pushfront function to insert the value at the beginning and the pushback function to insert the value at the end. After that, the emplacefront and emplaceback function acts the same as pushfront and pushback functions, but it is more efficient to insert temporary or constructed values directly.

2) Accessing the Elements in a Deque

The elements of a deque can be accessed directly with index notation, which contains square brackets. Deques are 0-indexed, which means that the first element is at index 0, the second is at index 1, and so on. It allows for quick and easy retrieval of elements from particular positions within the container. It also offers the front and back methods to easily access the first and last element from the list.

Example of Accessing the Elements in a Deque

Now, let's look at a C++ example of accessing the elements in a deque.

Example

#include <iostream>

#include <deque>

using namespace std;

int main() 

{

deque<string> socialmedia_apps = {"Snapchat", "Twitter", "Whatsapp", "Instagram"};

    cout << "App at index 0 is: " << socialmedia_apps[0] << endl;

    cout << "App at index 1 is: " << socialmedia_apps[1] << endl;

    cout << "The first app (front) is: " << socialmedia_apps.front() << endl;

    cout << "The last app (back) is: " << socialmedia_apps.back() << endl;

    cout << "App at index 2 (using at()) is: " << socialmedia_apps.at(2) << endl;

    cout << "App at index 3 (using at()) is: " << socialmedia_apps.at(3) << endl;

    return 0;

}

Output:

App at index 0 is: Snapchat

App at index 1 is: Twitter

The first app (front) is: Snapchat

The last app (back) is: Instagram

App at index 2 (using at()) is: Whatsapp

App at index 3 (using at()) is: Instagram

Explanation

In this example, we generate a deque named socialmedia_apps that contains a list of social media application names and demonstrates how to get its contents using index notation, front, back, and the at method. After that, it displays each accessible element in the console.

3) Modifying the Deque Element

In order to change the value of a specific element in a deque, use its index wrapped in square brackets and the at method. These functions offer direct access to an element's location and value replacement. While operator allows for speedier access, but the at function is more secure because it performs bounds checks and throws an exception if the index is outside of range.

Example of Modifying the Deque Element

Now, let's look at a C++ example of modifying the deque element.

Example

#include <iostream>

#include <deque>

using namespace std;

int main() 

{

    deque<string>names_of_fruits = {"Mango", "Apple", "Watermelon", "Musk melon"};

    names_of_fruits[0] = "Pomegranate";

    names_of_fruits.at(1) = "Custard Apple";

    names_of_fruits.push_front("Banana");

    names_of_fruits.push_back("Grapes");

    names_of_fruits.pop_front();

    names_of_fruits.pop_back();

    cout << "Updated list of the Fruitnames:\n";

    for (const string& a : names_of_fruits) 

    {

        cout << a << endl;

    }

    return 0;

}

Output:

Updated list of the Fruitnames:

Pomegranate

Custard Apple

Watermelon

Musk melon

Explanation

In this example, we initialize a deque with fruit names using the index access operator and the at function. After that, we insert the "Banana" at the front and "Grapes" to the at the back of the deque.

4) Removing Elements from a Deque

In C++, the deque container allows efficient removal operations from both the front and back of the queue. The popfront function is used to remove the element at the front, while the popback function is used to remove the element at the rear. These functions permanently delete the respective elements without returning them.

Example of Removing Elements from a Deque

Now, let's look at a C++ example of removing elements from a deque.

Example

#include <deque>

#include <iostream>

#include <string>

int main() 

{

    std::deque<std::string> s = {

        "Volvo", "BMW", "Ford", "Mazda"

    };

    std::cout << "The Service Queue elements are:\n";

    for (const auto& request: s)

    {

        std::cout << request << std::endl;

    }

    s.pop_front();  

    s.pop_back();   

    std::cout << "The updated Service Queue elements are:\n";

    for (const auto& request: s) 

    {

        std::cout << request << std::endl;

    }

    return 0;

}

Output:

The Service Queue elements are:

Volvo

BMW

Ford

Mazda

The updated Service Queue elements are:

BMW

Ford

Explanation

In this example, we demonstrate how to utilize a deque to handle a car brand service queue. After that, it shows all of the elements in the queue before removing the first and last entries using popfront and popback.

5) Deque Size

In C++, the size method returns the number of elements currently contained in a deque container. It is a constant-time operation that helps in queue size monitoring, which is useful for logic control, iteration, and status reporting in real-world applications.

Example of Deque Size:

Now, let's look at a C++ example of deque size.

Example

#include <iostream>

#include <deque>

using namespace std;  //using standard namespace

int main()   //Main Function

{

    deque<string> patients_names = {"John", "Joseph", "Jacob", "Charles"};

    cout << "Number of patients waiting: " << patients_names.size() << endl;

    return 0;

}

Output:

Number of patients waiting: 4

Explanation

This is an example of a patient queue at a clinic. The.size function indicates how many patients are currently waiting.

6) Check if a Deque is Empty

In C++, the empty method determines whether or not a deque container contains any elements. It returns true (1) if the deque is empty and false (0) if it contains at least one element. It is useful in real-time scenarios where operations, such as task processing, user input response, and queue management, should only occur if the container contains data.

C++ Example to Check if a Deque is Empty

Now, let's look at a C++ example of checking if a deque is empty.

Example

#include <iostream>

#include <deque>

using namespace std;  //using standard namespace

int main()   //main function

{

    deque<string> returnbox;

    if (returnbox.empty()) 

        cout << "No books have been returned yet.\n";

    else 

        cout << "There are books in the return box.\n";

    return 0;

}

Output:

No books have been returned yet.

Explanation

In this example, we creates an empty deque named returnbox and uses empty function to check if it contains any elements. It prints a message depending on whether the return box contains books or not.

7) Looping Through a Deque

A loop is used to retrieve and process each element in a deque. The index-based loop allows for position-based access and is appropriate when element positions are critical. The range-based for-each loop (added in C++11) is more readable and useful when the attention is only on the elements themselves.

Example of looping through a Deque

Now, let's look at a C++ example of looping through a deque.

Example

#include <iostream>

#include <deque>

#include <string>

using namespace std;  //using standard namespace

int main()   //Main Function

{

deque<string> medicines = {"Aspirin", "Vitamin D", "Antibiotic", "Cough Syrup"};

    cout << "Medication Schedule - (using an index-based loop):\n";

    for (int i = 0; i < medicines.size(); i++) 

    {

        cout << medicines[i] << endl;

    }

    cout << "Medication Schedule - (using a for-each loop):\n";

    for (const string& med : medicines) 

    {

        cout << med << endl;

    }

    return 0;

}

Output:

Medication Schedule - (using an index-based loop):

Aspirin

Vitamin D

Antibiotic

Cough Syrup

Medication Schedule - (using a for-each loop):

Aspirin

Vitamin D

Antibiotic

Cough Syrup

Explanation

In this example, we create a deque containing a list of medicines. It first prints the medication schedule using an index-based for loop that accesses elements based on position. After that, it outputs the same list with a cleaner for-each loop that iterates directly over the elements.

C++ Deque Functions

The table below shows the several functions of Deque that perform operations in C++.

Other Common Operations on Deque

Some other common operations on Deque in C++ are as follows:

C++ Deque Iterators

In C++, the deque container supports random-access iterators. These iterators can point to elements within the deque and provide traversal, modification, and access to elements the same as those found in a vector.

Syntax

Syntax for Declaring a Deque Iterator:

deque<type>::iterator iterator_name;

C++ Deque Iterators Example

Now, let's look at a C++ example of deque iterators.

Example

#include <iostream>

#include <deque>

using namespace std;

int main() 

{

    deque<double> temperatures = {36.5, 37.0, 36.8, 37.2, 36.9};

    deque<double>::iterator q;

    cout << "Temperatures of the day:\n";

    for (q = temperatures.begin(); q!= temperatures.end(); ++q) 

    {

        cout << *q << "°C" << endl;

    }

    return 0;

}

Output:

Temperature log for the day:

36.5°C

37°C

36.8°C

37.2°C

36.9°C

Explanation

In this example, we initialize a double-valued deque containing daily temperature information. An iterator q is defined and used to traverse the deque, accessing each element through a for loop. During traversal, each temperature value is printed with the "°C" sign to denote degrees Celsius.

Accessing Elements using Deque Iterators

Deque iterators provide access to elements by pointing to memory locations. The iterator can be moved to any place using arithmetic (such as begin + i) and dereferenced using * to retrieve the value.

Example of Accessing Elements using Deque Iterators

Now, let's look at a C++ example of accessing elements using deque iterators.

Example

#include <iostream>

#include <deque>

using namespace std;

int main() 

{

    deque<int> IDs = {11, 12, 13};

    deque<int>::iterator q;

    q = IDs.begin();

    cout << "First ID: " << *q << endl;

    q = IDs.begin() + 1;

    cout << "Second ID: " << *q << endl;

    q = IDs.end() - 1;

    cout << "Last ID: " << *q << endl;

    return 0;

}

Output:

First ID: 11

Second ID: 12

Last ID: 13

Explanation

In this example, we create a deque of integers that represent IDs and accesses specific elements using the iterator q. It produces the first, second, and last IDs by allocating the iterator to the appropriate positions using begin and end.

Time Complexity

The table below shows the time complexity of several operations performed on deque.

C++ Deque MCQS

1) Which header file is required to use deque in C++?

• ✅ <vector>
• ✅ <deque>
• ✅ <array>
• ✅ <list>

2) What is the time complexity of inserting an element at the front of a deque?

• ✅ O(1)
• ✅ O(n)
• ✅ O(log n)
• ✅ O(n log n)

3) Which function is used to remove the last element of a deque?

• ✅ remove_back
• ✅ delete_back
• ✅ pop_back
• ✅ erase_back

4) What does deque<int>::iterator represent?

• ✅ An object
• ✅ A pointer
• ✅ An algorithm
• ✅ An iterator for integer deque

5) Which of the following is true about deque?

• ✅ It only supports push and pop at the back
• ✅ It is implemented using arrays only
• ✅ It supports random access iterators
• ✅ It is slower than the list for insertion