C++ stack和queue的使用和模拟（含deque容器的底层解析）
栈和队列的概念详细解析请移步我写的博客
1. stack的使用
因为STL容器接口的通用性，所以接口的使用我就简单的讲一讲。
其实更常用的接口这一张表就足够说明 接口的详情请移步C++文档查阅。
| 函数说明 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测 stack 是否为空 |
| size() | 返回 stack 中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素 val 压入 stack 中 |
| pop() | 将 stack 中尾部的元素弹出 |
以下是对 std::stack 成员函数的介绍及简单示例： |
1.1. (constructor)（构造函数）
用于创建栈对象，可默认构造空栈，也可基于指定容器构造。
示例：
#include <stack>
#include <vector>
int main() {
std::stack<int> s1; // 默认构造空栈
std::vector<int> v = {1,2,3};
std::stack<int, std::vector<int>> s2(v); // 基于vector构造栈
return 0;
}
1.2. empty
检测栈是否为空，空则返回 true，否则返回 false。
示例：
std::stack<int> s;
if (s.empty()) {
std::cout << "栈为空" << std::endl;
}
s.push(10);
if (!s.empty()) {
std::cout << "栈不为空" << std::endl;
}
1.3. size
返回栈中元素的个数。
示例：
std::stack<int> s;
s.push(1);
s.push(2);
std::cout << "栈的大小：" << s.size() << std::endl; // 输出2
1.4. top
返回栈顶元素的引用，可用于读取或修改栈顶元素（非 const 版本）。
示例：
std::stack<int> s;
s.push(10);
std::cout << "栈顶元素：" << s.top() << std::endl; // 输出10
s.top() = 20;
std::cout << "修改后栈顶元素：" << s.top() << std::endl; // 输出20
1. 5. push
将元素压入栈顶（支持拷贝或移动语义）。
示例：
std::stack<int> s;
s.push(1); // 拷贝压入
s.push(2);
1.6. emplace（C++11及以上）
在栈顶原地构造元素，避免额外拷贝/移动，效率更高。
示例：
struct Point {
int x, y;
Point(int a, int b) : x(a), y(b) {}
};
std::stack<Point> s;
s.emplace(3, 4); // 原地构造Point(3,4)
std::cout << "栈顶元素坐标：" << s.top().x << "," << s.top().y << std::endl; // 输出3,4
1.7. pop
移除栈顶元素（无返回值，需先通过 top 获取再删除）。
示例：
std::stack<int> s;
s.push(10);
s.push(20);
s.pop(); // 移除20
std::cout << "栈顶元素：" << s.top() << std::endl; // 输出10
1.8. swap（C++11及以上）
交换两个栈的内容。
示例：
std::stack<int> s1, s2;
s1.push(1);
s2.push(2);
s1.swap(s2);
std::cout << "s1栈顶：" << s1.top() << ", s2栈顶：" << s2.top() << std::endl; // 输出s1栈顶：2, s2栈顶：1
1.9. 迭代器相关的注意事项（容器适配器）
注意stack不支持迭代器 因为这样就无法保证栈独有的后进先出的特性。
本篇的4.0 章节 我会深入探讨一下 C++ 中的容器适配器（Container Adapters）。
2.queue的使用
详情请移步文档查阅
下面这些都是queue最常用的接口：
| 函数声明 | 接口说明 |
|---|---|
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空,是返回 true ,否则返回 false |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素 val 入队列 |
| pop() | 将队头元素出队列 |
以下是对 std::queue 成员函数的介绍及简单示例：
2.1. (constructor)（构造函数）
用于创建队列对象，可默认构造空队列，也可基于指定容器构造。
示例：
#include <queue>
#include <list>
int main() {
std::queue<int> q1; // 默认构造空队列
std::list<int> l = {1,2,3};
std::queue<int, std::list<int>> q2(l); // 基于list构造队列
return 0;
}
2.2. empty
检测队列是否为空，空则返回 true，否则返回 false。
示例：
std::queue<int> q;
if (q.empty()) {
std::cout << "队列为空" << std::endl;
}
q.push(10);
if (!q.empty()) {
std::cout << "队列不为空" << std::endl;
}
2.3. size
返回队列中元素的个数。
示例：
std::queue<int> q;
q.push(1);
q.push(2);
std::cout << "队列的大小：" << q.size() << std::endl; // 输出2
2.4. front
返回队头元素的引用，可用于读取或修改队头元素（非 const 版本）。
示例：
std::queue<int> q;
q.push(10);
q.push(20);
std::cout << "队头元素：" << q.front() << std::endl; // 输出10
q.front() = 15;
std::cout << "修改后队头元素：" << q.front() << std::endl; // 输出15
2.5. back
返回队尾元素的引用，可用于读取或修改队尾元素（非 const 版本）。
示例：
std::queue<int> q;
q.push(10);
q.push(20);
std::cout << "队尾元素：" << q.back() << std::endl; // 输出20
q.back() = 25;
std::cout << "修改后队尾元素：" << q.back() << std::endl; // 输出25
2.6. push
将元素压入队尾（支持拷贝或移动语义）。
示例：
std::queue<int> q;
q.push(1); // 拷贝压入
q.push(2);
2.7. emplace（C++11及以上）
在队尾原地构造元素，避免额外拷贝/移动，效率更高。
示例：
struct Point {
int x, y;
Point(int a, int b) : x(a), y(b) {}
};
std::queue<Point> q;
q.emplace(3, 4); // 原地构造Point(3,4)
std::cout << "队尾元素坐标：" << q.back().x << "," << q.back().y << std::endl; // 输出3,4
2.8. pop
移除队头元素（无返回值，需先通过 front 获取再删除）。
示例：
std::queue<int> q;
q.push(10);
q.push(20);
q.pop(); // 移除10
std::cout << "队头元素：" << q.front() << std::endl; // 输出20
2.9. swap（C++11及以上）
交换两个队列的内容。
示例：
std::queue<int> q1, q2;
q1.push(1);
q2.push(2);
q1.swap(q2);
std::cout << "q1队头：" << q1.front() << ", q2队头：" << q2.front() << std::endl; // 输出q1队头：2, q2队头：1
3.例题部分
3.1 最小栈
题目链接
我们这道题思路是 创建两个栈 一个存储数据 一个栈顶存储最小数据（包括最小值相等情况）。
为什么这么说？因为当你左边st删除栈顶元素，如果删除元素与minset栈顶相等，你右边minst也要删除栈顶元素，如果第二次的1不进入minset 那么你此时栈最小元素不就变成了3了吗？
class MinStack {
public:
MinStack() {}//走初始化列表，自定义类型会调用他的默认构造，所以不写也没事
void push(int val) {
_st.push(val);
if(_minset.empty() ||val<=_minset.top())
_minset.push(val);
}
void pop() {
if(_st.top()==_minset.top())
_minset.pop();
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minset.top();
}
private:
stack<int> _st;
stack<int> _minset;
};
3.2 栈的压入、弹出序列
题目链接
这道题的思路就是模拟进出栈 如果模拟通过则说明合法 不通过则说明非法 我们可以定义两个下标pushi和popi pushi指向数据入栈，然后持续让栈里里面的数据跟popi指向出栈比较相等，则popi++，出栈顶数据，直到栈为空，或者不匹配。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型vector
* @param popV int整型vector
* @return bool布尔型
*/
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
// write code here
stack<int> st;
size_t pushi=0,popi=0;
while(pushi<pushV.size())
{
//入栈序列入栈
st.push(pushV[pushi++]);
//栈顶尝试跟出栈序列匹配
while(!st.empty()&&st.top()==popV[popi])
{
popi++;
st.pop();
}
}
return st.empty();
}
};
3.3 逆波兰表达式求解
逆波兰表达式（Reverse Polish Notation，RPN）是一种后缀表达式，它将运算符放在操作数之后，无需括号即可明确表示运算顺序。
中缀表达式：运算符位于操作数中间，例如：1 + 2 * 3
逆波兰表达式：运算符位于操作数之后，例如：1 2 3 * +
计算规则：
遍历表达式，遇到数字则压入栈中。
遇到运算符则从栈中弹出两个元素，进行运算后将结果压回栈中。
遍历结束后，栈中剩余的元素即为结果。
示例: 计算逆波兰表达式 1 2 3 * + 4 /
- 遇到 1，压栈：[1]
- 遇到 2，压栈：[1, 2]
- 遇到 3，压栈：[1, 2, 3]
- 遇到 * ，弹出 3 和 2，计算 2*3=6，压栈：[1, 6]
- 遇到 +，弹出 6 和 1，计算 1+6=7，压栈：[7]
- 遇到 4，压栈：[7, 4]
- 遇到 /，弹出 4 和 7，计算 7/4=1（整数除法），压栈：[1]
解题思路：
- 先让运算数入栈。
- 当碰到运算符，出栈顶的两个数据运算，运算结果继续入栈。
当然这里面 我们会用到stoi函数
stoi 是 C++ 标准库中的一个函数，它的全称是 string to integer，用于将一个字符串（std::string）转换为一个整数（int）。
#include <string> // 必须包含这个头文件
int stoi(const std::string& str, size_t* pos = nullptr, int base = 10);
参数说明
- str：需要转换的字符串。
- pos（可选）：一个指针，用于存储转换停止的位置。例如，如果字符串是 “123abc”，转换到 “123” 后停止，pos 会指向 “a” 的位置。如果不需要这个信息，可以传入 nullptr（默认值）。
- base（可选）：转换时使用的进制。默认是 10（十进制）。常见的其他值有 2（二进制）、8（八进制）、16（十六进制）等。
返回值
转换成功后，返回字符串对应的整数。
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])
{
case '+':
st.push(left+right);
break;
case '-':
st.push(left-right);
break;
case '*':
st.push(left*right);
break;
case '/':
st.push(left/right);
break;
default:
break;
}
}
else
{
//运算数入栈
st.push(stoi(str));
}
}
return st.top();
}
};
3.4 二叉树的层序遍历
题目链接
层序遍历知识点请移步我的另一篇博客
我这里有两个思路 第一个思路就是创建两个队列 如图：
同时 还有一个更简单的思路 也是我这次实现的思路：
我们定义一个叫levelSize的变量和一个队列，记录当前层有多少个数据，然后利用while(levelSize--)来控制一层一层的出 出的时候再把孩子节点带进去 当前层出完了，下一层节点也都进队列了，队列数据个数就是下一层的节点个数更新levelSize的值 周而复始直到树遍历完。
/**
* 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;
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;
}
};
4. 容器适配器
4.1 什么是容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的､多数人知晓的､经过分类编目的､代码设 计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口｡
在 C++ STL 中，容器适配器是一种特殊的容器，它不直接管理数据，而是通过“包装”一个已有的基础容器（如
std::vector,std::list,std::deque），并提供一个受限的、特定的接口来适配其行为。
核心思想： 复用现有容器的功能，通过限制其接口来满足特定的数据结构需求。
4.2 深入理解适配器的工作方式
我们以 std::stack 为例，来看看适配器是如何工作的。
std::stack 的默认底层容器是 std::deque。当你使用 std::stack 时：
std::stack<int> s;
s.push(10); // 1. 调用 s 的 push 方法
s.pop(); // 2. 调用 s 的 pop 方法
背后发生的事情是：
s.push(10)会调用其内部std::deque对象的push_back(10)方法。s.pop()会调用其内部std::deque对象的pop_back()方法。s.top()会调用其内部std::deque对象的back()方法。
std::stack 就像一个“外壳”，它规定了“只能在尾部操作”这个规则，并将具体的执行细节交给了 std::deque。
4.3 如何选择和更换底层容器
选择哪种底层容器通常取决于你的性能需求：
-
std::vector：- 优点：随机访问速度快，缓存局部性好。
- 缺点：在头部或中间插入/删除元素效率低（需要移动大量元素），扩容时可能需要重新分配内存和拷贝元素。
- 适用适配器：
std::stack(因为stack只在尾部操作)。
-
std::list：- 优点：在任意位置插入/删除元素效率高（O(1)），不需要移动元素。
- 缺点：不支持随机访问，只能顺序访问，内存开销较大。
- 适用适配器：
std::stack,std::queue。
-
std::deque(双端队列)：- 优点：结合了
vector和list的部分优点。头尾两端的插入/删除效率高（O(1)），也支持随机访问（O(1)）。 - 缺点：内部实现相对复杂。
- 适用适配器：
std::stack(默认),std::queue(默认)。
- 优点：结合了
更换底层容器的示例：
#include <iostream>
#include <stack>
#include <vector>
#include <list>
int main() {
// 使用 std::vector 作为 std::stack 的底层容器
std::stack<int, std::vector<int>> stack_with_vector;
stack_with_vector.push(1);
stack_with_vector.push(2);
std::cout << "Stack with vector: " << stack_with_vector.top() << std::endl;
// 使用 std::list 作为 std::queue 的底层容器
std::list<int> my_list = {10, 20, 30};
std::queue<int, std::list<int>> queue_with_list(my_list);
std::cout << "Queue with list: " << queue_with_list.front() << std::endl;
return 0;
}
注意：std::priority_queue (本篇后面会讲)的选择受到更多限制。它要求底层容器支持随机访问迭代器，因此通常使用 std::vector（默认）或 std::deque，但不能使用 std::list。
4.4 总结
- 简化接口：提供了更简单、更专注的接口，使代码更清晰、更易于理解和维护。例如，使用
std::stack就明确表示这部分逻辑遵循 LIFO 规则。 - 保证数据结构特性：通过限制接口，强制用户按照特定的数据结构规则（如 FIFO, LIFO）来操作数据，避免了误操作导致的逻辑错误。
- 代码复用：复用了已有的、经过充分测试的基础容器的实现，无需从零开始编写复杂的数据结构。
简单来说，当你需要一个严格遵循 FIFO、LIFO 或优先级规则的数据结构时，使用 std::queue, std::stack 或 std::priority_queue 这些容器适配器是最佳实践，而不是直接使用 std::vector 或 std::list 并自己去维护这些规则。
5. stack&&queue的模拟实现
所以我们模拟实现就不再需要单独通过模版造轮子，可以利用适配器特性 利用vector、list等的底层来实现stack和queue
#include<iostream>
#include<vector>
#include<list>
using namespace std;
namespace fcy
{
//适配器/配接器
//容器适配器
template<class T,class Container =vector<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
size_t size() const
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& top() const
{
return _con.back();
}
T& top()
{
return _con.back();
}
private:
Container _con;
};
}
#include<iostream>
#include<vector>
#include<list>
using namespace std;
namespace fcy
{
//适配器/配接器
//容器适配器
template<class T,class Container =list<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_front();//vector中没有pop_front()的接口 虽然有erase 但是这么写需要移动数据 效率低下 所以建议使用list容器
}
void pop()
{
_con.pop_front();
}
size_t size() const
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
const T& back() const
{
return _con.back();
}
const T& front() const
{
return _con.front();
}
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
private:
Container _con;
};
}
但实际上我们模版的缺省模版是deque。
6.deque(双端队列 仅了解)
但实际底层实际中 queue和stack的模版缺省值是deque 那么deque是什么呢？？
6.1 deque的原理介绍
deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端 进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高｡
关于deque的结构是由start指向第一个内存块开头的迭代器，和finish指向最后一个内存块结尾的迭代器构成的：
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个 动态的二维数组,“连续” 空间含义：deque的 “连续” 是逻辑层面的假象，实际底层由 “多个分段连续的小内存块” 组成，通过一个 “中控数组（map）” 存储这些内存块的指针，形成整体连续的访问体验。这种设计既避免了vector“单一连续空间扩容时需拷贝全部元素” 的缺陷，又比list“每个元素独立节点 + 指针” 的结构更节省内存，兼顾了空间连续性和扩容灵活性。其底层结构如下图所示:
双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问 的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:
这里缓冲区（buffer）是deque底层实际存储元素的分段连续内存块
中控器中的迭代器封装了4个指针：
first、last指向当前buffer的开头和结尾（T*）。cur指向buffer中具体访问的元素,通过cur++不断访问别的元素(T*)。node指向中控位置(T**)。那
deque是如何借助其迭代器维护其假想连续的结构呢?
当前buffer走完以后 我们通过node+1更新node本身（因为map的空间也是连续的）同时也可以找到下一个buffer的开始 用来更新first和cur同时因为每个buffer的长度是相同的 通过first+长度又能成功更新last。
对于前删前插，后删后插操作，这里我简单讲一下前插，后面的其实就可以类比了。
前插中最难理解的就是 队首缓冲区已满 的情况 当start.cur == start.first时，说明当前队首的缓冲区已经没有空闲空间了，必须创建一个新的缓冲区来容纳新元素。
deque会从内存中分配一个新的、大小合适的缓冲区。
- 关于
map：
- 如果
map数组的前端还有空闲空间（即start.node不是map的第一个元素，ps：map是从中间开始存入数据的），就直接将新缓冲区的地址存入start.node的前一个位置。- 如果
map数组的前端没有空间了，deque会重新分配一个更大的map数组，将旧的map内容拷贝过去，并在新map的前端留出空间，然后将新缓冲区的地址存入。- 关于更新队首迭代器：
start.node指针向前移动一个位置，指向map中新插入的那个缓冲区地址。start.first指针被设置为新缓冲区的起始地址。start.last指针被设置为新缓冲区的末尾地址。start.cur指针被设置为start.last - 1（即新缓冲区的最后一个位置），因为我们要在新缓冲区的末尾（也就是整个deque的新队首）插入元素。综上
deque的前后插删都很方便！
但是,
deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实 际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看 到的一个应用就是,STL用其作为stack和queue的底层数据结构｡
6.2 deque的缺陷
deque底层由 多个 “分段连续的小内存块” 组成，通过 “中控数组（map）” 存储这些块的指针。为了让用户感知到 “连续空间”，deque的迭代器需要做特殊处理：
迭代器内部需记录当前所在的内存块指针和块内的位置；
当迭代器从一个块的末尾移动到下一个块时，需要检测边界，并切换到中控数组中的下一个块指针，再定位到新块的起始位置。
这个 “跨块检测与切换” 的过程会带来额外的开销，导致遍历（如 for 循环、范围for）时效率低于vector（完全连续内存，迭代器直接 ++ 即可）和list（双向链表，迭代器只需操作指针）。
- 内存块指针：指向当前元素所在的 “分段连续内存块” 的起始地址
- 块内偏移量（块内位置）：当前元素在该内存块中的相对位置（可以是索引，也可以是字节偏移，最终通过 “内存块起始地址 + 偏移” 计算实际地址）
这个说人话就是 假设说内存按照每100byte 分成一个内存板块 里面存储了好几个deque的数据 而块内偏移量 就是存储其在该块内的具体位置 当移动到一个块的末尾 会检测边界 产生额外开销 然后在map中切换下一个新块 从而周而复始 而遍历会导致频繁的进行“跨块检测和块的切换” 额外开销特别大。
6.3 为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性 结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据 结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list｡但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:
stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进 行操作｡- 在
stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的 元素增长时,deque不仅效率高,而且内存使用率高（不需要像list一样频繁扩容，缓存污染低）｡
6.4 总结
其实说人话 简单总结一下：
- 就是数组类（vector）就是下标随机访问快、尾插、尾删效率高，cpu高速缓存命中率高（存储物理连续）； 但缺点也很明显 头部或者中间插入删除效率低，插入空间不够要扩容，扩容有一定性能消耗，存在一定空间浪费。（数据访问方便，插入不便）
- 这里的链表（list） 就是任意位置 O（1）的插入删除，按需申请释放内存； 但是缺点也明显，不支持下标随机访问，cpu高速缓存命中率低，还存在缓存污染（因为存储不连续 容易加载无用数据）。（易插入，访问不便）
- 这里的
deque就是由多个分段连续的小内存块组成- 与
vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素；但是100w量级以上随机访问量效率略低于vector。 - 与
list比较,其底层是多个小段的连续空间,空间利用率比较高,不需要存储额外字段和频繁像list一样申请空间；同时因为deque不是像list那样完全不连续，所以cpu高速缓存命中率也不低，同时避免内存污染（因为每一小块存储的都是有用数据）；同时由于map的存在，我们可以通过/ %运算快速定位数据位置（但实际底层实现是利用总元素-前面的块数*块的大小，因为%运算效率太低），随机访问效率高；但是相比于list中间位置删除插入效率低，需要大量挪动数据。 - 但由于
deque不适合遍历deque的迭代器要频繁的去检测其
是否移动到某段小空间的边界，导致效率低下 而实际场景中，我们需要经常遍历 所以实际场景我们并不常用，同时相比于list和vector优点都不够极致，但是对于queue和stack这种不需要遍历的“容器”，同时只需要前后插入删除，deque就是栈和队列默认适配容器的最优解。
- 与
具体的使用可以参考deque文档.
求三！！！
更多推荐
31
0- 0
已为社区贡献4条内容
所有评论(0)