Deque

Leave a Comment / C++ STL / By

Hi everyone ✋

In this tutorial we will talk about Deque

So, What is Deque actually?

Deque stands for Double Ended Queue.

Deque is a special type of queue where data can be inserted and removed at both ends.

 

Header File Inclusion for deque

#include <deque>

Declaration & Initialization

Declaring an empty deque —

deque <int> dqList;

Declaring a deque with values —

deque <int> dqList = { 10, 20, 30, 40, 50 };

Insertion

Insert at the end

With push_back() and emplace_back() methods we insert data at the end of a deque —

deque <int> dqList;

dqList.push_back(2);
dqList.push_back(6);
dqList.push_back(12);

dqList.emplace_back(33);

After Insertion dqList will look like this —

 

2 6 12 33

 

Insert at the beginning

With push_front() and emplace_front() methods we insert data at the beginning of a deque —

dqList.push_front(5);
dqList.push_front(25);
dqList.push_front(13);

dqList.emplace_front(21);

After Insertion dqList will look like this —

 

21 13 25 5 2 6 12 33

 

Insert using insert() method

insert() method can take an iterator position and a value, then it will insert the value at that position —

dqList.insert(dqList.begin() + 1, 17);

After Insertion dqList will look like this —

 

21 17 13 25 5 2 6 12 33

 

insert() method can also take an iterator position, a count and a value, then it will insert the value count times starting from that position —

dqList.insert(dqList.begin(), 5, 11);

After Insertion dqList will look like this —

 

11 11 11 11 11 21 17 13 25 5 2 6 12 33

 

insert() method can also copy a range of elements from another deque —

deque <int> qList;

qList.push_back(7);
qList.push_back(5);
qList.push_back(15);

dqList.insert(dqList.begin(), qList.begin(), qList.end());

After Insertion dqList will look like this —

 

7 5 15 11 11 11 11 11 21 17 13 25 5 2 6 12 33

 

Accessing the element

front() method
front() method returns the front element of the deque —

int num = dqList.front();

num will be 7

back() method
back() method returns the back or tail element of the deque —

int num = dqList.back();

num will be 33

[ ] subscript operator
With the [ ] subscript operator we can randomly access any element of the deque —

// this will output the element at index 2
cout << dqList[2] << endl;

Output will be – 15

at() method
at() method also returns the element at the given index —

// this will output the element at index 2
cout << dqList.at(2) << endl;

Output will be – 15

at() method is useful for pointer variables. We can not use the [ ] subscript operator directly for pointer variables, in those cases we need to use at() method —

deque <int> *pDeque = &dqList;

// this will output the element at index 2
cout << pDeque->at(2) << endl;

Output will be – 15

Deletion

pop_back() method

pop_back() method removes the last element from the deque —

// removing element 33 from the back
dqList.pop_back();

After Deletion dqList will look like this —

 

7 5 15 11 11 11 11 11 21 17 13 25 5 2 6 12

 

pop_front() method

pop_front() method removes the front element from the deque —

// removing element 7 from the front
dqList.pop_front();

After Deletion dqList will look like this —

 

5 15 11 11 11 11 11 21 17 13 25 5 2 6 12

 

erase() method

erase() method takes an iterator position and removes the element at that position —

// removing the first element
dqList.erase(dqList.begin());

After Deletion dqList will look like this —

 

15 11 11 11 11 11 21 17 13 25 5 2 6 12

 

erase() method also takes a range and removes all elements in that range —

// removing first 3 elements
dqList.erase(dqList.begin(), dqList.begin() + 3);

After Deletion dqList will look like this —

 

11 11 11 21 17 13 25 5 2 6 12

 

clear() method

clear() method removes all elements from the deque —

dqList.clear();

After calling clear() dqList will be empty.

assign() method

assign() method removes all existing elements first, then assigns new values to the deque.

The first parameter of assign() is the count and the second parameter is the value —

deque <int> dqList = { 5, 2, 7 };

dqList.assign(5, 25);

After assign dqList will look like this —

 

25 25 25 25 25

 

Using assign() we can also copy the elements from one deque to another deque —

deque <int> copyList;

copyList.assign(dqList.begin(), dqList.end());

Now copyList will look like this —

 

25 25 25 25 25

 

Swapping

swap() method

STL deque has a method named swap(), which swaps values between two deque data structures —

deque <int> dequeOne = { 1, 3, 5, 7, 9 };
deque <int> dequeTwo = { 2, 4, 6, 8 };

dequeOne will look like this —

 

1 3 5 7 9

 

dequeTwo will look like this —

 

2 4 6 8

 

Now, let’s swap the elements of two deque —

// swapping values between two deques
dequeOne.swap(dequeTwo);

After Swapping dequeOne will look like this —

 

2 4 6 8

 

After Swapping dequeTwo will look like this —

 

1 3 5 7 9

 

Copying a deque to another

We can copy one deque to another by using the assignment operator. This is achieved by using operator overloading for deque objects —

deque <int> oldList = { 10, 20, 30 };
deque <int> newList;

newList = oldList;

Now newList will have the same elements as oldList.

Replacing deque values

We can also replace all values of a deque with a new initializer list —

newList = { 1, 2, 5, 6 };

After replacing newList will look like this —

 

1 2 5 6

 

Time Complexity

 

Operation Description Time Complexity
[ ] or at() Random access O(1)
begin() or rend() Returns an iterator pointing to the first element in the deque O(1)
end() or rbegin() Returns an iterator pointing next to the last element of the deque O(1)
front() Accessing the front element O(1)
back() Accessing the back or tail element O(1)
push_back() or emplace_back() Insert value at the end O(1)
push_front() or emplace_front() Insert value at the beginning O(1)
empty() Returns a bool value False if deque is not empty True if deque is empty O(1)
size() Returns the number of elements present in the deque O(1)
resize() Resize the deque size O(1)
max_size() Returns the maximum number of elements that a deque container can hold O(1)
insert() Insert new elements in the deque O(n)
assign() Assigns new elements to the deque by replacing its current elements O(n)
erase() Removes a single element or a range of elements from the deque O(n)
clear() Removes all elements from the deque O(n)
swap() Swap elements between two deques O(n)

 

Applications

        • Implementing both stack and queue data structures
        • Undo and redo operations in text editors
        • Palindrome checking
        • Sliding window problems
        • A-Steal job scheduling algorithm

In the next tutorial we will talk about another useful STL container.

Until then
Happy Coding 💻 🎵

Leave a Comment

Your email address will not be published. Required fields are marked *