-
Hajipur, Bihar, 844101
C++ Deque
A deque (short for double-ended queue) in C++ is a sequence container that allows elements to be added or removed from both the front and the back efficiently. Unlike vectors, which allow fast insertions and deletions only at the end, deques provide flexibility at both ends.
In simple terms, you can think of a deque as a mix of a vector and a queue — it combines the fast random access of vectors with the flexible insertion and deletion of queues.
C++ provides a built-in implementation of deque in the Standard Template Library (STL) using the <deque> header.
Why Use a Deque in C++
A deque is an ideal container when you need to insert or remove elements from both ends frequently. It is widely used in applications like sliding window problems, caching, and implementing double-ended queues.
Some key benefits include:
-
Fast insertion and deletion at both ends.
-
Dynamic resizing like vectors.
-
Random access using index operators.
However, inserting or deleting elements in the middle is slower than lists but faster than vectors in certain cases.
Declaring a Deque
To use a deque, include the <deque> header and use the std::deque class template.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> numbers = {10, 20, 30};
numbers.push_front(5);
numbers.push_back(40);
for (int num : numbers)
cout << num << " ";
return 0;
}
Output:
5 10 20 30 40
Explanation:
Here, push_front() inserts an element at the beginning, while push_back() adds one at the end. This shows how easily a deque allows modifications at both ends.
Common Deque Operations in C++
The deque container supports several useful operations similar to vectors and lists.
1. push_back()
Adds an element to the end of the deque.
dq.push_back(100);
2. push_front()
Adds an element to the beginning.
dq.push_front(50);
3. pop_back()
Removes the last element.
dq.pop_back();
4. pop_front()
Removes the first element.
dq.pop_front();
5. at()
Accesses an element at a specific index.
cout << dq.at(2);
6. front() and back()
Returns references to the first and last elements.
cout << dq.front() << " " << dq.back();
7. size() and empty()
Check the size or whether the deque is empty.
cout << dq.size();
if (dq.empty()) cout << "Deque is empty";
Example: Basic Deque Operations
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_front(5);
dq.push_front(1);
cout << "Deque elements: ";
for (int val : dq)
cout << val << " ";
dq.pop_back();
dq.pop_front();
cout << "\nAfter pop operations: ";
for (int val : dq)
cout << val << " ";
return 0;
}
Output:
Deque elements: 1 5 10 20
After pop operations: 5 10
Accessing Elements in a Deque
You can access elements directly using indices or iterator-based loops.
Using Index:
cout << dq[1];
Using Iterators:
for (auto it = dq.begin(); it != dq.end(); ++it)
cout << *it << " ";
Modifying Elements in a Deque
Deques allow you to modify elements directly:
dq[0] = 100;
dq.at(1) = 200;
They behave much like vectors in terms of random access.
Clearing and Swapping Deques
You can clear all elements or swap contents between two deques easily.
deque<int> dq1 = {1, 2, 3};
deque<int> dq2 = {4, 5, 6};
dq1.swap(dq2);
dq1.clear();
Real-Life Example: Sliding Window Maximum
A popular problem solved using deques is finding the maximum element in every subarray of size k.
#include <iostream>
#include <deque>
using namespace std;
void printMax(int arr[], int n, int k) {
deque<int> dq;
for (int i = 0; i < n; i++) {
while (!dq.empty() && dq.front() <= i - k)
dq.pop_front();
while (!dq.empty() && arr[dq.back()] <= arr[i])
dq.pop_back();
dq.push_back(i);
if (i >= k - 1)
cout << arr[dq.front()] << " ";
}
}
int main() {
int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
printMax(arr, 8, k);
return 0;
}
Output:
3 3 5 5 6 7
This demonstrates how deques can manage data efficiently from both ends.
Advantages of Using Deque
-
Insertions and deletions from both ends are efficient.
-
Provides random access like vectors.
-
No need for reallocation as in vectors.
-
More flexible than queues and stacks.
Limitations of Deque
-
Insertion and deletion in the middle are slower than lists.
-
Slightly higher memory overhead compared to vectors.
-
Complex internal memory management.
When to Use a Deque
Use a deque when:
-
You frequently insert or remove elements from both ends.
-
You need random access to elements.
-
You are solving problems involving sliding windows or double-ended queues.
Summary of the Tutorial
A C++ Deque is a powerful STL container that combines the best of vectors and queues. It provides flexibility for insertion and deletion from both ends, along with direct access to elements. It’s an excellent choice for programs that require dynamic resizing and efficient double-ended operations.
Practice Questions
-
Write a C++ program to create a deque of integers and perform operations like
push_front(),push_back(),pop_front(), andpop_back(). -
Create a program that inserts five strings into a deque and displays them in both forward and reverse order.
-
Write a program to check whether a deque is empty and display its size.
-
Build a C++ program that removes all negative numbers from a deque of integers.
-
Write a program to access the first and last elements of a deque using
front()andback(). -
Create a program that reverses a deque without using any additional containers.
-
Write a C++ program to merge two deques and store the result in a new deque.
-
Build a program that simulates a double-ended queue in a ticket counter system.
-
Write a program that removes duplicate elements from a deque.
-
Create a program that sorts the elements of a deque in ascending order.
