C++

C++ Deque Function

The Standard Template Library (STL) also provides a class called “deque” that implements all the functionalities for this data structure. A sequential container that functions as a double-ended queue data structure in C++ is called the STL deque.

Elements are often added from the back and removed from the front in a normal queue. In contrast, we can add and remove the components from the front and back of a deque. The implementation of a deque in C++ can be done using either an array or a linked list.

Below is a list of the deque’s array implementation. We utilized the circular arrays to implement it because it is a double-ended queue. The double-ended queue is faster and more efficient than any other queue when it comes to adding and removing the components from both ends.

Deque’s representation

The time-consuming aspects of doing various deque processes include:

  • Getting at Elements: O (1)
  • Element addition or deletion- O (N)
  • Addition or deletion of components at the beginning of the end- O (1)

Types of Deque

Let’s check out the types related to deque in C++.

Input Restricted Deque

Input is confined at one end but allowed at the other two.

Output Restricted Deque

In this deque, the output is prohibited at one end, but insertion is permitted at both ends.

Creating C++ Deque Function

We must first include the deque header file to generate a deque in C++.

#include <deque>

After importing this file, the following syntax can be used to generate a deque:

# Deque<object-type> deque-name;

The data type that we would like to store in the deque is indicated by object-type in this case. For example: int, float, string, etc. Deque-name is a variable name for the data that we are going to use.

Initializing Deque Function

In C++, the Deque function can be initialized in the following ways:

deque<int> arr={1, 3, 7, 0, 5, 8};

deque<int> arr {1, 3, 7, 0, 5, 8};

Both of these methods are used to initialize deque. In both of these deque names, “arr” is initialized with integer values 1, 3, 7, 0, 5, 8.

Methods of Deque

Following are the methods of deque:

  • Insert(): Adds a new element and gives back an iterator with the first of the newly added elements as its point.
  • Rbegin(): Generates a reverse iterator pointing to the deque’s last value.
  • Rend(): Generates a reverse iterator with an initial position before the deque’s origin.
  • Cbegin(): Returns a constant iterator that always points to the container’s first element; as a result, the iterator can only be utilized to traverse the deque and not be modified.
  • Max_size(): The number of elements a deque container can hold is returned by this function.
  • Assign(): Used to assign values to a deque container that is the same or different.
  • Resize(): Function that is used to modify the deque’s size.
  • Push_back(): With the help of this function, components can be added from the rear into a deque.
  • Front(): It is used to refer to the deque container’s initial element.
  • Back(): It is used to refer to the deque container’s last element.
  • Clear(): It is used to clear all of the elements from deque by reducing its size to 0.
  • Erase(): Used to delete the objects from a container from a certain point or range.
  • Deque::empty(): It is used to determine whether the deque is empty.
  • Operator=: Used to allocate a new data to the container and swap out the old ones.
  • Operator[]: Used to refer to the element in the operator at the specified place.
  • At(): Used to refer to the component present at the location specified as the function’s parameter.
  • Swap(): This function is used to swap the deques of the same data type.
  • Begin(): It is used to provide an iterator pointing to the initial object of the deque container.
  • Emplace_front(): A new element is inserted into the deque container using this function. The beginning of the deque is amended to include the additional component.
  • Emplace_back(): Used to add a new value to the deque container. The new component is included at the very end of the deque.

Deque Data-Structure

Let’s check the deque data structure details in the following section:

Procedures on a Deque

These steps must be followed before carrying out the subsequent operations:

Step 1: Take an n-dimensional array (deque). In the first position, place two pointers and set front = -1 and rear = 0.

Set up a deque array and pointers.

Insertion at the Front

Step 1: This action adds a component in front. Check the front’s location.

If the front is less than 5, reset the front to n-1 (last index).

Step 2: Reduce the front by 1 if necessary. Now, add the new key n to the array[front]. Let’s suppose n=6.

Insertion at the Rear

Step 1: This action adds a component at the rare. Make sure that the array isn’t full.

Step 2: If the queue is full, reset the rear value to 0 (r=0). Otherwise, raise the rare by 1.

Step 3: In an array[rear], add the new key 6.

Remove from the Front

Step 1: An element at the front is removed during the process. Make sure that the deque isn’t empty.

Step 2: Deletion is not possible if the deque is empty (front = -1) (Underflow condition). Set the front = -1 only and the rear = -1 if the deque consists of one element such as front = rear. Assign the value to the front (front = 0) if the front is at the end (front = n – 1). If not, set the front to front = front+1.

Remove from the Rear

Step 1: An element at the end is removed during the process. Make sure that the deque isn’t empty.

Step 2: Deletion is not possible if the deque is empty (front = -1) (Underflow condition). Set the front = -1 and the rear = -1 if the deque only has a single element (front = rear). Otherwise, proceed with the following steps. Let’s move towards the front, rear = n – 1 if the rear is on the front (rear = 0). If not, set the rare = rare-1.

Example 1: Creating Deque

In this example, we create a deque. We first include our header files “#include <iostream>” and #include <deque> where #include commands the preprocessor to include the header file iostream and deque which contains all of the program’s functions.

#include <iostream>

#include <deque>

using namespace std;
void display_deque(deque);
int main() {
  deque mydeque {4, 2, 7, 5, 8};
  cout << "mydeque values are = ";
  for (int var : mydeque) {
    cout << var << ", ";
  }
  return 0;
}

After that, we describe a display _deque function that is used to execute the deque values that we assign to it.

Moving into our main function, the int main() indicates that our function must return an integer value at the end of execution, which we do by returning 0 at the program’s conclusion by using a uniform initialization “deque<int> mydeque {4, 2, 7, 5,8}”. In this “int” is the data type of values that we assigned and mydeque is the name that we used for our deque. We assigned the integer values to the deque named mydeque that are 4, 2, 7, 5, 8. To display our deque, we used the for loop to a fixed size. And then, we pushed the run or F7 button to get the output of the program.

Example 2: Adding More Values to a Deque

In this example, we add more values to a deque. After adding the required header files for this program, we move into our main function of the integer data type “deque<int> var {0, 1, 2}”. In this “int” is the data type of values that we assigned and “var” is the name that we used for our deque. We assign the integer values to the deque named “var” that are 0, 1, and 2. Then, we push two elements, element 8 at the front of the deque and element 5 at the end of the deque, using the push_front() and push_back() functions of the deque. So, the resulting deque that we have is 8, 0, 1, and 5.

#include <iostream>

#include <deque>

using namespace std;
int main() {
  deque var {0, 1, 2};
  cout << "Initial Deque values are: ";
  for (const int& var : var) {
    cout << var << ", ";
  }
  var.push_back(5);
  var.push_front(8);
  cout << "\nFinal Deque values are: ";
  for (const int& var : var) {
    cout << var << ", ";
  }
  return 0;
}

Once we are done with the coding of this example, we compile and execute it in any compiler. The result is depicting the expected output of the previous code.

Example 3: Updating Elements at Specified Indexes

In this example, we update the values in a deque after including our header files “#include <iostream>” and “#include <deque>” for this executable code.

#include <iostream>

#include <deque>

using namespace std;
int main() {
  deque var = {1, 2};
  cout << "Initial Deque values are: ";
  for (const int& var : var) {
    cout << var << ", ";
  }
  var.at(0) = 3;
  var.at(1) = 4;
  cout << "\nUpdated Deque values are: ";
  for (const int& var : var) {
    cout << var << ", ";
  }
  return 0;
}

Now, we go towards our main function in which we first initialized our deque named “var” with values 1 and 2. Then, we use a for loop to display the values of our initialized deque. To update the deque values, we use the at() function (as we know, the at() function is used to refer to the specified position in the deque) at index 0 and 1, assigning new values to “var”. These are 3 and 4. Then, our updated dequeue is 3 and 4. After getting our code ready, we compile it using any compiler tool. Here is the desired output of our code:

Example 4: Using Iterator to Remove the Values

In this example, we use the iterators to access the elements in the deque. An object that points to an element inside a container is called an iterator.

#include <iostream>

#include <deque>

using namespace std;
int main() {
  deque var {0, 3, 5, 8};
 deque::iterator var_iter;

  var_iter = var.begin();  
  int first_element = *var_iter;
  cout << "var[0] = " << first_element << endl;
  var_iter = var.begin() + 1;
  int element_index1 = *var_iter;
  cout << "var[1] = " << element_index1 << endl;
  var_iter = var.end() - 1;
  int last_element = *var_iter;
  cout << "var[2] = " << last_element;
  return 0;
}

Deque can be iterated both forward and backward using the deque::cbegin and deque::cend, and in both ways using the deque::crbegin and deque::crend.

Initially, we created an iterator that can point to a deque of integers named ”var”. Then, we pointed to the following elements using the “var_inter” iterator. The iterator that the begin() method returns points to the first element. The “begin() + 1” generates an iterator using the element’s index 1 as its starting point. As you can see, we use the var.end() – 1 rather than the var.end().

This is because the iterator for the end() method links to an iterator that goes past the last element. To obtain the last element, we deduct 1. We use the indirection operator * to obtain the value of an element after using the inter_var to point to it.

Operations of Deque

The fundamental operations that can be carried out on deque are as follows:

  • Insertfront is usually used to add or insert something at the front of the deque.
  • Insert or add something at the end of the deque by using the insertLast command.
  • deleteFront is used to remove the item from the queue’s front by deleting it.
  • remove final in this the item should be deleted or moved to the end of the queue.
  • Get the first item in the deque using the getFront method.
  • Get the last item in the queue using the getLast method.
  • isEmpty is used to check whether the deque is null.
  • isFull is used to determine whether the deque is full.

Conclusion

Deque is the greatest option because it is quicker and helps the code run more quickly. The deque operates better for log sequences. This article is based on deque implementation and its major methods, which help us to modify the deque according to our needs. We aim to explain the deque and its methods as well as with examples of how to use the deque and when to use it. The tool that we used to implement code is the C++ compiler. We made a sincere effort to make this tutorial as simple and as understandable for you as possible.

About the author

Omar Farooq

Hello Readers, I am Omar and I have been writing technical articles from last decade. You can check out my writing pieces.