WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
C++ Dequeues
Introduction:
A deque (double-ended queue) is a data structure that allows insertion and deletion of elements from both ends. It is part of the C++ Standard Library and provides a flexible array with efficient access to both ends.
Properties:
- Allows insertion and deletion at both ends.
- Random access is possible, similar to vectors.
- Dynamic size, automatically resizes as needed.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq;
dq.push_back(1);
dq.push_front(2);
for(int n : dq)
cout << n << ' ';
return 0;
}
Basic Operations:
- push_back(): Adds an element to the end of the deque.
- push_front(): Adds an element to the front of the deque.
- pop_back(): Removes an element from the end of the deque.
- pop_front(): Removes an element from the front of the deque.
Console Output:
2 1
Accessing Elements
Element Access:
Deques provide several ways to access elements:
- at(index): Returns a reference to the element at a specified position.
- operator[]: Provides direct access to elements using array notation.
- front(): Accesses the first element.
- back(): Accesses the last element.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {10, 20, 30};
cout << dq.at(1) << ' ' << dq[2] << ' ' << dq.front() << ' ' << dq.back();
return 0;
}
Console Output:
20 30 10 30
Modifying Deques
Modifications:
Deques allow modifications through various methods:
- insert(pos, val): Inserts elements at a specified position.
- erase(pos): Removes elements from a specified position.
- clear(): Removes all elements.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {1, 2, 3};
dq.insert(dq.begin() + 1, 4);
dq.erase(dq.begin());
for(int n : dq)
cout << n << ' ';
return 0;
}
Console Output:
4 2 3
Deque Size and Capacity
Size and Capacity:
Deques manage their size dynamically:
- size(): Returns the number of elements.
- max_size(): Returns the maximum possible number of elements.
- resize(n): Resizes the container to contain n elements.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {1, 2, 3};
cout << "Size: " << dq.size() << endl;
dq.resize(5);
cout << "New Size: " << dq.size();
return 0;
}
Console Output:
Size: 3 New Size: 5
Iterating Through Deques
Iteration:
Deques can be iterated using iterators:
- begin(): Returns an iterator to the first element.
- end(): Returns an iterator to the element following the last element.
- rbegin(): Returns a reverse iterator to the last element.
- rend(): Returns a reverse iterator to the element preceding the first element.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq = {1, 2, 3};
for(auto it = dq.begin(); it != dq.end(); ++it)
cout << *it << ' ';
return 0;
}
Console Output:
1 2 3
Deque vs Vector
Comparison:
Both deques and vectors provide dynamic arrays, but they have differences:
- Access Speed: Deques provide faster access to both ends, while vectors are faster for random access.
- Memory Allocation: Deques allocate memory in chunks, while vectors allocate a single contiguous block.
- Use Case: Deques are preferred when frequent insertions and deletions at both ends are required.
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main() {
deque<int> dq = {1, 2, 3};
vector<int> vec = {1, 2, 3};
dq.push_front(0);
vec.push_back(4);
cout << "Deque Front: " << dq.front() << ", Vector Back: " << vec.back();
return 0;
}
Console Output:
Deque Front: 0, Vector Back: 4
Deque Use Cases
Applications:
Deques are versatile and can be used in various scenarios:
- Task Scheduling: Efficiently manage tasks by adding and removing them from both ends.
- Sliding Window Algorithms: Deques help in maintaining a window of elements for processing.
- Palindrome Check: Check if a sequence is a palindrome by comparing elements from both ends.
#include <iostream>
#include <deque>
using namespace std;
bool isPalindrome(deque<char>& dq) {
while(dq.size() > 1) {
if(dq.front() != dq.back())
return false;
dq.pop_front();
dq.pop_back();
}
return true;
}
int main() {
deque<char> dq = {'r', 'a', 'c', 'e', 'c', 'a', 'r'};
cout << (isPalindrome(dq) ? "Palindrome" : "Not Palindrome");
return 0;
}
Console Output:
Palindrome
Deque Performance
Performance Considerations:
Understanding the performance characteristics of deques is crucial for efficient programming:
- Insertion/Deletion: Constant time complexity for operations at both ends.
- Random Access: O(1) time complexity, similar to vectors.
- Memory Overhead: Higher than vectors due to non-contiguous memory allocation.
#include <iostream>
#include <deque>
#include <ctime>
using namespace std;
int main() {
clock_t start, end;
deque<int> dq;
start = clock();
for(int i = 0; i < 1000000; ++i)
dq.push_back(i);
end = clock();
cout << "Time taken: " << double(end - start) / CLOCKS_PER_SEC << " seconds";
return 0;
}
Console Output:
Time taken: X.XXXX seconds
Advanced Deque Techniques
Advanced Techniques:
Utilizing deques in advanced scenarios can optimize solutions:
- Custom Allocators: Use custom memory allocators for specific performance needs.
- Thread Safety: Implement locks for concurrent access in multi-threaded environments.
- Hybrid Containers: Combine deques with other containers for specialized data structures.
#include <iostream>
#include <deque>
#include <mutex>
using namespace std;
mutex mtx;
void threadSafePush(deque<int>& dq, int val) {
lock_guard<mutex> lock(mtx);
dq.push_back(val);
}
int main() {
deque<int> dq;
threadSafePush(dq, 10);
cout << dq.front();
return 0;
}
Console Output:
10
