STL deque - 双端队列与滑动窗口

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 默认构造
    deque<int> dq;
    
    // 大小构造
    deque<int> dq1(5);      // 5个默认值（0）
    deque<int> dq2(5, 10);  // 5个值为10的元素
    
    // 迭代器构造
    vector<int> v = {1, 2, 3, 4, 5};
    deque<int> dq3(v.begin(), v.end());
    
    // 拷贝构造
    deque<int> dq4(dq3);
    
    // 移动构造
    deque<int> dq5(move(dq4));
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    deque<int> dq;
    
    // 两端插入
    dq.push_back(10);  // 队尾插入
    dq.push_front(20); // 队首插入
    dq.emplace_back(30);  // 原地构造
    dq.emplace_front(40); // 原地构造
    // dq: [40, 20, 10, 30]
    
    // 两端删除
    dq.pop_back();   // 删除队尾
    dq.pop_front();  // 删除队首
    // dq: [20, 10]
    
    // 访问元素
    cout << "队首: " << dq.front() << endl;  // 20
    cout << "队尾: " << dq.back() << endl;   // 10
    cout << "索引1: " << dq[1] << endl;      // 10
    cout << "索引1: " << dq.at(1) << endl;   // 10（带边界检查）
    
    // 大小和判空
    cout << "大小: " << dq.size() << endl;  // 2
    cout << "是否为空: " << (dq.empty() ? "是" : "否") << endl;  // 否
    
    // 清空
    dq.clear();
    cout << "清空后大小: " << dq.size() << endl;  // 0
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

vector<int> max_sliding_window(vector<int>& nums, int k)
{
    vector<int> result;
    deque<int> dq;  // 存储索引，维护单调递减队列
    
    for (int i = 0; i < nums.size(); i++)
    {
        // 移除窗口外的元素
        if (!dq.empty() && dq.front() == i - k)
        {
            dq.pop_front();
        }
        
        // 维护单调递减队列
        while (!dq.empty() && nums[dq.back()] <= nums[i])
        {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // 窗口形成后开始记录结果
        if (i >= k - 1)
        {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> result = max_sliding_window(nums, k);
    
    cout << "滑动窗口最大值: ";
    for (int x : result)
    {
        cout << x << " ";  // 3 3 5 5 6 7
    }
    cout << endl;
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

vector<int> min_sliding_window(vector<int>& nums, int k)
{
    vector<int> result;
    deque<int> dq;  // 存储索引，维护单调递增队列
    
    for (int i = 0; i < nums.size(); i++)
    {
        // 移除窗口外的元素
        if (!dq.empty() && dq.front() == i - k)
        {
            dq.pop_front();
        }
        
        // 维护单调递增队列
        while (!dq.empty() && nums[dq.back()] >= nums[i])
        {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // 窗口形成后开始记录结果
        if (i >= k - 1)
        {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

// 使用 deque 实现栈
class MyStack
{
private:
    deque<int> dq;
public:
    void push(int x)
    {
        dq.push_back(x);
    }
    
    int pop()
    {
        int x = dq.back();
        dq.pop_back();
        return x;
    }
    
    int top()
    {
        return dq.back();
    }
    
    bool empty()
    {
        return dq.empty();
    }
};

// 使用 deque 实现队列
class MyQueue
{
private:
    deque<int> dq;
public:
    void push(int x)
    {
        dq.push_back(x);
    }
    
    int pop()
    {
        int x = dq.front();
        dq.pop_front();
        return x;
    }
    
    int front()
    {
        return dq.front();
    }
    
    bool empty()
    {
        return dq.empty();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// 0-1 BFS 处理边权为 0 或 1 的图
vector<int> zero_one_bfs(int start, const vector<vector<pair<int, int>>>& adj)
{
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
    
    dist[start] = 0;
    dq.push_front(start);
    
    while (!dq.empty())
    {
        int u = dq.front();
        dq.pop_front();
        
        for (const auto& edge : adj[u])
        {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (w == 0)
                {
                    dq.push_front(v);  // 权值为 0 放在队首
                }
                else
                {
                    dq.push_back(v);   // 权值为 1 放在队尾
                }
            }
        }
    }
    
    return dist;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// 滑动窗口中位数（使用双端队列辅助）
vector<double> median_sliding_window(vector<int>& nums, int k)
{
    vector<double> result;
    multiset<int> window(nums.begin(), nums.begin() + k);
    auto mid = next(window.begin(), k / 2);
    
    for (int i = k; ; i++)
    {
        // 计算中位数
        if (k % 2 == 0)
        {
            result.push_back((*mid + *prev(mid)) / 2.0);
        }
        else
        {
            result.push_back(*mid);
        }
        
        if (i == nums.size())
        {
            break;
        }
        
        // 移除窗口左端元素
        window.insert(nums[i]);
        if (nums[i] < *mid)
        {
            mid--;
        }
        
        // 插入新元素
        if (nums[i - k] <= *mid)
        {
            mid++;
        }
        window.erase(window.lower_bound(nums[i - k]));
    }
    
    return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    deque<pair<int, string>> dq;
    dq.emplace_back(1, "apple");
    dq.emplace_back(2, "banana");
    
    for (const auto& p : dq)
    {
        int id = p.first;
        string name = p.second;
        cout << "id: " << id << ", name: " << name << endl;
    }
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    deque<int> dq = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // C++11: sort
    sort(dq.begin(), dq.end());
    
    // C++11: find
    auto it = find(dq.begin(), dq.end(), 5);
    if (it != dq.end())
    {
        cout << "找到 5 在位置: " << distance(dq.begin(), it) << endl;
    }
    
    // C++11: 过滤偶数
    cout << "偶数: ";
    for (int x : dq)
    {
        if (x % 2 == 0)
        {
            cout << x << " ";
        }
    }
    cout << endl;
    
    return 0;
}

1
2
3
4
5
6
7

// 预分配空间
int expected_size = 100000;
deque<int> dq;
dq.reserve(expected_size);  // 注意：deque 的 reserve 只是一个提示

// 更有效的方式：直接构造足够大的 deque
deque<int> dq(expected_size);

1
2
3
4
5
6
7

// 错误示范：在中间插入元素
deque<int> dq = {1, 2, 3, 4, 5};
dq.insert(dq.begin() + 2, 10);  // O(n) 操作

// 正确做法：优先在两端操作
dq.push_front(0);  // O(1)
dq.push_back(6);   // O(1)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

// 滑动窗口最大值
vector<int> max_sliding_window(vector<int>& nums, int k)
{
    vector<int> result;
    deque<int> dq;
    
    for (int i = 0; i < nums.size(); i++)
    {
        // 移除窗口外的元素
        if (!dq.empty() && dq.front() == i - k)
        {
            dq.pop_front();
        }
        
        // 维护单调递减队列
        while (!dq.empty() && nums[dq.back()] <= nums[i])
        {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // 窗口形成后开始记录结果
        if (i >= k - 1)
        {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}

// 0-1 BFS
vector<int> zero_one_bfs(int start, const vector<vector<pair<int, int>>>& adj)
{
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
    
    dist[start] = 0;
    dq.push_front(start);
    
    while (!dq.empty())
    {
        int u = dq.front();
        dq.pop_front();
        
        for (const auto& edge : adj[u])
        {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (w == 0)
                {
                    dq.push_front(v);
                }
                else
                {
                    dq.push_back(v);
                }
            }
        }
    }
    
    return dist;
}

// 双端队列实现栈
class MyStack
{
private:
    deque<int> dq;
public:
    void push(int x)
    {
        dq.push_back(x);
    }
    
    int pop()
    {
        int x = dq.back();
        dq.pop_back();
        return x;
    }
    
    int top()
    {
        return dq.back();
    }
    
    bool empty()
    {
        return dq.empty();
    }
};

// 双端队列实现队列
class MyQueue
{
private:
    deque<int> dq;
public:
    void push(int x)
    {
        dq.push_back(x);
    }
    
    int pop()
    {
        int x = dq.front();
        dq.pop_front();
        return x;
    }
    
    int front()
    {
        return dq.front();
    }
    
    bool empty()
    {
        return dq.empty();
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 测试滑动窗口最大值
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> result = max_sliding_window(nums, k);
    
    cout << "滑动窗口最大值: ";
    for (int x : result)
    {
        cout << x << " ";
    }
    cout << endl;
    
    // 测试 0-1 BFS
    int n = 4;
    vector<vector<pair<int, int>>> adj(n);
    adj[0] = {{1, 0}, {2, 1}};
    adj[1] = {{0, 0}, {3, 1}};
    adj[2] = {{0, 1}, {3, 0}};
    adj[3] = {{1, 1}, {2, 0}};
    
    vector<int> dist = zero_one_bfs(0, adj);
    cout << "0-1 BFS 距离: ";
    for (int d : dist)
    {
        cout << d << " ";
    }
    cout << endl;
    
    // 测试栈实现
    MyStack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    cout << "栈顶: " << stack.top() << endl;  // 3
    cout << "弹出: " << stack.pop() << endl;  // 3
    cout << "栈顶: " << stack.top() << endl;  // 2
    
    // 测试队列实现
    MyQueue queue;
    queue.push(1);
    queue.push(2);
    queue.push(3);
    cout << "队首: " << queue.front() << endl;  // 1
    cout << "弹出: " << queue.pop() << endl;  // 1
    cout << "队首: " << queue.front() << endl;  // 2
    
    return 0;
}