本篇目标学会stackqueue和priority_queue的接口使用引子stack、queue和priority_queue都属于容器适配器。它们不直接负责存储数据而是在其他容器的基础上封装出一组特定接口。#include stack #include queue #include vector #include functional using namespace std;一.stack1. 基本特点stack是栈遵循后进先出原则即 LIFOLast In First Out。只能直接访问栈顶元素入栈1 2 3 出栈3 2 1默认情况下stack使用deque作为底层容器。2. 常用接口接口功能时间复杂度stackT st构造一个空栈O(1)st.empty()判断栈是否为空O(1)st.size()返回元素个数O(1)st.top()访问栈顶元素O(1)st.push(x)将元素压入栈顶O(1)st.pop()删除栈顶元素O(1)基本使用#include iostream #include stack using namespace std; int main() { stackint st; st.push(10); st.push(20); st.push(30); while(!st.empty()) { coutst.top()endl; st.pop(); } return 0; }3. 使用特点pop()只删除不返回元素下面的写法是错误的int value st.pop(); // 错误正确写法int value st.top(); st.pop();访问栈顶前应先判断是否为空if (!st.empty()) { cout st.top() endl; }空栈调用top()或pop()会产生未定义行为。4.有效的括号网址20. 有效的括号 - 力扣LeetCode20. 有效的括号 - 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。有效字符串需满足 1. 左括号必须用相同类型的右括号闭合。 2. 左括号必须以正确的顺序闭合。 3. 每个右括号都有一个对应的相同类型的左括号。 示例 1输入s ()输出true示例 2输入s ()[]{}输出true示例 3输入s (]输出false示例 4输入s ([])输出true示例 5输入s ([)]输出false 提示 * 1 s.length 104 * s 仅由括号 ()[]{} 组成https://leetcode.cn/problems/valid-parentheses/1.题意解释给定一个只包含(、)、[、]、{、}的字符串判断其中的括号是否正确匹配。例如()[]{} → true ([{}]) → true (] → false ([)] → false2.解题思路括号匹配需要满足左括号和右括号的类型必须相同。后出现的左括号必须先匹配。例如([{}])左括号进入顺序( → [ → {右括号出现后匹配顺序必须是} → ] → )这正好符合栈“后进先出”的特点。具体过程遇到左括号将其压入栈中。遇到右括号检查栈顶左括号是否与其匹配。如果栈为空说明右括号没有对应的左括号返回false。如果类型不匹配返回false。如果匹配就将栈顶左括号弹出。遍历结束后栈必须为空否则说明存在未匹配的左括号。3.示例分析以字符串([{}])为例当前字符操作栈中内容(左括号入栈([左括号入栈([{左括号入栈([{}与{匹配出栈([]与[匹配出栈()与(匹配出栈空遍历结束后栈为空因此括号匹配成功。两种失败情况1.右括号多())处理最后一个)时栈已经为空匹配失败。2.左括号多(()遍历结束后栈中还有一个(匹配失败。因此最后不能直接返回true必须返回return st.empty();4.代码实现class Solution { public: bool isValid(string s) { stackchar st; for (char ch : s) { // 遇到左括号直接入栈 if (ch ( || ch [ || ch {) { st.push(ch); } else { // 右括号过多 if (st.empty()) { return false; } char top st.top(); // 判断括号类型是否匹配 if ((ch ) top ! () || (ch ] top ! [) || (ch } top ! {)) { return false; } // 当前左右括号匹配 st.pop(); } } // 栈为空说明所有左括号都完成匹配 return st.empty(); } };二.queue1. 基本特点queue是队列遵循先进先出原则即 FIFOFirst In First Out。元素从队尾进入从队头离开入队1 2 3 出队1 2 3默认情况下queue使用deque作为底层容器。2. 常用接口接口功能时间复杂度queueT q构造一个空队列O(1)q.empty()判断队列是否为空O(1)q.size()返回元素个数O(1)q.front()访问队头元素O(1)q.back()访问队尾元素O(1)q.push(x)从队尾插入元素O(1)q.pop()删除队头元素O(1)基本使用#include iostream #include queue using namespace std; int main() { queueint q; q.push(10); q.push(20); q.push(30); while(!q.empty()) { coutq.front() ; q.pop(); } return 0; }3. 使用特点队头和队尾的作用不同q.front(); // 下一个将要出队的元素 q.back(); // 最后一个进入队列的元素pop()只删除队头不返回元素int value q.front(); q.pop();访问元素前要判断队列是否为空if (!q.empty()) { cout q.front() endl; }4.用队列实现栈225. 用队列实现栈 - 力扣LeetCode225. 用队列实现栈 - 请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。实现 MyStack 类 * void push(int x) 将元素 x 压入栈顶。 * int pop() 移除并返回栈顶元素。 * int top() 返回栈顶元素。 * boolean empty() 如果栈是空的返回 true 否则返回 false 。 注意 * 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 * 你所使用的语言也许不支持队列。 你可以使用 list 列表或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。 示例输入[MyStack, push, push, top, pop, empty][[], [1], [2], [], [], []]输出[null, null, null, 2, 2, false]解释MyStack myStack new MyStack();myStack.push(1);myStack.push(2);myStack.top(); // 返回 2myStack.pop(); // 返回 2myStack.empty(); // 返回 False 提示 * 1 x 9 * 最多调用100 次 push、pop、top 和 empty * 每次调用 pop 和 top 都保证栈不为空 进阶你能否仅用一个队列来实现栈。https://leetcode.cn/problems/implement-stack-using-queues/1.题目解析只使用队列实现栈的push(x) pop() top() empty()2.解题思路队列是先进先出栈是后进先出。准备两个队列queueint q1; queueint q2;规定q1.front()始终表示栈顶。插入新元素x时先把x放入空队列q2将q1中原来的元素依次转移到q2交换q1和q2。例如原来的栈为栈顶 - 3 2 1对应队列队头 - 3 2 1插入4时q24然后把q1中的元素转移过来q24 3 2 1所以新元素4位于队头也就相当于栈顶。3.代码实现class MyStack { public: void push(int x) { // 新元素先进入辅助队列 q2.push(x); // 将原来的元素移动到新元素后面 while (!q1.empty()) { q2.push(q1.front()); q1.pop(); } // q1继续作为主队列 swap(q1, q2); } int pop() { int value q1.front(); q1.pop(); return value; } int top() { return q1.front(); } bool empty() { return q1.empty(); } private: queueint q1; queueint q2; };三.priority_queue1. 基本特点priority_queue称为优先队列。普通队列按照进入顺序出队优先队列则按照元素的优先级出队。默认情况下数值越大的元素优先级越高。priority_queue的底层结构是堆默认使用vector存储数据。插入顺序3 1 8 5 弹出顺序8 5 3 12. 常用接口接口功能时间复杂度priority_queueT pq构造一个空优先队列O(1)pq.empty()判断是否为空O(1)pq.size()返回元素个数O(1)pq.top()访问优先级最高的元素O(1)pq.push(x)插入元素O(log N)pq.pop()删除优先级最高的元素O(log N)3. 大堆与小堆priority_queue默认创建大堆堆顶是最大元素priority_queueint pq; pq.push(3); pq.push(8); pq.push(1); cout pq.top() endl; // 8使用greater创建小堆堆顶是最小元素priority_queueint, vectorint, greaterint pq; pq.push(3); pq.push(8); pq.push(1); cout pq.top() endl; // 1小堆需要包含#include functional模板参数含义priority_queue int, // 元素类型 vectorint, // 底层容器 greaterint // 比较方式 pq;可以简单记忆为priority_queueint // 大堆 priority_queueint, vectorint, greaterint // 小堆4. 使用特点top()表示优先级最高的元素它不一定是最先插入的元素priority_queueint pq; pq.push(10); pq.push(50); pq.push(20); cout pq.top() endl; // 50pop()同样不返回元素int value pq.top(); pq.pop();不支持遍历和随机访问priority_queue不提供迭代器也不能使用下标访问。只能不断读取并删除堆顶while (!pq.empty()) { cout pq.top() ; pq.pop(); }5.数组中的第K大个最大元素215. 数组中的第K个最大元素 - 力扣LeetCode215. 数组中的第K个最大元素 - 给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1:输入: [3,2,1,5,6,4], k 2输出: 5示例 2:输入: [3,2,3,1,2,4,5,5,6], k 4输出: 4 提示 * 1 k nums.length 105 * -104 nums[i] 104https://leetcode.cn/problems/kth-largest-element-in-an-array/1.题目解析给定整数数组nums和整数k返回数组中第k个最大的元素。注意是排序后的第k大不是第k个不同的元素。例如nums [3,2,1,5,6,4] k 2排序后为6 5 4 3 2 1第二大的元素是5。2.思路priority_queueint默认是大堆堆顶始终是当前最大元素。处理步骤将数组中的所有元素放入大堆弹出前k-1个最大元素此时堆顶就是第k大的元素。例如堆顶弹出顺序6、5、4、3、2、1当k 2时只需要弹出最大的6剩下的堆顶5就是答案。3.代码class Solution { public: int findKthLargest(vectorint nums, int k) { // 使用数组区间直接构造大堆 priority_queueint pq(nums.begin(), nums.end()); // 删除前k-1个最大元素 for (int i 0; i k - 1; i) { pq.pop(); } // 此时堆顶就是第k大的元素 return pq.top(); } };也可以逐个插入priority_queueint pq; for (int value : nums) { pq.push(value); }总结stack、queue和priority_queue都属于容器适配器它们在底层容器的基础上提供不同的元素访问与删除规则。stack遵循后进先出原则通过top()访问栈顶适合解决括号匹配等问题queue遵循先进先出原则通过front()访问队头适合按顺序处理数据priority_queue按优先级取出元素默认使用大堆也可以通过greater创建小堆适合求最大值、最小值以及处理 Top K 问题。使用时需要注意三者的pop()都只删除元素不返回元素访问或删除元素前应保证容器非空。掌握它们各自的处理顺序和常用接口才能根据具体问题选择合适的工具。