迪庆藏族自治州网站建设_网站建设公司_小程序网站_seo优化

本文章是学习过程中记录的笔记，主要来源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; }