栈 —— 数据结构基础刷题路程

一、P1739 表达式括号匹配 - 洛谷

算法代码：

#include<bits/stdc++.h>
using namespace std;
const int N=300008;
struct mystack
{int a[N];int t=-1;//压栈void push(int data){a[++t]=data;	} //取栈顶元素int top(){return a[t];	} //弹出栈顶元素void pop(){if(t>-1){t--;	}	} //取栈的大小int size(){return t+1;	} //判空int empty(){return t=-1?1:0;	} 
};
int main()
{mystack st;char x;while(cin>>x){if(x=='@'){break;}if(x=='('){st.push(x);}if(x==')'){if(st.empty()){cout<<"NO";}else{st.pop();}}}if(st.empty()){cout<<"YES";}else{cout<<"NO";}return 0;	
} 

---

二、P1734 - [NewOJ Contest 4] 排列 - New Online Judge

算法代码： 

#include<bits/stdc++.h>
using namespace std;
const int N=300008;
int a[N]; 
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}stack<int> st;long long ans=0;for(int i=1;i<=n;i++){while(!st.empty()&&st.top()<a[i]){st.pop();if(!st.empty()){int last=st.top();ans+=(i-last+1);}}st.push(a[i]);}ans+=(n-1)*2;cout<<ans;return 0;	
} 

---

三、1.妮妮的神秘宝箱 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;int main() {string s;cin >> s;stack<char> st;for (char c : s) {if (c == '(' || c == '[' || c == '{') {st.push(c);} else if (c == ')' || c == ']' || c == '}') {if (st.empty()) {cout << "N";  // 统一输出为 "N"return 0;}char _top = st.top();if ((c == ')' && _top == '(') || (c == ']' && _top == '[') || (c == '}' && _top == '{')) {st.pop();}else{cout << "N";return 0;} }// 忽略其他字符（如 '.'）}cout << (st.empty() ? "Y" : "N");return 0;
}

---

四、1.小蓝的括号串1 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{stack<char> st;int n;cin>>n;char ch;while(cin>>ch){if(ch=='('){st.push(ch);}if(ch==')'){if(st.empty()){cout<<"No";return 0;}char _top=st.top();if(_top=='('&&ch==')'){st.pop();}}}if(st.empty()){cout<<"Yes";}else{cout<<"No";}return 0;
}

---

五、1.小邋遢的衣橱 - 蓝桥云课

算法代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,i;string t1,t2,t3;stack<string> a;cin>>n;for(i=0;i<n;i++){cin>>t1>>t2;if(t1=="in")a.push(t2);if(t1=="out"){if(a.empty())return 0;for(t3=a.top();t3!=t2;a.pop()){if(a.empty())return 0;t3=a.top();}}}if(a.empty())cout<<"Empty";elsecout<<a.top();return 0;
}