目录

栈的概念以及栈的实现

STL 的stack

栈和stack的算法题

栈的模板题

栈的算法题之有效的括号

验证栈序列

后缀表达式

括号匹配 

---

栈的概念以及栈的实现

栈是一种只允许在一端进行插入和删除的线性表

空栈：没有任何元素

入栈：插入元素消息

出栈：删除元素

栈本身就是一个线性表，我们可以写一个足够大的数组来实现栈

除此之外，我们还需要变量n来记录栈顶元素和栈的元素个数

我们来实现一下栈

#include <iostream>
using namespace std;
const int N = 1e6;
int st[N];
int n = 0;
void push(int x)
{st[++n] = x;
}
void pop()
{--n;
}
int top()
{return st[n];
}
int size()
{return n;
}
bool empty()
{return n == 0;
}int main()
{for (int i = 0; i < 10; i++){push(i);}while (size()){cout << top() << " ";pop();}}

上述代码就是我们栈的实现，我们栈的元素是从数组下标为1开始的，如果栈顶下标是0的话就是空栈

我们入栈是0，1，2，3，4，5，6，7，8，9

出栈的时候就是从9开始弹出

STL 的stack

除了我们的静态的栈，我们stl库里面还有一个现成的栈，叫stack，它的创建和vector实际上是差不多的

我们来测试一下stack

#include <iostream>
#include <stack>
using namespace std;
const int N = 1e6;stack <int> st;
int main()
{for(int i =0 ;i<10;i++){st.push(i);}while(!st.empty()){cout << st.top() << " ";st.pop();}}

栈和stack的算法题

栈的模板题

这道题我们有两个需要注意的点，第一个数据范围

int的数据范围是-2的31次方到2的31次方-1

unsigned int是0到 2的32次方-1

long long的范围是2的63次方-1

unsigned long long的范围是2的64次方减1

所以我们栈的数据类型应该是unsigned longlong

第二点就是，我们每组数据是隔离的，互不影响的，所以我们要处理脏数据，再每次处理完一组数据之后，要清空我们的栈

这是我们ac的代码

#include <iostream>
using namespace std;
const int N = 1e6+10;
typedef unsigned long long LL;
LL st[N];
int top;
int main()
{int t;int n;cin >> t;while(t--){top = 0;int n;cin >> n;while(n--){string op;cin >> op;if(op == "push"){LL x;cin >> x;st[++top] =x;}else if(op == "pop"){if(top == 0)cout << "Empty" << endl;elsetop--;}else if(op == "query"){if(top == 0){cout <<"Anguei!" << endl;}elsecout << st[top] << endl;}else{cout << top << endl;}}}return 0;
}

栈的算法题之有效的括号

这道题我们用stack来解决一下

如果是左括号，我们入栈，如果是右括号，我们进行匹配，匹配成功出栈，匹配如果不成功那我们就返回false，最后我们还要查看一下栈是不是空，如果不是空，还是false

class Solution {
public:bool isValid(string s) {stack <char> a;for(auto e:s){if (e == '(' || e == '[' || e=='{'){a.push(e);}if(e == ')' || e == ']' || e== '}'){if(empty(a))return false;if((e == ')' && a.top() != '(') || (e == '}' && a.top() != '{') || (e == ']' && a.top() != '[')) return false;a.pop();}}return empty(a);}
};

小tips ：我们要注意，右括号匹配的时候，如果栈空了，也是要返回false的，如果没有判空这一个条件，我们取top就会越界。

验证栈序列

思路：边入栈边出栈，用指针指向出栈序列每一个元素，如果栈顶元素刚好是指针指的元素，那就出栈，如果不是就不出，最后如果栈出到空栈，说明我们的出栈序列是正确的。

这是我们的代码

#include <iostream>
#include <stack>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
int main()
{int q;cin >> q;while(q--){int n;cin >> n;for(int i = 1;i<=n;i++) cin >> a[i];for(int i = 1;i<=n;i++) cin >> b[i];stack <int> st;int j = 1;for(int i = 1;i<=n;i++){st.push(a[i]);while(j<=n && st.size() && st.top() == b[j]){st.pop();j++;}}if(st.empty()) cout << "Yes" << endl;else cout << "No" << endl;}}

后缀表达式

这道题，我们要用栈模拟我们的这个后缀表达式（也叫逆波兰表达式），如果是操作数，我们就入栈，然后如果是运算符号，我们就弹出两个元素，第一个元素表示右操作数，第二个元素表示左操作数，然后对这两个操作数进行运算把结果再入栈

直到遇到@的时候，我们结束，输出栈里最后的元素也就是我们的结果了

#include <iostream>
#include <stack>
using namespace std;int main()
{stack <int> st;char c;int num = 0;while(cin >> c){if(c >= '0' && c<='9'){num = num*10 + c-'0';}else if(c == '.'){st.push(num);num = 0;}else if(c == '@')break;else{int b = st.top();st.pop();int a = st.top();st.pop();if(c == '/')st.push(a/b);else if(c == '*')st.push(a*b);else if(c == '+')st.push(a+b);else st.push(a-b);}}cout << st.top() << endl;
}

括号匹配 

这道题我们的思路是从左到右遍历字符串，如果是左括号就入栈，如果是右括号就看他是否和栈顶匹配，如果匹配成功的话就把这个字符和栈顶字符的位置标记成正确的，并把栈顶弹出去

，如果匹配不成功的，我们把它补全

下面是我们的代码

#include <iostream>
#include <stack>
using namespace std;
const int N = 110;
int b[N];
int main()
{stack <int> st;string s;cin >> s;for(int i = 0;i<s.size();i++){if(s[i] == '(' || s[i] == '[')st.push(i);else{if(st.empty())continue;int t = st.top();char left = s[t];if((left == '(' && s[i] == ')') || (left == '[' && s[i] == ']')){b[i] = b[t] = 1;st.pop();}}}string ret = "";char ch;for(int i = 0;i<s.size();i++){ch = s[i];if(b[i]){ret+=ch;}else if(ch == '('){ret+=ch;ret+=')';}else if(ch == ')'){ret+='(';ret+=ch; }else if(ch == '['){ret+=ch;ret+=']';}else{ret+='[';ret+=ch;}}cout << ret << endl;return 0;
}