🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
一、搞懂基础：Stack 与 Queue 的核心特性
二、Stack（栈）：后进先出（LIFO）的容器
1、核心特性
2、头文件和定义
3、常用接口使用
4、基础用法代码演示
三、Queue（队列）：先进先出（FIFO）的容器
1、核心特性
2、头文件与定义
3、常用接口使用
4、基础用法代码演示
四、实战练习题
1、最小栈
2、栈的压入、弹出序列
3、逆波兰表达式求值
4、 二叉树的层序遍历
结束语
一、搞懂基础：Stack 与 Queue 的核心特性
在介绍相关接口以及测试代码前，首先要明确两者的 “数据访问规则”—— 这是它们区别于其他容器的关键：
| 容器 | 核心规则 | 访问特性 | 适用场景 |
| stack | 后进先出（LIFO） | 仅能访问“栈顶”元素 | 函数调用栈、表达式求值、撤销操作 |
| quene | 先进先出（FIFO） | 仅能访问“队头”和“队尾”元素 | 任务调度、消息队列、广度优先搜索（BFS） |
两者的共性是 “限制访问”：不支持随机访问（如[]下标），也不支持迭代器遍历 —— 目的是强制遵循其数据规则，避免错误的访问方式。
二、Stack（栈）：后进先出（LIFO）的容器
1、核心特性
- 访问规则：只能从"栈顶"添加或删除元素(最后入栈的元素最先出栈)
- 适用场景：函数调用栈，表达式求值等。
参考文档：stack - C++ Reference
2、头文件和定义
#include <stack> //必须包含栈的头文件 using namespace std; //定义栈：默认存储int类型，底层依赖deque实现 stack<int> st; //可指定底层容器（如vector、list） stack<int, vector<int>> st_v; // 基于vector的栈 stack<int, list<int>> st_lt; // 基于list的栈3、常用接口使用
| 接口 | 功能描述 | 示例 |
| push(val) | 向栈顶添加元素，新元素成为新的栈顶 | st.push(10); |
| pop() | 删除当前栈顶元素（操作后原栈顶的下一个元素成为新栈顶），无返回值，需先确保栈非空 | st.pop(); |
| top() | 返回栈顶元素的引用（可直接读取或修改栈顶值），需先确保栈非空 | int x = st.top(); (读取); st.top() = 20;(修改) |
| size() | 返回栈中当前存储的元素总个数，返回值为无符号整数(size_t) | cout << st.size(); |
| empty() | 判断栈是否为空，若栈中无元素则返回 true，否则返回 false | if (!st.empty()) { ... } |
4、基础用法代码演示
void test_stack() { stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } int main() { test_stack(); }三、Queue（队列）：先进先出（FIFO）的容器
1、核心特性
- 访问规则：从"队尾"添加元素，从"队头"删除元素(最先入队的元素最先出队)
- 适用场景：任务调度（如打印队列）、消息队列、广度优先搜索（BFS）等
参考文档：queue - C++ Reference
2、头文件与定义
#include <queue> //必须包含的头文件 using namespace std; //定义队列：默认底层依赖deque实现 queue<int> q; //可指定底层容器（如list，不建议用vector，因vector头删效率低） queue<int, list<int>> q_lt; // 基于list的队列3、常用接口使用
| 接口 | 功能描述 | 示例 |
| push(val) | 向队列的队尾添加一个元素，新元素成为队列的最后一个元素，操作后队列长度+1 | q.push(10); |
| pop() | 删除队列的队头元素（即最早入队的元素），操作后队列长度-1，无返回值（需先通过front()获取队头元素再删除） | q.pop(); |
| front() | 返回队列队头元素的引用（可读取或修改），仅访问不删除，需确保队列非空 | int x = q.front(); (读取); q.front() = 20;(修改) |
| back() | 返回队列队尾元素的引用（可读取或修改），仅访问不删除，需确保队列非空 | int x = q.back(); (读取); q.back() = 30;(修改) |
| size() | 返回队列中当前存储的元素总个数，返回值类型为 size_t（无符号整数） | cout << q.size(); |
| empty() | 判断队列是否为空：若队列中无元素则返回 true，有元素则返回 false，常用于遍历或删除前判断队列状态 | if (!q.empty()) { ... } |
4、基础用法代码演示
void test_queue() { queue<int> q; q.push(1); q.push(2); q.push(3); q.emplace(4); while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; } int main() { test_queue(); }四、实战练习题
1、最小栈
题目链接：
155. 最小栈 - 力扣（LeetCode）
C++算法代码：
class MinStack { public: MinStack() //调用构造函数进入函数体之前都会进行初始化列表 //如果没有显式写初始化列表对于内置类型不确定是否初始化 //对于自定义类就会调用对应的默认构造函数 { //所以可以不用写该函数 } void push(int val) { st.push(val); if(min_st.empty() || min_st.top() >= val) { min_st.push(val); } } void pop() { if(min_st.top() == st.top()) { min_st.pop(); } st.pop(); } int top() { return st.top(); } int getMin() { return min_st.top(); } stack<int> st; stack<int> min_st; };2、栈的压入、弹出序列
题目链接：
栈的压入、弹出序列_牛客题霸_牛客网
C++算法代码：
class Solution { public: bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { stack<int> st; size_t _push = 0; size_t _pop = 0; while(_push < pushV.size()) { st.push(pushV[_push]); while(!st.empty() && st.top() == popV[_pop]) { st.pop(); _pop++; } _push++; } return st.empty(); } };图解：
3、逆波兰表达式求值
题目链接：
150. 逆波兰表达式求值 - 力扣（LeetCode）
补充说明：
C++算法代码：
class Solution { public: int evalRPN(vector<string>& tokens) { for(auto str : tokens) //需要注意vector里面的数据是string类型 //下面的判断条件不要写错 //访问字符需要写出str[0]，因为每个string数据只有一个字符 { if(str == "+" || str == "-" || str == "*" || str == "/") { int right = st.top(); st.pop(); int left = st.top(); st.pop(); switch(str[0]) { 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)); //stoi可将字符串转换为整数 } } return st.top(); } stack<int> st; };4、 二叉树的层序遍历
题目链接：
102. 二叉树的层序遍历 - 力扣（LeetCode）
C++算法代码：
/** * 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) { vector<vector<int>> vv; queue<TreeNode*> q1;//队列用来存放每层的数据 size_t levelSize = 0; if(root) { q1.push(root); levelSize = 1; }//如果不是空树首先将头节点入队列 while(!q1.empty()) //q1如果为空则说明树的所有数据已经全部遍历 { vector<int> v; while(levelSize--) { TreeNode* front = q1.front(); v.push_back(front->val); if(front->left) { q1.push(front->left); //如果该节点有对应左孩子结点则入队列 } if(front->right) { q1.push(front->right); //如果该节点有对应右孩子结点则入队列 } q1.pop(); } vv.push_back(v); //当出了while循环说明当前层的数据已全部传入v中，则作为一组传给vv levelSize = q1.size(); } return vv; } };图解：
结束语
stack（栈）和 queue（队列）是 C++ 标准库中两种常用的适配器容器，它们的核心价值在于提供严格的数据访问规则（后进先出 / 先进先出），广泛应用于算法设计和业务逻辑实现。到此 stack 和 queue 的相关接口使用和相关算法题就讲解完了，相比于前面学习的所有容器，栈和队列在接口使用上是非常简单的，本篇文章主要是对栈和队列的相关算法题进行讲解，下篇文章我们就要对栈和队列进行模拟实现。希望这篇文章对大家学习C++能有所帮助！
C++参考文档：
https://legacy.cplusplus.com/reference/
https://zh.cppreference.com/w/cpp
https://en.cppreference.com/w/
-无迹卡尔曼滤波(UKF))
