C++：stl_stackqueue模拟实现
文章目录
- 前言
- 一、Stack与Queue介绍
- 1.1 Stack介绍与用法
- 1.2 Queue介绍与用法
- 二、小试牛刀
- 2.1逆波兰表达式求值
- 解析：
- 小知识——中缀表达式转后缀表达式
- 2.2 用栈实现队列
- 2.3 栈的压入、弹出序列
- 2.4 最小栈
- 2.5 两个队列实现栈
- 三、容器适配器
- 四、deque
- 4.1 deque介绍
- 4.2 deque效率对比
- 五、stack模拟实现
- 六、queue模拟实现
- 总结
前言
今天我们一起来学习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 +）。
转换过程（利用栈）：
- 操作数：直接输出。
- 左括号：压入栈。
- 右括号：弹出栈顶符号，直到遇到左括号，左括号丢弃。
- 运算符：弹出栈中所有优先级大于或等于当前运算符的符号，并输出，再将当前运算符压入栈。
- 剩余符号：遍历结束后，将栈中剩余的符号全部弹出。
通过这种转换，省去了括号的优先级问题，便于表达式的计算。
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 栈的压入、弹出序列
栈的压入、弹出序列
思路：
-
条件检查：首先检查
pushV和popV的大小是否相等。如果两个序列的长度不同，那么肯定无法通过栈操作实现，所以直接返回false。 -
栈模拟过程：
- 使用一个栈
s来模拟入栈和出栈的行为。 - 遍历
popV，依次检查每个元素是否与当前栈顶元素相等。 - 如果栈为空或者栈顶元素不等于当前出栈元素，则继续从
pushV中压入元素，直到栈顶元素与出栈序列中的元素匹配。 - 一旦匹配，弹出栈顶元素，继续匹配下一个出栈元素。
- 使用一个栈
-
终止条件：如果遍历完
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 操作后，能够在常数时间内获取栈中的最小值。它使用了两个栈：一个存储所有元素，另一个存储当前的最小值。
思路：
- 普通栈
_elme：用于存储正常的栈元素，栈的基本操作（push、pop、top）都作用在这个栈上。 - 辅助栈
_min：用于存储当前栈中的最小值。每当一个新的元素被压入主栈_elme时，如果这个元素小于或等于当前的最小值，就将该元素也压入_min。当主栈弹出一个元素时，如果这个元素等于最小栈栈顶的元素，也需要将其从_min中弹出。 - 保持同步：在每次压栈或出栈操作时，主栈和最小值栈保持同步，这样可以在常数时间内获取最小值。
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本身进行排序。
结果分析：
-
deque拷贝到vector排序再拷贝回去：- 先执行拷贝操作，增加了数据传输的开销。
vector的排序性能通常优于deque，因为vector内存布局是连续的，排序操作的局部性较好，缓存命中率高。
-
直接对
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();
// 先拷贝到vector
for (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模拟实现
-
模板参数：
stack类模板接受两个参数：元素类型T和容器类型Container，默认使用deque<T>作为底层容器。这样可以灵活选择使用不同的容器（如deque、vector或list）来存储栈元素。 -
基本栈操作：
push(const T& x)：将元素压入栈顶，使用容器的push_back。top()：返回栈顶元素，利用容器的back方法。pop()：弹出栈顶元素，调用容器的pop_back。size()：返回栈中元素的个数，调用容器的size。empty()：判断栈是否为空，调用容器的empty。
-
容器灵活性：通过模板参数，栈可以基于不同容器实现，提供了更大的灵活性，比如可以替换为
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,empty
void 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模拟实现
-
模板参数：
queue类模板接受两个参数：元素类型T和容器类型Container，默认使用deque<T>作为底层容器。这样可以灵活选择不同的容器（如deque、vector或list）来实现队列功能。 -
基本队列操作：
push(const T& x)：将元素添加到队尾，调用容器的push_back。front()：返回队头元素，利用容器的front。back()：返回队尾元素，利用容器的back。pop()：移除队头元素，调用容器的pop_front。size()：返回队列中元素的个数，调用容器的size。empty()：判断队列是否为空，调用容器的empty。
-
容器灵活性：通过模板参数，队列的底层容器可以灵活选择，支持不同类型的容器（如
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,empty
void 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;
};
总结
到这里就结束啦，还剩一个优先队列我们下次在进行讲解，谢谢大家😘😘😘😘💕💕💕
