std::deque
Double-ended queue
Interview Relevant: Efficient front/back operations
std::deque
Double-ended queue. O(1) insertion at both ends.
Code Examples
Double-ended queue for flexible operations.
cpp
1#include <deque>
2
3deque<int> dq = {2, 3, 4};
4
5// Add to both ends - O(1)
6dq.push_back(5);
7dq.push_front(1); // {1, 2, 3, 4, 5}
8
9// Remove from both ends - O(1)
10dq.pop_back();
11dq.pop_front();
12
13// Random access - O(1)
14dq[0] = 10;
15dq.at(1) = 20;
16
17// When to use deque vs vector:
18// - Need to add/remove from front frequently: deque
19// - Need contiguous memory: vector
20// - Random access: both are O(1)
21// - Iterators invalidation: similar rules
22
23// Sliding window pattern
24deque<int> window;
25for (int i = 0; i < n; i++) {
26 window.push_back(arr[i]);
27 if (window.size() > k) {
28 window.pop_front();
29 }
30}