C++ Deque

In C++, the deque, short for Double-Ended Queue, functions as a type of queue where elements are insertable and removable from both the front and the back. This data structure caters to both First-In-First-Out (FIFO) and Last-In-First-Out (LIFO) operations, providing a more versatile alternative to traditional queues. Within the realm of C++, the STL deque is recognized as a linear container that enables the swift addition and elimination of elements at both ends of the queue.

Unlike a standard queue that restricts insertion to the back and removal from the front, a deque offers greater versatility with operations possible at both ends. Additionally, it facilitates element retrieval through index positions, making it well-suited for situations requiring random access and resizing on the fly. To utilize a deque container, the inclusion of the \<deque\> header file is essential.

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's consider a scenario to demonstrate the deque data structure 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 instance, we establish a deque containing integers with an initial set of six elements: {7, 8, 5, 1, 2, 9}. Employing a range-based for loop, the program traverses the deque and displays each element with spaces in between. Subsequently, the deque offers rapid insertions and removals from both ends, enhancing its versatility compared to arrays or vectors in specific situations.

Basic operations on Deque

Various actions are carried out on a deque in C++. A few of these include:

1) Creating and Inserting Elements in a Deque:

In declaring a deque, you will utilize the deque keyword followed by the data type enclosed in angle brackets (< >), along with the chosen variable identifier. The Standard Template Library (STL) includes the deque as a data structure that facilitates rapid additions and removals at both the front and back ends.

In C++ deque, we have the ability to add and remove elements at both ends by utilizing the pushback and pushfront functions. When there is a need to insert an element at a particular position within the deque, the insert method can be employed.

Example of Creating and Inserting Element on Deque

Let's consider an example to generate and add elements to a deque container 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 instance, we are demonstrating the utilization of the pushfront method to add a value at the start and the pushback method to add a value at the end. Following this, the emplacefront and emplaceback functions perform similarly to pushfront and pushback, but they offer greater efficiency when adding temporary or constructed values directly.

2) Accessing the Elements in a Deque

Deque elements can be directly accessed using index notation represented by square brackets. Deques follow a 0-indexed system where the initial element is at index 0, the subsequent element is at index 1, and so forth. This feature enables efficient and effortless retrieval of elements from specific positions in the container. Additionally, deques provide the front and back functions for convenient access to the initial and final elements in the sequence.

Example of Accessing the Elements in a Deque

Now, let's examine a C++ illustration of retrieving 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 instance, we create a deque named socialmedia_apps that holds a collection of social networking app names and illustrates retrieving its elements using index notation, front, back, and the at method. Subsequently, it showcases each available item in the console.

3) Modifying the Deque Element

To modify the value of a particular element within a deque, you can utilize square brackets along with the at method. These functionalities provide a direct pathway to both the position of an element and the ability to substitute its value. Although the operator enables quicker access, the at method ensures greater safety by conducting boundary validations and raising an exception when the index exceeds the valid range.

Example of Modifying the Deque Element

Now, let's examine a C++ illustration of altering 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 instance, we create a deque containing names of fruits by employing the index access operator as well as the at method. Subsequently, we add "Banana" to the front and "Grapes" to the rear of the deque.

4) Removing Elements from a Deque

In C++, the deque data structure enables efficient removal operations from both the front and back of the queue. To eliminate the element at the front, the popfront method is employed, whereas for the element at the rear, the popback function is utilized. These methods effectively erase the specific elements without any return value.

Example of Removing Elements from a Deque

Now, let's examine a C++ illustration of deleting 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 instance, we illustrate the usage of a deque to manage a queue for servicing car brands. Subsequently, it displays the entirety of the items in the queue prior to eliminating the initial and final entries by employing popfront and popback.

5) Deque Size

In C++, the size function provides the count of elements currently stored in a deque container. This operation has a constant time complexity and is beneficial for monitoring queue size. It plays a crucial role in controlling logic, facilitating iteration, and reporting status in practical software implementations.

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 serves as a demonstration of a patient lineup at a medical facility. The.size method reveals the current number of patients in the queue.

6) Check if a Deque is Empty

In C++, the empty function checks if a deque container holds any elements. It outputs true (1) for an empty deque and false (0) if it has elements. This function proves beneficial in situations that require immediate actions, like task execution, user interaction handling, and queue administration, only when the container is not empty.

C++ Example to Check if a Deque is Empty

Now, let's examine a C++ illustration of verifying whether a deque is devoid of elements.

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 instance, a new deque named returnbox is instantiated as empty, and the empty method is employed to verify its element count. A message is displayed based on whether the return box holds any books.

7) Looping Through a Deque

A loop is employed to fetch and handle each item in a deque. The index-driven loop enables access based on position and is suitable when the exact element positions are crucial. On the other hand, the range-based for-each loop (introduced in C++11) enhances readability and is beneficial when the focus is solely on the elements.

Example of looping through a Deque

Now, let's examine a C++ illustration of iterating over 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 instance, we are generating a deque that holds a collection of medications. Initially, it displays the medicine timetable by utilizing an index-oriented for loop to retrieve elements by their positions. Following that, it showcases the identical list using a more streamlined for-each loop, which directly iterates through the elements.

C++ Deque Functions

The following table outlines various functions of Deque responsible for executing operations in C++.

Other Common Operations on Deque

Additional typical operations performed on a Deque in C++ include:

C++ Deque Iterators

In C++, the deque container enables the use of random-access iterators. These iterators have the capability to reference elements within the deque, allowing for traversal, modification, and access to elements in a manner similar to what is seen in a vector.

Syntax

Syntax for Declaring a Deque Iterator:

deque<type>::iterator iterator_name;

C++ Deque Iterators Example

Now, let's examine a C++ illustration showcasing 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 instance, we start by creating a deque that stores temperatures as double values. We then define an iterator, denoted as q, to move through the deque using a for loop. As we iterate through the deque, each temperature is displayed along with the symbol "°C" indicating Celsius.

Accessing Elements using Deque Iterators

Deque iterators offer access to elements by referencing memory locations. These iterators can be repositioned anywhere using arithmetic operations (like begin + i) and the element can be retrieved by dereferencing with *.

Example of Accessing Elements using Deque Iterators

Now, let's explore a C++ illustration of accessing elements through 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 instance, a deque containing integer IDs is established to access particular elements using the iterator q. It retrieves the initial, second, and final IDs by assigning the iterator to the correct positions through begin and end functions.

Time Complexity

The chart provided illustrates the time complexity of various operations executed on a 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