std::stack和std::queue
目录
stack
stack模拟实现
构造函数
push和pop
返回栈顶元素
栈中元素个数及判空
queue
queue模拟实现
构造函数
push和pop
返回头尾元素
返回队列元素个数及判空
补充deque
补充练习
栈的压入和弹出
最小栈问题
逆波兰表达式求值
stack
stack是C++中的一个容器栈，stack要满足LIFO context (last-in first-out)，先进后出的原则，先进入的元素后出来，后进入的元素先出来。就好像一个碗，先装进去的饭最后才能吃到，而后装进去的能先吃到。
因为stack要满足先进后出的原则，所以stack没有头插尾插，头删尾删，其只有插入和删除。
stack - C++ Reference
https://legacy.cplusplus.com/reference/stack/stack/?kw=stackstack实际上并不是容器，而是一个容器适配器，就是stack能直接用其他容器来实现栈的效果，而不需要本身创建一个容器。
stack是容器适配器，那stack使用哪一个容器呢？？？实际上使用哪一个容器是不固定的，可以使用vector也可以使用list，看用户自己的需求，但没有指定容器的话，默认用deque容器，关于deque容器结尾会进行讲解。能使用不同的容器就意味着需要对stack增加一个模板参数来实现。
stack模拟实现
关于stack的模拟实现是比较简单的，因为stack是容器适配器所以再模拟实现各个功能的时候可直接调用容器中的成员函数来实现。
构造函数
关于构造函数，此处仅实现无参构造。因为stack的成员自定义类型回去调用自定义类型的默认构造，所以此处不需要实现默认构造。
//模拟实现stack
template<class T ,class Container=deque<T>> //container是容器的模板，默认是deque
class stack
{
public:
_con()
{
}
private:
Container _con;
};
push和pop
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}返回栈顶元素
//非const版本
T& top()
{
return _con[_con.size()-1];
}
//const版本
const T& top()const
{
return _con[_con.size() - 1];
}栈中元素个数及判空
//返回栈中个数
size_t size()
{
return _con.size();
}
//判断栈是否为空
bool empty()
{
return _con.empty();
}queue
queue和stack相同，只是规则不一样，queue队列是FIFO context (first-in first-out)，要满足先进先出的原则。
queue模拟实现
构造函数
template<class T, class Container = deque<T>>
class queue
{
public:
queue()
{
}
private:
Container _con;
};push和pop
//插入
void push(const T& val)
{
_con.push_back(val);
}
//删除
void pop()
{
_con.pop_front();
}返回头尾元素
//非const类
//返回头部元素
T& front()
{
return _con[0];
}
//返回尾部元素
T& back()
{
return _con[_con.size() - 1];
}
//const类
const T& front()const
{
return _con[0];
}
//返回尾部元素
const T& back()const
{
return _con[_con.size() - 1];
}返回队列元素个数及判空
//返回元素个数
size_t size()
{
return _con.size();
}
//判空
bool empty()
{
return _con.empty();
}补充deque
deque是stack和queue容器适配器的默认容器。deque即有push_back，push_front和pop_back和pop_front，又能对下标解引用，deque相当于list和vector的结合体。
deque的实现是有一个中控指针数组来实现的，这个中控数组存放一个个的指针指向存储数据的数组中去。
指针数组在使用的时候，先使用中间的空间，当头插的时候向前使用空间，当尾插的时候向后使用空间，来实现头插和尾插及删除。
每一个buffer的元素个数是相同的，所以同个计算可以找到指定的下标。
但是因为deque既想要list的下标解引用又要有list的头插尾插的效率导致最后相比原来两者的效率大大降低了。
1）与vector相比deque有头插和头删的高效，但是deque的下标解引用没有vector的纯粹和高效，deque要计算访问的元素在哪一个buffer，在这个buffer的哪一个位置，而vector连续空间直接访问；
2）与list相比，deque有list无法实现的下标解引用[ ]，也有list的头插和尾插，但是deque的中间位置插入删除效率取极低，因为不能改变buffer长度导致，对中间元素进行处理的时候需要大量移动数据，使得效率降低。
因为则两个原因一般不会直接使用deque作为我们代码编写是的使用容器。而是选择vector或list的一个长处作为容器使用。
补充练习
栈的压入和弹出
栈的压入、弹出序列_牛客题霸_牛客网https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
给定一个序列B判断序列B是否可以由序列A栈弹出。
此题的关键在于模仿栈的压入和弹出情况，通过模拟栈的压入和弹出来判断是否满足情况。
解法：用栈来实现，先让指针指向目标B，再让A依次入栈，如果A的栈顶元素和指针指向B的元素相同A出栈，B指针向后走，如果不同就继续入栈，直到序列中的最后一个元素入栈后出栈，如果最终的栈是空则满足题意。
//栈的压入和弹出
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
stack<int> ans;
int pushi = 0; //用pushi和popi来记录两个顺序表指向的位置
int popi = 0;
while (pushi < pushV.size())
{
//让第一个元素入栈
ans.push(pushV[pushi]);
++pushi;
//判断是否出栈之前要保证栈不为空
while (!ans.empty() && ans.top() == popV[popi])
{
ans.pop();
++popi;
}
}
return ans.empty(); //如果栈为空则满足题意
}最小栈问题
155. 最小栈 - 力扣（LeetCode）https://leetcode.cn/problems/min-stack/submissions/606067751/
设置一个类MinStack要求其能返回堆栈中最小的元素。注意：此题要求在参数时间类返回最小元素，即getMin()的时间复杂度是O(1)。
此题要求在参数时间内返回最小的元素，则用一个栈是行不通的。
思考：能否用一个变量来保存栈中的最小元素？？？
实际上是不行的，因为当最小元素被pop后，再调用getMin()函数的时候怎么办？？所以不仅仅保留最小的元素，还需要保留倒数第二个，倒数第三个....
解法：创建一个额外的栈来专门存放“最小”元素，将第一个压入栈的元素作为最小元素，当后面一个元素比他小或等于的时候才入栈，比他打的时候就不入栈，这样就能保证这个栈顶始终存放的是最小值，当原栈中的最小值被pop时，额外栈才pop。
class MinStack {
public:
MinStack() {
} //类的成员都是自定义类型所以这里不需要写构造函数
void push(int val) {
origin.push(val);
if (min.empty()||val<=min.top()) //如果栈min是空或者val小于等于最小元素就入栈
{
min.push(val);
}
}
void pop() {
//如果要pop的元素就是最小元素就需要对min栈pop
if (!min.empty() && min.top() == origin.top())
{
min.pop();
}
origin.pop();
}
int top() {
return origin.top();
}
int getMin() {
return min.top();
}
private:
stack<int> origin; //用来储存原有栈的元素
stack<int> min; //储存最小元素
};逆波兰表达式求值
150. 逆波兰表达式求值 - 力扣（LeetCode）150. 逆波兰表达式求值 - 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 [https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437] 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意： * 有效的算符为 '+'、'-'、'*' 和 '/' 。 * 每个操作数（运算对象）都可以是一个整数或者另一个表达式。 * 两个整数之间的除法总是 向零截断 。 * 表达式中不含除零运算。 * 输入是一个根据逆波兰表示法表示的算术表达式。 * 答案及所有中间计算结果可以用 32 位 整数表示。 示例 1：输入：tokens = ["2","1","+","3","*"]输出：9解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9示例 2：输入：tokens = ["4","13","5","/","+"]输出：6解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6示例 3：输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]输出：22解释：该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 + 3) * -11))) + 17) + 5= ((10 * (6 / (12 * -11))) + 17) + 5= ((10 * (6 / -132)) + 17) + 5= ((10 * 0) + 17) + 5= (0 + 17) + 5= 17 + 5= 22 提示： * 1 <= tokens.length <= 104 * tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数 逆波兰表达式：逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。 * 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。 * 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。逆波兰表达式主要有以下两个优点： * 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。 * 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中https://leetcode.cn/problems/evaluate-reverse-polish-notation/
通常情况下一个表达式：2+1*3；
其中缀表达式是：2 + 1 * 3
后缀表达书是： 2 1 + 3 *
中缀表达式不用说就是一个整式的正常顺序，那莫后缀表达式是什么呢？？？
后缀表达式是中缀表达式将其操作数不变，将其操作符按照优先级顺序进行重排。
后缀表达式的计算方法：按照上面显示的当遇到操作符的时候，将其前两个数字按在当前操作符进行运算，结果放回。
解法：将数字依次入栈，当遇到操作符时停止入栈，取出操作符进行运算，将运算结果再入栈。
//逆波兰表达式求值
class Solution {
public:
void sum(stack<int>& num, char c)
{
//取出栈顶两个元素求和，将结果再入栈
int a = num.top(); //右操作数
num.pop();
int b = num.top(); //左操作数
num.pop();
switch (c)
{
case '+':
num.push(b + a);
break;
case '-':
num.push(b - a);
break;
case '*':
num.push(b * a);
break;
case '/':
num.push(b / a);
break;
}
}
int evalRPN(vector<string>& tokens) {
stack<int> num;
int i = 0;
while (i < tokens.size())
{
//判断是不是操作符
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
{
sum(num, tokens[i][0]); //用tokens[i][0]来传运算符，传过去字符
++i;
}
else
{
//是数字就入栈
num.push(stoi(tokens[i])); //此处使用stoi将字符串转化为数字
++i;
}
}
//返回栈顶元素
return num.top();
}
};补充：怎么将中缀表达式转化为后缀表达式呢？？？？
在将中缀表达式转化为后缀表达式的时候我们需要考虑运算符的优先级问题。数字还是依次插入，当出现运算符的时候是否插入要看前两个数是不是先计算，eg：2+8*6：插入2 8之后是否插入+，可以看到这里是不会插入的，因为要想计算8*6，因此时2 8 6 * +。