Welcome to The Coding College! In this tutorial, we’ll dive into deque (double-ended queue) in C++, a versatile data structure provided by the Standard Template Library (STL).
What Is a Deque?
A deque (double-ended queue) is a linear data structure that allows insertion and deletion of elements from both the front and back. Unlike stacks and queues, which are restricted to LIFO and FIFO operations, a deque offers greater flexibility.
Key Characteristics:
- Dynamic Size: The size of a deque can grow or shrink dynamically.
- Access From Both Ends: You can add or remove elements from both ends.
Declaring a Deque
To use deques in C++, include the <deque> header.
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> myDeque; // Declare a deque of integers
return 0;
}Common Operations
1. Push Elements
You can add elements to both the front and back of the deque using push_front and push_back.
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> myDeque;
myDeque.push_back(10); // Add 10 to the back
myDeque.push_back(20); // Add 20 to the back
myDeque.push_front(5); // Add 5 to the front
cout << "Front: " << myDeque.front() << endl; // Access the front element
cout << "Back: " << myDeque.back() << endl; // Access the back element
return 0;
}Output:
Front: 5
Back: 20 2. Pop Elements
Remove elements from either the front or the back using pop_front and pop_back.
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> myDeque;
myDeque.push_back(10);
myDeque.push_back(20);
myDeque.push_front(5);
myDeque.pop_front(); // Remove the front element (5)
cout << "Front after pop: " << myDeque.front() << endl;
myDeque.pop_back(); // Remove the back element (20)
cout << "Back after pop: " << myDeque.back() << endl;
return 0;
}Output:
Front after pop: 10
Back after pop: 10 3. Access Elements by Index
Deques allow direct access to elements using the [] operator or at().
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> myDeque = {10, 20, 30};
cout << "Element at index 1: " << myDeque[1] << endl; // Using []
cout << "Element at index 2: " << myDeque.at(2) << endl; // Using at()
return 0;
}Output:
Element at index 1: 20
Element at index 2: 30 4. Check Size and Empty Status
Use size() to get the number of elements and empty() to check if the deque is empty.
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> myDeque;
cout << "Deque is empty: " << boolalpha << myDeque.empty() << endl;
myDeque.push_back(10);
cout << "Deque size: " << myDeque.size() << endl;
return 0;
}Output:
Deque is empty: true
Deque size: 1 5. Insert and Erase Elements
You can insert or remove elements at specific positions using insert and erase.
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> myDeque = {10, 20, 30};
myDeque.insert(myDeque.begin() + 1, 15); // Insert 15 at index 1
for (int x : myDeque) {
cout << x << " ";
}
cout << endl;
myDeque.erase(myDeque.begin() + 2); // Remove element at index 2
for (int x : myDeque) {
cout << x << " ";
}
return 0;
}Output:
10 15 20 30
10 15 30 Iterating Over a Deque
You can use iterators to traverse a deque.
#include <deque>
#include <iostream>
using namespace std;
int main() {
deque<int> myDeque = {10, 20, 30, 40};
for (auto it = myDeque.begin(); it != myDeque.end(); ++it) {
cout << *it << " ";
}
return 0;
}Output:
10 20 30 40 Applications of Deques
- Sliding Window Problems: Efficiently handle a fixed-size window over a dataset.
- Palindrome Checking: Verify whether a string is a palindrome.
- Double-Ended Buffers: Process data from both ends.
- Scheduling Algorithms: Manage tasks that require both FIFO and LIFO operations.
Real-World Example: Sliding Window Maximum
Find the maximum value in a sliding window of size k in an array.
#include <deque>
#include <iostream>
#include <vector>
using namespace std;
void slidingWindowMax(vector<int> arr, int k) {
deque<int> dq;
for (int i = 0; i < arr.size(); ++i) {
// Remove elements outside the current window
if (!dq.empty() && dq.front() == i - k) {
dq.pop_front();
}
// Remove elements smaller than the current element
while (!dq.empty() && arr[dq.back()] < arr[i]) {
dq.pop_back();
}
dq.push_back(i);
// Output maximum for the current window
if (i >= k - 1) {
cout << arr[dq.front()] << " ";
}
}
}
int main() {
vector<int> arr = {1, 3, 1, 2, 5, 3, 6, 7};
int k = 3;
slidingWindowMax(arr, k);
return 0;
}Output:
3 3 5 5 6 7 Summary
- Advantages: Dynamic size, access to both ends.
- Key Methods:
push_back,push_front,pop_back,pop_front,front,back,insert,erase. - Applications: Efficient in problems requiring operations at both ends of a sequence.
Learn More at The Coding College
For more tutorials on C++ and advanced data structures, visit The Coding College.