C++：stl_stackqueue模拟实现

---

前言

今天我们一起来学习stl中stack和queue的用法，以及进行模拟实现<(￣︶￣)↗[GO!]

---

一、Stack与Queue介绍

---

1.1 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;

---

1.2 Queue介绍与用法

queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);//这样子循环遍历队列
while (!q.empty())
{cout << q.front() << " ";q.pop();
}
cout << endl;

---

二、小试牛刀

2.1逆波兰表达式求值

解析：

逆波兰表达式求值

这段代码实现了一个逆波兰表达式（后缀表达式）的求值器。核心思想是利用栈来保存操作数，遇到运算符时从栈中弹出两个操作数进行运算，并将结果重新压入栈。循环遍历输入的 token 列表，判断每个 token 是操作数还是运算符，最终栈顶的元素即为表达式的结果。

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> s;for (size_t i = 0; i < tokens.size(); i++){if (tokens[i] == "+" ||tokens[i] == "-" ||tokens[i] == "*" ||tokens[i] == "/" ){int right = s.top();s.pop();int left = s.top();s.pop();switch(tokens[i][0]){case '+':s.push(left + right);break;case '-':s.push(left - right);break;case '*':s.push(left * right);break;case '/':s.push(left / right);break;}}else{s.push(atoi(tokens[i].c_str()));}}return s.top();}
};

---

小知识——中缀表达式转后缀表达式

中缀表达式转后缀表达式的目的是为了简化运算顺序和优先级处理。中缀表达式是我们常用的形式，操作符位于操作数之间（如 A + B），而后缀表达式（逆波兰表达式）则将操作符放在操作数之后（如 A B +）。

转换过程（利用栈）：

1. 操作数：直接输出。
2. 左括号：压入栈。
3. 右括号：弹出栈顶符号，直到遇到左括号，左括号丢弃。
4. 运算符：弹出栈中所有优先级大于或等于当前运算符的符号，并输出，再将当前运算符压入栈。
5. 剩余符号：遍历结束后，将栈中剩余的符号全部弹出。

通过这种转换，省去了括号的优先级问题，便于表达式的计算。

---

2.2 用栈实现队列

用栈实现队列

具体的思路看这里~~~戳我戳我戳我ο(=•ω＜=)ρ⌒☆

class MyQueue {
public:MyQueue() {}void push(int x) {stackIn.push(x);}int pop() {if (stackOut.empty()){while (!stackIn.empty()){stackOut.push(stackIn.top());stackIn.pop();}}int top = stackOut.top();stackOut.pop();return top;}int peek() {if (stackOut.empty()){while (!stackIn.empty()){stackOut.push(stackIn.top());stackIn.pop();}}return stackOut.top();}bool empty() {return stackIn.empty() && stackOut.empty();}private:stack<int> stackIn;stack<int> stackOut;
};

---

2.3 栈的压入、弹出序列

栈的压入、弹出序列

思路：

1. 条件检查：首先检查 pushV 和 popV 的大小是否相等。如果两个序列的长度不同，那么肯定无法通过栈操作实现，所以直接返回 false。

2. 栈模拟过程：

   • 使用一个栈 s 来模拟入栈和出栈的行为。
   • 遍历 popV，依次检查每个元素是否与当前栈顶元素相等。
   • 如果栈为空或者栈顶元素不等于当前出栈元素，则继续从 pushV 中压入元素，直到栈顶元素与出栈序列中的元素匹配。
   • 一旦匹配，弹出栈顶元素，继续匹配下一个出栈元素。

3. 终止条件：如果遍历完 popV，并且所有元素都能按照顺序正确出栈，则返回 true，否则返回 false。

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code here//入栈和出栈的元素个数必须相同if(pushV.size() != popV.size())return false;// 用s来模拟入栈与出栈的过程stack<int> s;int index = 0;int index2 = 0;while (index2 < popV.size()){// 如果s是空，或者栈顶元素与出栈的元素不相等，就入栈while (s.empty() || s.top() != popV[index2]){if (index < pushV.size()) s.push(pushV[index++]);else return false;}// 栈顶元素与出栈的元素相等，出栈s.pop();index2++;}return true;}
};

---

2.4 最小栈

最小栈

带有 获取最小值 功能的栈 MinStack，其中每次执行 push、pop 操作后，能够在常数时间内获取栈中的最小值。它使用了两个栈：一个存储所有元素，另一个存储当前的最小值。

思路：

1. 普通栈 _elme：用于存储正常的栈元素，栈的基本操作（push、pop、top）都作用在这个栈上。
2. 辅助栈 _min：用于存储当前栈中的最小值。每当一个新的元素被压入主栈 _elme 时，如果这个元素小于或等于当前的最小值，就将该元素也压入 _min。当主栈弹出一个元素时，如果这个元素等于最小栈栈顶的元素，也需要将其从 _min 中弹出。
3. 保持同步：在每次压栈或出栈操作时，主栈和最小值栈保持同步，这样可以在常数时间内获取最小值。

class MinStack {
public:MinStack() {}void push(int val) {_elme.push(val);if (_min.empty() || val <= _min.top())_min.push(val);}void pop() {int top = _elme.top();_elme.pop();if (top == _min.top())_min.pop();}int top() {return _elme.top();}int getMin() {return _min.top();}private:// 保存栈中的元素stack<int> _elme;// 保存栈的最小值stack<int> _min;
};

---

2.5 两个队列实现栈

两个队列实现栈

为了实现栈的后入先出（LIFO）特性，我们使用两个队列来模拟栈的操作。queue1 用于存储栈内的元素，而 queue2 则作为入栈操作的辅助队列。

在执行入栈操作时，首先将元素放入 queue2，接着将 queue1 中的所有元素逐个出队并加入到 queue2 中。这时，queue2 的前端元素即为新入栈的元素。完成后，我们交换 queue1 和 queue2，使得 queue1 中的元素始终是栈内的元素，且其前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保 queue1 的前端元素为栈顶，因此出栈和获取栈顶元素的操作可以简单实现：出栈操作只需移除并返回 queue1 的前端元素，而获取栈顶元素操作只需返回 queue1 的前端元素而不移除。

判断栈是否为空时，只需检查 queue1 是否为空。

class MyStack {
public:MyStack() {}void push(int x) {queue2.push(x);while(!queue1.empty()){queue2.push(queue1.front());queue1.pop();}std::swap(queue1, queue2);}int pop() {int tmp = queue1.front();queue1.pop();return tmp;}int top() {return queue1.front();}bool empty() {return queue1.empty();}private:queue<int> queue1;   // 用于存储栈元素queue<int> queue2;  // 辅助队列
};

---

三、容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设
计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为
容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认
使用deque，比如：

---

四、deque

4.1 deque介绍

我们先开看deque的接口：

可以发现，deque既有list的头插头删，也支持vector的随机访问，这样看起来他是不是像一个六边形战士？

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端
进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与
list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个
动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问
的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩
容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其
是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实
际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看
到的一个应用就是，STL用其作为stack和queue的底层数据结构。

因此deque我们做了解即可。

---

4.2 deque效率对比

核心步骤：

• 第一种方法（dq1）：先把 deque 中的元素拷贝到 vector，对 vector 进行排序，排序完成后再将结果拷贝回 deque。
• 第二种方法（dq2）：直接对 deque 本身进行排序。

结果分析：

1. deque 拷贝到 vector 排序再拷贝回去：

   • 先执行拷贝操作，增加了数据传输的开销。
   • vector 的排序性能通常优于 deque，因为 vector 内存布局是连续的，排序操作的局部性较好，缓存命中率高。

2. 直接对 deque 排序：

   • deque 的内存是分段的，排序时需要更多的时间来处理不连续的内存块，导致缓存性能较差。

void test_op()
{srand(time(0));const int N = 1000000;vector<int> v1;vector<int> v2;v1.reserve(N);v2.reserve(N);deque<int> dq1;deque<int> dq2;for (int i = 0; i < N; ++i){auto e = rand();//v1.push_back(e);//v2.push_back(e);dq1.push_back(e);dq2.push_back(e);}// 拷贝到vector排序，排完以后再拷贝回来int begin1 = clock();// 先拷贝到vectorfor (auto e : dq1){v1.push_back(e);}// 排序sort(v1.begin(), v1.end());// 拷贝回去size_t i = 0;for (auto& e : dq1){e = v1[i++];}int end1 = clock();int begin2 = clock();//sort(v2.begin(), v2.end());sort(dq2.begin(), dq2.end());int end2 = clock();printf("deque copy vector sort:%d\n", end1 - begin1);printf("deque sort:%d\n", end2 - begin2);
}

结果：

可以看到，vector排序还牵扯到了两次拷贝数据时间上都大优于deque的排序，可见，deque对于[ ]访问的效率并不高。

---

五、stack模拟实现

1. 模板参数：stack 类模板接受两个参数：元素类型 T 和容器类型 Container，默认使用 deque<T> 作为底层容器。这样可以灵活选择使用不同的容器（如 deque、vector 或 list）来存储栈元素。

2. 基本栈操作：

   • push(const T& x)：将元素压入栈顶，使用容器的 push_back。
   • top()：返回栈顶元素，利用容器的 back 方法。
   • pop()：弹出栈顶元素，调用容器的 pop_back。
   • size()：返回栈中元素的个数，调用容器的 size。
   • empty()：判断栈是否为空，调用容器的 empty。

3. 容器灵活性：通过模板参数，栈可以基于不同容器实现，提供了更大的灵活性，比如可以替换为 vector<T> 或 list<T> 作为底层实现。

#pragma once
#include<list>
#include<vector>namespace jyf
{template<class T, class Container = deque<T>>class stack{public://push,top,, pop ,size,emptyvoid push(const T& x){_con.push_back(x);}T& top(){return _con.back();}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};

---

六、queue模拟实现

1. 模板参数：queue 类模板接受两个参数：元素类型 T 和容器类型 Container，默认使用 deque<T> 作为底层容器。这样可以灵活选择不同的容器（如 deque、vector 或 list）来实现队列功能。

2. 基本队列操作：

   • push(const T& x)：将元素添加到队尾，调用容器的 push_back。
   • front()：返回队头元素，利用容器的 front。
   • back()：返回队尾元素，利用容器的 back。
   • pop()：移除队头元素，调用容器的 pop_front。
   • size()：返回队列中元素的个数，调用容器的 size。
   • empty()：判断队列是否为空，调用容器的 empty。

3. 容器灵活性：通过模板参数，队列的底层容器可以灵活选择，支持不同类型的容器（如 deque、vector、list）来实现队列操作。

#pragma once
#include<list>
#include<vector>namespace jyf
{template<class T, class Container = deque<T>>class queue{public://push,top,, pop ,size,emptyvoid push(const T& x){_con.push_back(x);}T& front(){return _con.front();}T& back(){return _con.back();}void pop(){_con.pop_front();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};

---

总结

到这里就结束啦，还剩一个优先队列我们下次在进行讲解，谢谢大家😘😘😘😘💕💕💕