Deque
I. In-Class Exercises
Programming Exercises
II. Knowledge Summary
Core Idea
A deque (Double-Ended Queue) is a data structure that allows insertion and deletion at both ends. Unlike a regular queue (which only supports enqueue at the back and dequeue at the front), a deque supports O(1) insertion and deletion at both the front and back.
The C++ STL deque uses segmented contiguous storage (multiple fixed-size array blocks) internally, also supporting O(1) random access.
STL deque Operations
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 deque<int> dq;
6
7 // Back operations
8 dq.push_back(1); // [1]
9 dq.push_back(2); // [1, 2]
10 dq.push_back(3); // [1, 2, 3]
11
12 // Front operations
13 dq.push_front(0); // [0, 1, 2, 3]
14 dq.push_front(-1); // [-1, 0, 1, 2, 3]
15
16 // Random access O(1)
17 cout << "dq[2] = " << dq[2] << endl; // 1
18
19 // Front and back access
20 cout << "front = " << dq.front() << endl; // -1
21 cout << "back = " << dq.back() << endl; // 3
22
23 // Front and back deletion
24 dq.pop_front(); // [0, 1, 2, 3]
25 dq.pop_back(); // [0, 1, 2]
26
27 // Size
28 cout << "size = " << dq.size() << endl; // 3
29
30 // Traversal
31 for (int x : dq) cout << x << " "; // 0 1 2
32 cout << endl;
33
34 return 0;
35}deque vs vector vs list
| Operation | deque | vector | list |
|---|---|---|---|
| push_back | O(1) | Amortized O(1) | O(1) |
| push_front | O(1) | O(n) | O(1) |
| pop_back | O(1) | O(1) | O(1) |
| pop_front | O(1) | O(n) | O(1) |
| Random access [i] | O(1) | O(1) | O(n) |
| Middle insertion | O(n) | O(n) | O(1) |
| Memory layout | Segmented contiguous | Contiguous | Linked list |
When to choose deque: When you need efficient operations at both ends while also needing random access.
Classic Application: Sliding Window
The most important application of deque is the sliding window problem. Although this scenario more commonly uses a "monotonic queue" (covered later), understanding basic deque operations is a prerequisite.
Problem: Given an array and a window size k, find the maximum value in each window.
1#include <bits/stdc++.h>
2using namespace std;
3
4// Brute force O(nk)
5void bruteForce(int a[], int n, int k) {
6 for (int i = 0; i <= n - k; i++) {
7 int maxVal = a[i];
8 for (int j = i + 1; j < i + k; j++)
9 maxVal = max(maxVal, a[j]);
10 printf("%d ", maxVal);
11 }
12 printf("\n");
13}
14
15// Monotonic queue method O(n) — See the "Monotonic Queue" lesson for details
16void dequeMethod(int a[], int n, int k) {
17 deque<int> dq; // Store indices, maintaining a decreasing queue
18
19 for (int i = 0; i < n; i++) {
20 // Remove elements that are out of the window range
21 while (!dq.empty() && dq.front() <= i - k)
22 dq.pop_front();
23
24 // Maintain monotonicity: remove all elements smaller than a[i]
25 while (!dq.empty() && a[dq.back()] <= a[i])
26 dq.pop_back();
27
28 dq.push_back(i);
29
30 // Output window maximum
31 if (i >= k - 1)
32 printf("%d ", a[dq.front()]);
33 }
34 printf("\n");
35}
36
37int main() {
38 int a[] = {1, 3, -1, -3, 5, 3, 6, 7};
39 int n = 8, k = 3;
40
41 printf("Brute force: ");
42 bruteForce(a, n, k);
43
44 printf("Deque method: ");
45 dequeMethod(a, n, k);
46
47 return 0;
48}Execution Example
Using array [1, 3, -1, -3, 5, 3, 6, 7] with window size k=3:
| i | a[i] | Indices in deque | Corresponding values | Window Maximum |
|---|---|---|---|---|
| 0 | 1 | [0] | [1] | - |
| 1 | 3 | [1] | [3] | - |
| 2 | -1 | [1, 2] | [3, -1] | 3 |
| 3 | -3 | [1, 2, 3] | [3, -1, -3] | 3 |
| 4 | 5 | [4] | [5] | 5 |
| 5 | 3 | [4, 5] | [5, 3] | 5 |
| 6 | 6 | [6] | [6] | 6 |
| 7 | 7 | [7] | [7] | 7 |
Output: 3 3 5 5 6 7
Key step analysis (for i=4, a[i]=5):
- Check front: dq.front()=1,
1 <= 4-3=1, remove (out of window) - Check back: a[dq.back()]=a[3]=-3
<= 5, remove - Check back: a[dq.back()]=a[2]=-1
<= 5, remove - Deque is empty, push_back(4)
- Window maximum = a[dq.front()] = a[4] = 5
BFS with Deque (0-1 BFS)
When edge weights are only 0 and 1, a deque can replace a priority queue for shortest path, reducing time complexity from O(E log V) to O(V + E):
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5vector<pair<int, int>> adj[MAXN]; // (neighbor, weight 0 or 1)
6int dist[MAXN];
7
8void bfs01(int start, int n) {
9 fill(dist, dist + n + 1, INT_MAX);
10 dist[start] = 0;
11 deque<int> dq;
12 dq.push_back(start);
13
14 while (!dq.empty()) {
15 int u = dq.front();
16 dq.pop_front();
17
18 for (auto [v, w] : adj[u]) {
19 if (dist[u] + w < dist[v]) {
20 dist[v] = dist[u] + w;
21 if (w == 0)
22 dq.push_front(v); // Weight 0, add to front
23 else
24 dq.push_back(v); // Weight 1, add to back
25 }
26 }
27 }
28}Detailed Problem-Solving Steps
Consider using a deque in the following situations:
- Need operations at both ends: Simultaneously need push_front and push_back
- Sliding window problems: Maintaining the maximum/minimum within a window (with monotonicity)
- 0-1 BFS: Shortest path with edge weights of only 0 and 1
- Simulating double-ended operations: Such as certain card games or queue problems
Common Mistakes
- Calling front/back on an empty deque: Accessing without checking empty() leads to undefined behavior
- Confusing deque and queue: queue only supports back insertion and front removal; deque supports both ends
- Misusing deque instead of vector in competitions: Although deque's random access is O(1), the constant factor is larger and slower than vector
- Incorrect index management in sliding windows: Be clear about whether the deque stores indices or values
- Forgetting to check for updates in 0-1 BFS: Leading to duplicate elements in the queue and reduced efficiency
Algorithm Evaluation
| Application Scenario | Time Complexity | Description |
|---|---|---|
| Basic double-ended operations | O(1) per operation | push/pop front/back |
| Sliding window extrema | O(n) | Combined with monotonic queue |
| 0-1 BFS | O(V + E) | Replaces Dijkstra |
| Random access | O(1) | But larger constant than vector |
Deque is a powerful data structure. Mastering it is the foundation for learning monotonic queues and 0-1 BFS. The most common usage in competitions is as the underlying container for monotonic queues.