66
The deque (double-ended queue) in the C++ Standard Template Library (STL) is a sequence container that supports fast insertion and deletion at both the front and back.
It’s similar to vector but provides efficient operations on both ends, making it versatile for various applications.
Key Features of deque
- Double-ended: Supports insertion and deletion from both front and back.
- Dynamic resizing: Expands and contracts as needed, unlike static arrays.
- Random access: Elements can be accessed in constant time with an index, like vector.
Basic Syntax
#include <deque> using namespace std; deque<int> dq;
1. Basic Operations: Insertion and Deletion
The push_back and push_front functions add elements at the back and front, respectively, while pop_back and pop_front remove elements from the back and front.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq;
// Inserting elements at the back
dq.push_back(10);
dq.push_back(20);
// Inserting elements at the front
dq.push_front(5);
cout << "Deque after insertions: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
// Removing elements from front and back
dq.pop_front();
dq.pop_back();
cout << "Deque after pop_front and pop_back: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
return 0;
}
Output:
Deque after insertions: 5 10 20 Deque after pop_front and pop_back: 10
2. Accessing Elements
deque allows random access to elements using both the at function and [] operator. front and back functions access the first and last elements, respectively.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {10, 20, 30, 40};
cout << "Element at index 2: " << dq.at(2) << endl;
cout << "First element: " << dq.front() << endl;
cout << "Last element: " << dq.back() << endl;
// Accessing elements using []
cout << "Elements: ";
for (size_t i = 0; i < dq.size(); i++) {
cout << dq[i] << " ";
}
cout << endl;
return 0;
}
Output:
Element at index 2: 30 First element: 10 Last element: 40 Elements: 10 20 30 40
3. Initializing a deque with Values
You can initialize a deque with default values using the constructor that takes a size and a value.
#include <iostream>
#include <deque>
using namespace std;
int main() {
// Create a deque of size 5, initialized with the value 100
deque<int> dq(5, 100);
cout << "Deque initialized with default values: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
return 0;
}
Output:
Deque initialized with default values: 100 100 100 100 100
4. Inserting Elements at Specific Positions
The insert function allows insertion at specific positions within the deque.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {10, 20, 30};
// Inserting 25 at the second position
dq.insert(dq.begin() + 1, 25);
cout << "Deque after inserting 25 at position 1: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
return 0;
}
Output:
Deque after inserting 25 at position 1: 10 25 20 30
5. Removing Specific Elements
Elements can be removed from specific positions using the erase function, which takes an iterator.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {10, 20, 30, 40};
// Removing element at index 1
dq.erase(dq.begin() + 1);
cout << "Deque after erasing element at position 1: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
return 0;
}
Output:
Deque after erasing element at position 1: 10 30 40
6. Clearing All Elements
The clear function removes all elements from the deque, making it empty.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {10, 20, 30};
cout << "Size before clear: " << dq.size() << endl;
dq.clear();
cout << "Size after clear: " << dq.size() << endl;
return 0;
}
Output:
Size before clear: 3 Size after clear: 0
7. Checking if deque is Empty
The empty function returns true if the deque is empty, otherwise false.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq;
if (dq.empty()) {
cout << "Deque is empty." << endl;
}
dq.push_back(10);
if (!dq.empty()) {
cout << "Deque is not empty." << endl;
}
return 0;
}
Output:
Deque is empty. Deque is not empty.
8. Resizing a deque
The resize function changes the number of elements in the deque. If the new size is greater, new elements are added with a specified value; if smaller, extra elements are removed.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {10, 20, 30};
// Resizing to a larger size, filling with 100
dq.resize(5, 100);
cout << "Deque after resizing to 5 with default value 100: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
// Resizing to a smaller size
dq.resize(2);
cout << "Deque after resizing to 2: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
return 0;
}
Output:
Deque after resizing to 5 with default value 100: 10 20 30 100 100 Deque after resizing to 2: 10 20
9. Swapping Two deque Containers
The swap function exchanges the contents of two deque containers.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq1 = {1, 2, 3};
deque<int> dq2 = {4, 5, 6, 7};
dq1.swap(dq2);
cout << "Deque 1 after swap: ";
for (int x : dq1) {
cout << x << " ";
}
cout << endl;
cout << "Deque 2 after swap: ";
for (int x : dq2) {
cout << x << " ";
}
cout << endl;
return 0;
}
Output:
Deque 1 after swap: 4 5 6 7 Deque 2 after swap: 1 2 3
10. Using Iterators with deque
deque supports iterators, which allow for easy traversal and manipulation of elements.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {10, 20, 30, 40, 50};
cout << "Elements using iterator: ";
for (auto it = dq.begin(); it != dq.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// Using reverse iterator
cout << "Elements in reverse order: ";
for (auto rit = dq.rbegin(); rit != dq.rend(); ++rit) {
cout << *rit << " ";
}
cout << endl;
return 0;
}
Output:
Elements using iterator: 10 20 30 40 50 Elements in reverse order: 50 40 30 20 10
Summary Table of deque Operations
| Operation | Code Example | Description |
|---|---|---|
| Insert at back | dq.push_back(10); | Adds element to the end |
| Insert at front | dq.push_front(10); | Adds element to the front |
| Remove from back | dq.pop_back(); | Removes element from the end |
| Remove from front | dq.pop_front(); | Removes element from the front |
| Access by index | dq[i] or dq.at(i); | Access element at specific index |
| First element | dq.front(); | Accesses the first element |
| Last element | dq.back(); | Accesses the last element |
| Insert at position | dq.insert(dq.begin() + 1, 25); | Inserts element at specified position |
| Remove at position | dq.erase(dq.begin() + 1); | Removes element at specified position |
| Clear all elements | dq.clear(); | Removes all elements |
| Check if empty | dq.empty(); | Returns true if deque is empty |
| Resize | dq.resize(5, 100); | Resizes deque, filling new slots as needed |
| Swap | dq1.swap(dq2); | Swaps contents of two deques |
| Iterate | for (auto it = dq.begin(); it != dq.end(); ++it) | Iterates through the deque |
Complete Example
This example demonstrates initializing a deque, inserting and removing elements, resizing, and using iterators for traversal.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {10, 20, 30};
// Insert elements at both ends
dq.push_front(5);
dq.push_back(40);
// Display elements
cout << "Deque after push_front and push_back: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
// Remove elements from both ends
dq.pop_front();
dq.pop_back();
cout << "Deque after pop_front and pop_back: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
// Resize deque
dq.resize(5, 100);
cout << "Deque after resizing: ";
for (int x : dq) {
cout << x << " ";
}
cout << endl;
// Using iterator to traverse
cout << "Using iterator: ";
for (auto it = dq.begin(); it != dq.end(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Sample Output:
Deque after push_front and push_back: 5 10 20 30 40 Deque after pop_front and pop_back: 10 20 30 Deque after resizing: 10 20 30 100 100 Using iterator: 10 20 30 100 100
Key Takeaways
- deque in C++ provides a dynamic, double-ended queue, allowing efficient insertions and deletions at both ends.
- It supports random access, similar to vector, and is well-suited for scenarios requiring manipulation at both ends.