stack的介绍和使用

非成员函数

例题

最小栈

解析

用另一个栈minst去存储st的最小值，当st每插入一个数是新的最小值(相同也是)就同时插入minst，释放这个最小值时minst同时释放

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

解析：

1.先把入栈序列入列

2.栈顶元素和出栈序列是否匹配

a.如果匹配，持续出数据，直到不匹配或者栈为空

b.如果不匹配，继续入数据

结束标志

入栈序列走完了，再来判断

1.栈为空或出栈序列到尾则返回true

2.栈不为空或出栈序列没有到尾返回false

逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹于1929年首先提出的一种表达式的表示方法。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。

逆波兰表达式计算

由内圈向外圈

用栈计算

逆波兰表达式的转换

用栈转换

1.操作数输出

2.操作符

a.栈为空吗，入栈

b.比栈顶的操作符优先级高，入栈

c.比栈顶的操作符优先级低或相等，出栈顶操作符，重复执行2操作

结束后，将栈中操作符全部出栈输出

遇见括号则走递归，解决括号中表达式

stack的模拟实现

#include<iostream> using namespace std; #include<vector> #include<list> namespace bit { // 设计模式 // 适配器模式 -- 转换 //适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计 //经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。 // stack<int, vector<int>> st1; // stack<int, list<int>> st2; 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() { return _con.size(); } bool empty() {