【C++STL ：stack && queue (一) 】STL：stack与queue全解析｜深入使用（附高频算法题详解）
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的简介：
🎬艾莉丝的C++专栏简介：
目录
C++的两个参考文档
老朋友（非官方文档）：cplusplus
官方文档（同步更新）：cppreference
stack容器文档链接：stack
queue容器文档链接：queue
1 ~> stack && queue的使用层
1.1 stack的使用
1.1.1 使用：表格整理
| 函数说明 | 接口说明 | 参数说明 | 返回值说明 | 时间复杂度 |
|---|---|---|---|---|
| stack() | 构造空的栈 | 无参数 | 无返回值 | O(1) |
| empty() | 检测stack是否为空 | 无参数 | 返回bool值，true为空，false为非空 | O(1) |
| size() | 返回stack中元素的个数 | 无参数 | 返回size_t类型的元素数量 | O(1) |
| top() | 返回栈顶元素的引用 | 无参数 | 返回栈顶元素的const引用 | O(1) |
| push() | 将元素val压入stack中 | const T& val (要压入的元素) | 无返回值 | 平均O(1) |
| pop() | 将stack中尾部的元素弹出 | 无参数 | 无返回值 | O(1) |
1.2 queue的使用
1.2.1 文档内容理解
1、队列是一种容器适配器，专门用于在FIFO上下文（先进先出）中操作，其中从容器一端插入元
素，另一端提取元素。
2、队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供
一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3、底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少
支持以下操作——
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
4、标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器
类，则使用标准容器deque。
1.2.2 使用表格整理
| 函数声明 | 接口说明 | 参数说明 | 返回值说明 | 时间复杂度 | 注意事项 |
|---|---|---|---|---|---|
| queue() | 构造空的队列 | 无参数 | 无返回值 | O(1) | 创建空的队列对象 |
| empty() | 检测队列是否为空，是返回true，否则返回false | 无参数 | 返回bool值，true为空，false为非空 | O(1) | 在操作队列前应先检查是否为空 |
| size() | 返回队列中有效元素的个数 | 无参数 | 返回size_t类型的元素数量 | O(1) | 获取当前队列长度 |
| front() | 返回队头元素的引用 | 无参数 | 返回队头元素的const引用 | O(1) | 队列为空时调用行为未定义 |
| back() | 返回队尾元素的引用 | 无参数 | 返回队尾元素的const引用 | O(1) | 队列为空时调用行为未定义 |
| push() | 在队尾将元素val入队列 | const T& val (要入队的元素) | 无返回值 | 平均O(1) | 在队列尾部添加新元素 |
| pop() | 将队头元素出队列 | 无参数 | 无返回值 | O(1) | 队列为空时调用行为未定义 |
1.3 使用层（Test.cpp文件）
运行一下——
2 ~> stack && queue算法题练习
2.1 stack
2.1.1 最小栈
力扣链接：LCR 147. 最小栈
（和155. 最小栈一样，随便点哪个链接都可以）
力扣题解链接：额外创建一个栈解决
题目描述：
博主手记——
代码演示——
class MinStack { public: /** initialize your data structure here. */ MinStack() { // 不用管，甚至可以直接删掉这个函数 // 留着也可以，会调用默认构造 } void push(int val) { _st.push(val); if(_minst.empty() || val <= _minst.top()) _minst.push(val); } void pop() { if(_st.top() == _minst.top()) _minst.pop(); _st.pop(); } int top() { return _st.top(); } int getMin() { return _minst.top(); } private: stack<int> _st; stack<int> _minst; }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */2.1.2 逆波兰表达式
力扣链接：150. 逆波兰表达式求值
力扣题解链接：后缀法 && 操作符紧跟操作数 && switch...case...语句解决
题目描述：
博主手记——
代码演示——
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for(auto& str : tokens) { // 判断四种运算符 if(str == "+" || str == "-" || str == "*" || str == "/") { // 运算符 int right = st.top(); st.pop(); int left = st.top(); st.pop(); switch(str[0]) // 大坑：switch...case语句只能是int类型 { case '+': st.push(left + right); break; case '-': st.push(left - right); break; case '*': st.push(left * right); break; case '/': st.push(left / right); break; } } else { // 运算数 st.push(stoi(str)); // 字符串转整型，to_string } } return st.top(); } };2.1.3 栈的压入、弹出序列
牛客网链接：JZ31 栈的压入、弹出序列
题目描述：
博主手记——
代码演示——
#include <iterator> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型 */ bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { // 定义两个下标，分别指向入栈和出栈序列 size_t pushi = 0,popi = 0; stack<int> st; // 定义一个栈 while(pushi < pushV.size()) { st.push(pushV[pushi]); while(!st.empty() && st.top() == popV[popi]) { st.pop(); popi++; // 弹出一次，popi往后走 } // pushi往后走 pushi++; } // 是返回true，否返回false return st.empty(); } };2.2 queue
2.2.1 用队列实现栈
力扣链接：225. 用队列实现栈
题目描述：
这道题博主这里不做演示。
2.2.2 二叉树的层序遍历
力扣链接：102. 二叉树的层序遍历
力扣题解链接：队列解决【二叉树的层序遍历】问题
题目描述：
博主手记——
代码演示——
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; // 创建一个新变量levelSize，记录层数,一层一层出 int levelSize = 0; if(root) { q.push(root); levelSize = 1; } // 设计很精妙 vector<vector<int>> vv; while(!q.empty()) // 不为空就继续，为空就跳出循环 { // 一层一层出完 vector<int> v; while(levelSize--) // 一层一层出 { TreeNode* front = q.front(); // 队头 q.pop(); v.push_back(front->val); // 放到队列里面，先进先出，后进后出 if(front->left) q.push(front->left); // 左子节点 if(front->right) q.push(front->right); // 右子节点 } vv.push_back(v); levelSize = q.size(); } return vv; } };本文代码完整展示
Test.cpp：
#define _CRT_SECURE_NO_WARNINGS 1 // stack 和 queue的使用：构造、增删 #include<iostream> #include<stack> #include<queue> using namespace std; int main() { // 栈(stack)的使用演示 stack<int> st; st.push(1); st.push(2); st.push(3); st.emplace(4); // emplace是C++11的高效插入 // 遍历并清空栈 (LIFO: 后进先出) while (!st.empty()) { cout << st.top() << " "; // 输出栈顶元素：4 3 2 1 st.pop(); // 弹出栈顶元素 } cout << endl; // 队列(queue)的使用演示 queue<int> q; q.push(1); q.push(2); q.push(3); q.emplace(4); // emplace是C++11的高效插入 while (!q.empty()) { cout << q.front() << " "; // 输出队头元素 q.pop(); // 出队 } return 0; }结尾
往期回顾：
【C++STL ：list类 (二) 】list vs vector：终极对决与迭代器深度解析 && 揭秘list迭代器的陷阱与精髓
结语：都看到这里啦！那请大佬不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
