deque和priority_queue - C++程序设计

deque 概述

deque（double-ended queue）是双端队列，支持在两端快速插入和删除。

deque 的特点

两端插入删除：$$ O(1) $$
随机访问：$$ O(1) $$
中间插入删除：$$ O(n) $$
比 vector 稍慢（内存不连续）

deque 基本用法


#include <deque>
using namespace std;

int main() {
    // 创建 deque
    deque dq;

    // 前端操作
    dq.push_front(1);  // 前端插入
    dq.push_front(2);
    // dq: 2 1

    // 后端操作
    dq.push_back(3);   // 后端插入
    dq.push_back(4);
    // dq: 2 1 3 4

    // 访问元素
    cout << dq.front() << endl;  // 2 (前端)
    cout << dq.back() << endl;   // 4 (后端)
    cout << dq[0] << endl;       // 2 (随机访问)

    // 遍历
    for (int i = 0; i < dq.size(); i++) {
        cout << dq[i] << " ";
    }
    // 输出: 2 1 3 4

    // 前端删除
    dq.pop_front();   // 删除前端
    // dq: 1 3 4

    // 后端删除
    dq.pop_back();    // 删除后端
    // dq: 1 3

    // 使用迭代器
    for (deque::iterator it = dq.begin(); it != dq.end(); it++) {
        cout << *it << " ";
    }

    return 0;
}

deque 可视化

deque 支持两端操作：

deque 为空

deque vs vector vs list

操作	vector	deque	list
前端插入	$$ O(n) $$	$$ O(1) $$	$$ O(1) $$
后端插入	$$ O(1) $$ (摊还)	$$ O(1) $$	$$ O(1) $$
中间插入	$$ O(n) $$	$$ O(n) $$	$$ O(1) $$
随机访问	$$ O(1) $$	$$ O(1) $$	$$ O(n) $$
内存连续	是	否（分段连续）	否

使用建议

主要后端操作：使用 vector
两端都操作：使用 deque
中间频繁插入删除：使用 list

priority_queue 概述

priority_queue 是优先队列，基于堆实现，支持快速获取最大/最小元素。

priority_queue 的特点

插入：$$ O(\log n) $$
删除最大/最小：$$ O(\log n) $$
获取最大/最小：$$ O(1) $$
默认大顶堆（最大元素在堆顶）

priority_queue 基本用法


#include <queue>
using namespace std;

int main() {
    // 大顶堆（默认）
    priority_queue pq;

    // 插入元素
    pq.push(5);
    pq.push(3);
    pq.push(7);
    pq.push(1);

    // 获取最大元素（堆顶）
    cout << pq.top() << endl;  // 7

    // 删除最大元素
    pq.pop();
    cout << pq.top() << endl;  // 5

    // 遍历（从小到大输出）
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    // 输出: 5 3 1

    return 0;
}

小顶堆


// 小顶堆
priority_queue, greater> min_pq;

min_pq.push(5);
min_pq.push(3);
min_pq.push(7);

cout << min_pq.top() << endl;  // 1（最小元素）

存储复杂数据类型


// 存储 pair（按 first 排序）
priority_queue> pq;

pq.push({3, 1});
pq.push({1, 2});
pq.push({2, 3});

// 按 first 从大到小
cout << pq.top().first << ", " << pq.top().second << endl;  // 3, 1
pq.pop();
cout << pq.top().first << ", " << pq.top().second << endl;  // 2, 3

// 自定义排序（按 second 从小到大）
struct cmp {
    bool operator()(pair a, pair b) {
        return a.second > b.second;  // 小顶堆
    }
};

priority_queue, vector>, cmp> pq2;
pq2.push({1, 3});
pq2.push({2, 1});
pq2.push({3, 2});

cout << pq2.top().second << endl;  // 1

priority_queue 可视化

优先队列基于堆实现，堆顶是最大/最小元素：

插入:

优先队列为空

实际应用示例

1. 合并 K 个有序链表


vector mergeKLists(vector>& lists) {
    priority_queue>, vector>>,
        greater>>> pq;

    // 将每个链表的头节点插入优先队列
    for (int i = 0; i < lists.size(); i++) {
        if (!lists[i].empty()) {
            pq.push({lists[i][0], {i, 0}});
        }
    }

    vector result;
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();

        int val = top.first;
        int list_idx = top.second.first;
        int elem_idx = top.second.second;

        result.push_back(val);

        // 插入下一个元素
        if (elem_idx + 1 < lists[list_idx].size()) {
            pq.push({lists[list_idx][elem_idx + 1], {list_idx, elem_idx + 1}});
        }
    }

    return result;
}

2. 前K个高频元素


vector topKFrequent(vector& nums, int k) {
    // 统计频率
    unordered_map freq;
    for (int num : nums) {
        freq[num]++;
    }

    // 使用小顶堆，保持堆大小为 k
    priority_queue, vector>,
        greater>> pq;

    for (auto& p : freq) {
        pq.push({p.second, p.first});
        if (pq.size() > k) {
            pq.pop();
        }
    }

    // 提取结果
    vector result;
    while (!pq.empty()) {
        result.push_back(pq.top().second);
        pq.pop();
    }

    return result;
}

3. 滑动窗口最大值


vector maxSlidingWindow(vector& nums, int k) {
    deque dq;
    vector result;

    for (int i = 0; i < nums.size(); i++) {
        // 移除滑出窗口的元素
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 保持 deque 递减（维护窗口内的最大值）
        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;
}