🔥小叶-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）的容器

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、常用接口使用

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、常用接口使用

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/