本文章是学习过程中记录的笔记，主要来源Erik_Tse
stack
stack是栈，一种后进先出（Last In First Out）的容器，它仅维护栈顶（top），支持入栈（push），查询栈顶（top），出栈（pop），查询大小（size）操作。
常用于"单调栈"，"括号匹配"，"dfs"，"Tarjan求强连通分量"，"波兰表达式（计算器）"等算法或数据结构中。
初始化
stack<int> stk;//创建一个空栈，栈不允许列表初始化或填充相同元素
//但是可以从已有的栈进行拷贝构造
stack<int> stk2(stk);
stack<int> stk3 = stk2;
入栈
stk.push(10);//stk = [10(top)]
stk.push(20);//stk = [10,20(top)]
stk.push(50);//stk = [10,20,50(top)]
cout << stk.top() << '\n';//50, stk = [10,20,50(top)]
stk.pop();//stk = [10,20(top)]
cout << stk.top() << '\n';//20, stk = [10,20(top)]
取出栈顶元素
//c++中top()只会取出栈顶元素，不会将栈顶元素pop()掉
cout << stk.top() << '\n';
出栈
//弹出栈顶元素，注意判断非空！
if(stk.size()) {
cout << stk.top() << '\n';
stk.pop();
}
获取栈大小（元素个数），判空
cout << stk.size() << '\n';
if(stk.empty()) ...//栈空
清空栈
while(stk.size()) stk.pop();//O(n)
手写栈
//stack中不允许遍历，但是我们可以用手写栈或者用vector，就可以实现遍历啦
//手写栈，只需要用top表示栈顶下标，以下标1作为栈底即可
int stk[N],top=0;
//入栈
stk[++ top] =x;
//出栈
top --;
//取出栈顶元素
cout << stk[top] << '\n';
//获取大小
cout << top << '\n';
//判断是否为空
if(top) ...//非空
//遍历栈
for(int i=1;i<=top;i++)
//甚至还可以在单调栈上进行二分
练习题(火车)
火车轨道 | 星码StarryCoding 算法竞赛新手村
答案代码
#include<bits/stdc++.h> using namespace std; int main(){ int n;cin>>n; stack<int> stk; int need=1; for(int i=1;i<=n;i++){ int x;cin>>x; stk.push(x); while(stk.size()&&need<=n&&stk.top()==need){ need++; stk.pop(); } } if(need==n+1) cout << "Yes" << '\n'; else cout << "No" << '\n'; return 0; }注意一点——在 while 循环的条件判断部分，需要先判空，再去取栈顶元素，否则如果为空，但是已经取出栈顶元素了，这是非法操作，不会再进行后续操作（程序崩溃了）
练习题（括号匹配）
括号匹配 | 星码StarryCoding 算法竞赛新手村
答案代码
#include<bits/stdc++.h> using namespace std; const int N = 2e5+9; char s[N]; void solves(){ cin>>s+1; int n=strlen(s+1); stack<char> stk; bool ans=true; for(int i=1;i<=n;i++){ if(s[i]=='('||s[i]=='['||s[i]=='{'){ stk.push(s[i]); }else{ if(stk.empty()){ ans=false; break; }else{ if((stk.top()=='('&&s[i]==')')|| (stk.top()=='['&&s[i]==']')|| (stk.top()=='{'&&s[i]=='}')){ stk.pop(); }else{ ans=false; break; } } } } if(stk.size()) ans=false; cout<<(ans?"YES":"NO")<<'\n'; } int main(){ int _;cin>>_; while(_--){ solves(); } return 0; }
