C++初阶(11)/STL(四)：stack和queue

💬 ：如果你在阅读过程中有任何疑问或想要进一步探讨的内容，欢迎在评论区畅所欲言！我们一起学习、共同成长~！

👍 ：如果你觉得这篇文章还不错，不妨顺手点个赞、加入收藏，并分享给更多的朋友噢~！

1. 容器适配器概述

容器适配器是一种设计模式，自身不直接存储数据，而是将一个类的接口转换为另一个接口，使原本不兼容的类能够协同工作。

STL中，stack、queue、priority_queue均属于容器适配器，而非独立容器，它们的功能依赖底层容器实现。

STL中stack和queue默认使用deque作为底层容器，核心原因如下：

1. deque是双开口分段连续空间，头尾插删操作无需搬移元素。
2. 扩容时无需搬移大量元素，效率优于vector；无需存储额外指针，空间利用率高于list。
3. stack和queue无迭代器，不支持遍历，从而避开deque遍历效率低的缺陷。

stack 和 queue 不提供迭代器的核心原因是维护自身核心特性与简化接口，具体如下：

1. stack（LIFO）仅允许访问栈顶，queue（FIFO）仅允许访问队头和队尾。迭代器提供遍历容器的能力，用户可能通过迭代器访问、修改中间元素，直接破坏它们 “严格限制访问顺序” 的核心设计。
2. stack 和 queue 基于底层容器封装简化的接口，屏蔽底层复杂的存储细节。若提供迭代器会暴露底层容器的实现，违背 “封装底层、提供统一简单接口” 的设计初衷。

2. 定义

2.1 stack的定义

• 包含头文件<stack>
• 通过std::stack访问或使用using namespace std;

方式1：用默认的底层容器deque<T>定义栈

// std::stack<元素类型> 栈名; std::stack<int> st1;

方式2：用特定的底层容器定义栈（需包含底层容器头文件）

// std::stack<元素类型, 底层容器类型> 栈名; std::stack<int, vector<int>> st2; std::stack<int, list<int>> st3;

2.2 queue的定义

• 包含头文件<queue>
• 通过std::queue访问或使用using namespace std;

方式1：用默认的底层容器deque<T>定义队列

// std::queue<元素类型> 队列名; std::queue<int> q1;

方式2：用特定的底层容器定义队列（需包含底层容器头文件）

// std::queue<元素类型, 底层容器类型> 队列名; std::queue<int, vector<int>> q2; std::queue<int, list<int>> q3;

3. stack的使用

3.1 核心特性与常用接口

核心特性：后进先出（LIFO，Last-In-First-Out），顶删顶插。

常用接口：

3.2 高频OJ题

3.2.1 有效的括号（简单）

有效的括号

配对问题 + 后出现的左括号先闭合 → 栈

#include <string> #include <stack> using namespace std; class Solution { public: bool isValid(string s) { stack<char> L; for (char c : s) { if (c == '(' || c == '[' || c == '{') L.push(c); // 左括号入栈 else { // 遇1个右括号执行1次 if (L.empty()) return false; char top = L.top(); L.pop(); // 遇右括号时无论栈顶左括号是否匹配，都弹出该栈顶，这样才能检查下一个左括号 if (c == ')' && top != '(') return false; // 执行return语句后整个函数结束，该函数后续代码不执行 if (c == ']' && top != '[') return false; if (c == '}' && top != '{') return false; } } return L.empty(); } };

3.2.2 用两个栈实现队列（简单）

用栈实现队列

设计两个栈，

1. inStack（插入元素，模拟队尾入队）：（栈底）[1，2，3|⬅
2. outStack（弹出元素，模拟队首出队）：[3，2，1|（栈顶）➡

inStack元素依次放入outStack，反转元素顺序模拟队列 ⬅（队首）|1，2，3|（队尾）⬅

#include <stack> using namespace std; class MyQueue { private: stack<int> inStack, outStack; void transfer() { // inStack ：1（栈底），2，3 → outStack ：3，2，1（栈顶） while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: MyQueue() {} void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { transfer(); } int x = outStack.top(); outStack.pop(); return x; // 题目示例有返回 } int peek() { // 获取队首元素 if (outStack.empty()) { transfer(); } return outStack.top(); } bool empty() { return inStack.empty() && outStack.empty(); } };

3.2.3 栈的压入、弹出序列

栈的压入弹出序列

解题思路：关键看示例1的说明“push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true”，第一个序列元素持续入栈，直到栈顶 = 第二个序列当前数。

#include <vector> #include <stack> using namespace std; class Solution { public: bool IsPopOrder(vector<int> pushV, vector<int> popV) { stack<int> s; int n = pushV.size(); int j = 0; for (int i = 0; i < n; i++) { // 遍历弹出序列 //栈为空或者栈顶不等于弹出序列当前数，则第一个序列元素持续入栈 while (j < n && (s.empty() || s.top() != popV[i])) { s.push(pushV[j]); j++; } if (s.top() == popV[i]) s.pop(); //栈顶等于出栈数组，while不执行，向下执行 else return false; // 压入序列元素全部入过栈，栈顶还不等时 } return true; } };

3.2.4 最小栈（中等）

最小栈

核心思路：用「主栈」存储所有元素，「辅助栈」仅存储当前最小值。

#include <stack> using namespace std; class MinStack { private: stack<int> dataSt; // 存储所有入栈元素 stack<int> minSt; // 辅助栈：同步记录当前最小值，栈顶=当前最小值 public: MinStack() {} void push(int val) { dataSt.push(val); if (minSt.empty() || val <= minSt.top()) { // minSt.empty()时第一个元素，直接入栈 // val <= minSt.top() 更新栈顶最小值 minSt.push(val); } else { // 当前元素不是最小值 minSt.push(minSt.top()); // 重复压入辅助栈栈顶元素，保持两栈长度一致，同一位置的两栈元素就是当前插入元素和插入后当前最小值 } } void pop() { dataSt.pop(); minSt.pop(); // 保持两栈长度一致 } int top() { return dataSt.top(); } int getMin() { return minSt.top(); } };

3.2.5 逆波兰表达式求值（中等）

逆波兰表达式求值

核心思路：遍历表达式中的每个元素，若当前元素是 “数字”，转换成整数后入栈；若当前元素是 “运算符”，从栈中弹出两个操作数（“左操作数”先入栈，则后出栈）。用当前运算符计算，计算结果压入栈。

#include <stack> #include <vector> #include <string> using namespace std; class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for (const string& token : tokens) { if (token == "+" || token == "-" || token == "*" || token == "/") { // 先后弹出右操作数、左操作数 int right = st.top(); st.pop(); int left = st.top(); st.pop(); if (token == "+") st.push(left + right); else if (token == "-") st.push(left - right); else if (token == "*") st.push(left * right); else if (token == "/") st.push(left / right); } else // 数字入栈（字符串转整数） { // stoi(str)将一个字符串转换成一个整数（stoi是 string to integer 的缩写） st.push(stoi(token)); } } return st.top(); } };

3.3 底层vector模拟实现stack（必掌握）

#include <vector> namespace lyl { // 自定义命名空间，避免与STL::stack冲突 template<class T> class atsck { public: stack() {} void push(const T& x) { _v.push_back(x); } void pop() { _v.pop_back(); } T& top() { // 非const版：可修改栈顶元素 return _v.back(); } const T& top() const { // const版：不可修改栈顶元素 // 返回值前的const防止外部通过返回值修改对象内部数据 // 函数声明末尾的const保证函数内部不会修改对象的任何状态 return _v.back(); } bool empty() const { return _v.empty(); } size_t size() const { return _v.size(); } private: std::vector<T> _v; }; }

面试中，这是最常考的 “stack 模拟实现” 写法，必须能默写代码，并解释清楚三个高频问题：

（1）为什么用 vector 作底层：

1. 时间匹配：vector尾操作（push_back/pop_back/back）均O(1)，契合栈 LIFO 只在一端存取的特性。
2. 内存省心：vector 自动扩容释放，不用手动管理数组内存，规避野指针、内存泄漏。
3. 代码复用：直接复用容器已有接口，无需自研动态数组，开发成本低。

（2）top () 的 const / 非const 版本

（3）STL 容器的 pop 统一无返回值——接口单一职责（pop只管删，back/front只管取值）；避免返回异常。

4. queue的使用

4.1 核心特性与常用接口

核心特性：先进先出（FIFO，First-In-First-Out），头删尾插。

4.2 高频OJ题

4.2.1 用队列实现栈（简单）

用队列实现栈

核心思路：栈先进后出，队列先进先出。主队列存储元素；辅助队列临时转移元素，实现尾元素的删除/获取。

#include <queue> using namespace std; class MyStack { private: queue<int> q1; // 主：存储元素 queue<int> q2; // 辅：临时转移元素，实现尾元素的删除/获取 public: MyStack() {} void push(int x) { q1.push(x); } int pop() { while (q1.size() > 1) { q2.push(q1.front()); q1.pop(); } int top_val = q1.front(); q1.pop(); swap(q1, q2); // 使q1仍作存储当前未出列元素的主队列 return top_val; } int top() { while (q1.size() > 1) { q2.push(q1.front()); q1.pop(); } int top_val = q1.front(); q2.push(q1.front()); q1.pop(); swap(q1, q2); // 使q1仍作存储当前未出列元素的主队列 return top_val; } bool empty() { return q1.empty(); } };

4.3 底层list模拟实现queue

#include <list> namespace lyl { // 自定义命名空间，避免与STL::queue冲突 template<class T> class queue { public: queue() {}; void push(const T& x) { _lt.push_back(x); } void pop() { _lt.pop_front(); } T& front() { return _lt.front(); } const T& front() const { // 返回值前的const防止外部通过返回值修改对象内部数据 // 函数声明末尾的const保证函数内部不会修改对象的任何状态 return _lt.front(); } T& back() { return _lt.back(); } const T& back() const { return _lt.back(); } bool empty() const { return _lt.empty(); } size_t size() const { return _lt.size(); } private: std::list<T> _lt; }; }

（1）底层选list原因

1. list头尾操作均O(1)，契合queue头删尾插需求。而vector头删O(n)。
2. list 自动管理节点堆内存，无需手动开辟释放。
3. 直接复用 list 现成接口，不用自己实现双向链表。

（2）front/back 分 const / 非const 版本

5. 优先队列（priority_queue）

5.1 核心特性与常用接口

priority_queue是一种容器适配器，其底层实现通常基于堆（Heap）数据结构。队头对应堆顶。

核心特性：每次可以取出优先级最高的元素。默认实现大顶堆（堆顶元素最大）。

常用接口：

关键注意点：

• 使用priority_queue包含头文件<queue> 。
• 使用using namespace std; 或 std::priority_queue 。
• priority_queue不提供迭代器，无法遍历。（面试高频）
• 默认实现大顶堆（堆顶元素最大）。如果需要实现小顶堆，需要显式指定模板参数。

5.2 定义优先级队列对象

priority_queue的比较规则是：a优先级低于b的条件。

（1）默认大顶堆（➡ 比较规则less<T> ➡ a<b）

#include <queue> using namespace std; priority_queue<int> pq; // 等价于priority_queue<int, vector<int>, less<int>> pq;

（2）显式定义小顶堆（➡ greater<T> ➡ a>b）（笔试必考）

#include <queue> #include <vector> #include <functional> // greater using namespace std; // priority_queue<存储类型, 底层容器, 比较函数> 对象名; priority_queue<int, vector<int>, greater<int>> minHeap;

5.3 存储自定义类型

当priority_queue存储自定义类型（如struct）时，编译器无法自动判断两个对象的优先级。因此，必须显式地定义一个比较规则。这个规则必须是严格弱序（不能用 <= >= == 做比较，只能用 < > 实现）。

通常有两种方式来定义这个规则：

5.3.1 方式一：类内重载operator<(默认大顶堆)

缺点：一个类只能固定一套比较规则。

class 类名{ public: bool operator<(const 类名& other) const{ return 比较字段 < other.比较字段; // 即 return this->score < other.score; 当前对象比右边对象低分 } private: 成员变量; }; priority_queue<类名> pq;

简单示例：分数高优先（排前）

#include<queue> #include<string> #include<iostream> using namespace std; struct Stu{ string name; int score; bool operator<(const Stu& s) const{ return score < s.score; } }; int main(){ priority_queue<Stu> pq; pq.push({"A",80}); pq.push({"B",95}); pq.push({"C",88}); while(!pq.empty()){ cout<<pq.top().score<<" "; //95→88→80 pq.pop(); } return 0; }

如果需要小顶堆（分数低在前），可重载operator>，并且定义priority_queue<Stu,vector<Stu>,greater<Stu>> minHeap;

5.3.2 方式二：自定义比较结构体cmp

1. 类外单独定义一个结构体；
2. 结构体内部重载operator()，做成仿函数；
3. 此结构体作为 priority_queue第三个参数。
4. cmp(a,b)=true：a 优先级低，a下沉 / 后放。

class 类名{}; //类外比较结构体 struct cmp{ bool operator()(const 类名&a,const 类名&b) const{ return a.字段 运算符 b.字段; } }; priority_queue<类名,vector<类名>,cmp> q; //存储类型、底层容器、比较函数

简单示例：分数低优先

#include <queue> #include <vector> #include <string> #include <iostream> using namespace std; struct Stu{ string name; int score; }; struct cmp{ bool operator()(const Stu& a,const Stu& b) const{ return a.score > b.score; } }; int main(){ priority_queue<Stu,vector<Stu>,CmpMin> pq; pq.push({"A",80}); pq.push({"B",95}); pq.push({"C",88}); while(!pq.empty()){ cout<<pq.top().score<<" "; // 80→88→95 pq.pop(); } return 0; }

5.4 高频OJ题—Top K 问题

Top K 问题最通用的解题方法是堆（priority_queue）和快速排序。

5.4.1 堆解法

堆解法核心思想：

1. 求 第 K 大 或 前 K 大 → 维护一个大小为 K 的 小顶堆（堆顶是当前 K 个元素中的最小值）。
2. 求 第 K 小 或 前 K 小 → 维护一个大小为 K 的 大顶堆（堆顶是当前 K 个元素中的最大值）。

数组中的第K个最大元素

数组中的第K个最大元素

#include<vector> #include<queue> #include <functional> using namespace std; class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> minHeap; for (int i = 0; i < k; i++) { minHeap.push(nums[i]); } for (int i = k; i < nums.size(); i++) { if (nums[i] > minHeap.top()) { minHeap.pop(); minHeap.push(nums[i]); } } return minHeap.top(); } };

5.5 模拟实现priority_queue

#include <iostream> // cout #include <vector> #include <algorithm> // make_heap, push_heap, pop_heap #include <functional> // less #include <stdexcept> // throw out_of_range namespace lyl // 自定义命名空间，防止与std::priority_queue冲突 { template<class T,class Container=std::vector<T>,class Compare=std::less<T>> class priority_queue { public: priority_queue():c() {} // 无参构造，创建空的优先队列 // 迭代器区间构造（用其他容器的元素初始化） template<class InputIterator> // 方便修改容器类型 priority_queue(InputIterator first, InputIterator last) : c(first, last) { std::make_heap(c.begin(), c.end(), comp); // 调用make_heap自动建成堆 } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } const T& top() const { // 空堆调用抛异常 if (empty()) { throw std::out_of_range("priority_queue is empty"); } return c.front(); // 堆顶 = vector第一个元素 } void push(const T& val) { c.push_back(val); // vector末尾 = 堆底最后一位 std::push_heap(c.begin(), c.end(), comp); // 调用push_heap让新元素向上调整至合适位置 } void pop() { if (empty()) { throw std::out_of_range("priority_queue is empty"); } // 调用 pop_heap 交换堆顶元素（vector第一个元素）与堆底最后一位（vector最后一个元素） // 并将前n-1个元素重新调整为堆 std::pop_heap(c.begin(), c.end(), comp); c.pop_back(); // 删除当前堆底最后一位（即原堆顶） } private: Container c; // 底层容器（存储元素） Compare comp; // 比较函数对象 }; }