Deque in C++

Real Life Example of Deque

You might have been using undo and redo operations in lots of software i.e, Microsoft Word, Libre Office, Notepad, Visual Code, etc. Let's think about a high-level approach of how it might have been implemented. The first thing that might be clear to you is that there is a need of storing some data related to undo/redo operations in the data structure. Although there could be several data structures which we can use to store deque proves it worthiness because of some reasons, let's discuss one by one.

What if We Use Vector or Array?

• First of all we need to have two separate arrays to store the undo operations and redo operations.
• Now if our operations keep increasing then the expansion of the array might be costly because as we know entire array is copied into newly allocated memory.
• If we did redo then the corresponding operation should be removed from the undo operations array, or vice-versa. As we know entire array is shifted when we remove any element from the array it would be highly time consuming.
• Keeping these points as inference we can say that array is not good for these cases.

What if We Use Stack?

• We need to maintain two stacks, one for redo operation and the other for undo operations.
• Each time when a undo happens, we need to pop the operation from the top undo of the stack and push it to the top of the redo stack.

What if We Use Queue?

• We need to maintain two queues one for undo operations and the other for redo operations.
• Each time a undo happens, we need to pop the operation from the undo queue and push it to the redo queue and vice-versa.

Deque Over All of These

• Although Stack and queues are solving our problem efficiently as compared to the array, still there is an issue of maintaining two data variables.
• By using deque, we need to just maintain one variable.
• For each undo we can insert the operation from the front end and for redo we can delete the first element from the front end and add it to the back end of the deque.
• One end will represent the undo operations and other end will represent the redo operations.
• This entire flow of undo and redo will proceed in a circular manner.
• Also, here we can fix the maximum size of deque to set the limit of undo and redo operations.
• We can therefore conclude that deque is the best option for dealing with these kind of problems.

Why Deque was Implemented?

The abstract data type is created from concrete data types in order to create a unique data structure that can have its own properties, advantages, and disadvantages. These attributes are used in order to analyze the situation of the problem statement, like whether the current data structure is best suited to store and manipulate data for a given problem statement. In order to overcome the limitations of one-ended insertion and deletion of stacks and queues, Deque was introduced. By dynamically shrinking and growing at runtime, it allows inserting and deleting from both ends. Informally, we can say that deque has powers of queue and stack both.

Comparison with Vectors

They're comparable to vectors, but they're more efficient in element insertion and deletion because of insertion and deletion at both ends within constant time. Although vectors and deques have a similar interface and can be used for similar tasks, they operate in quite different ways internally. The elements of a deque can be spread across various locations on memory. The container maintains the required info internally to deliver direct access to any of its elements in constant time and with a uniform sequential interface. In contrast, vectors use a single array to store, and this array keeps expanding.

Basic Syntax

The basic syntax of deque data structure is as follows:

data_type: Data Type of the List dq_name: Variable Name for the Deque

Deque Operation and Illustration

Deque allows some of the major unique operations like insertion and deletion from both ends also we can see the front and rear data elements within the constant time complexity. The implementation of the deque is programmer dependent, we can use any concrete data structure to build our abstract data structure deque, but for this section, we are not going to build the entire class for the same, because C++ has inbuilt implementation of deque in STL.

Push Front

This operation adds the element to the deque from the front end.

Output:

Explanation:

Pop Front

This operation removes the first element from the front end.

Output:

Explanation:

Push Rear

Similar to the last ones, this operation adds the element from the rear/back end.

Deque STL Functions

Standard Template Library contains implementation of Deque, as we are dicussing from the Programming point of view, below are the various deque STL functions with descriptions:

Examples

Explanation of all Important Deque Functions

There are various Deque STL functions available in C++. Let’s look at the following example to understand all general purpose Deque Functions.

Output:

Explanation:

• Deque variable is declared using: deque<int> dq;.
• dq.push_front(1); inserts an 1 at the starting of the dq. Now, the deque dq is : { 1 }.
• dq.push_back(2); inserts an 2 at the ending of the dq. Now, the deque dq is : {1, 2}.
• dq.push_front(3); inserts an 3 at the starting of the dq. Now, the deque dq is : {3, 1, 2}.
• dq.push_back(4); inserts an 4 at the ending of the dq. Now, the deque dq is : {3, 1, 2, 4}.
• dq.push_back5); inserts an 5 at the endingg of the dq. Now, the deque dq is : {3, 1, 2, 4, 5}.
• dq.max_size(); returns the maximum size of the dq.
• dq.size(); returns the number of elements dq has, that is 5.
• dq.front(); returns the value of the first element of the deque. In the dq {3, 1, 2, 4, 5}, 3 is the first element, so it will return 3.
• dq.back(); returns the value of the last element of the deque. In the dq {3, 1, 2, 4, 5}, 5 is the last element, so it will return 5.
• dq.at(3); returns the value of the element at the third index of the deque. In the dq {3, 1, 2, 4, 5}, 4 is at third index, so it will return 4.
• dq.pop_back(); removes an element from the ending of the dq. In the dq {3, 1, 2, 4, 5}, 5 is the last element, so it will remove 5. Now, the deque dq is : {3, 1, 2, 4}.
• dq.pop_front(); removes an element from the starting of the dq. In the dq {3, 1, 2, 4, 5}, 3 is the last element, so it will remove 5. Now, the deque dq is : { 1, 2, 4}.

Sliding Window Technique

If we want to find all subarrays(called windows) continuously, then the sliding window technique reduces the nested loop to find all required portions of an array.

The deque can be used to store the windows at each forwarded step, we can just pop the item from the front and push a new item at the rear.

Digression: This has a real life application in computer networking, where sender sends multiple frames to reciever in a sliding window format. The protocol is named Sliding window Protocol in Networking.

Output:

Explanation:

• Here you can see we have created an initial window, and later we are just removing from the front of the deque and adding a new item to the rear.
• This process slides the window at each step.

Applications

The following are some applications of deque:

• Deque can be used to implement stacks and queues. Thus it has many applications.
• Task scheduling for various processors in a multiprocessor system is implemented using a scheduling algorithm. This implementation employs a deque, with the processor executing the first element from the deque.
• Many activities are available in software applications. "Undo" is one of them. When we do an undo action multiple times, the results are saved in a list. This list is kept as a deque to easily add or remove entries from any end.
• Another application of deque is in the implementation of browsers to save history. URLs that have been recently visited are added to the front of the deque, and the URL in the rear is removed after a certain amount of insertions to the front.

Read More:

• Array in C++.