算法与数据结构实验题 3.13 station
★实验任务 一天，小L 突然对列车的进出站问题产生了兴趣，如下图所示：
列车只能从A 进站，或从B 出站。
列车从A 进站，进站顺序为 1, 2, 3, 4, 5
列车从B 出站，出站顺序为 5, 4, 3, 2, 1
现在，小L 想知道：
列车从A 进站，进站顺序为 1~n
列车从B 出站，给定出站的顺序，判断是否可能按照这个顺序出站
★数据输入
第一行一个正整数 n（1<=n<=1000）。
第二行包含n 个正整数，为 1~n 的某个排列
★数据输出
若能够按照给定的顺序出站，输出”YES”（没有引号）
否则，输出”NO”（没有引号）
输入示例1
5
5 4 3 2 1
输出示例1
YES
输入示例2
3
3 1 2
输出示例2
NO
#include <iostream>
#include <stack>
using namespace std;
int main() {
int n, tmp;
cin>>n;
int cur=1; //从1开始进栈
stack<int>sk;
bool ans=true;
for(int i=0;i<n;i++){
cin>>tmp;
if(!ans)continue; //前面已不满足答案，完成输入即可
if(cur==tmp) //进栈并出栈
cur++;
else if(!sk.empty()&&sk.top()==tmp) //出栈栈顶
sk.pop();
else if(cur<=n){
bool fd=false; //是否找到
while(cur<=n){ //一直入栈并查找
sk.push(cur);
cur++;
if(cur==tmp){ //找到
fd=true;
cur++; //进栈并出栈
break;
}
}
if(!fd) //遍历结束仍未找到
ans=false;
}
else ans=false;
}
if(ans)cout<<"YES";
else cout<<"NO";
return 0;
}
就是考察堆栈这个数据结构，即先进后出。
给定入栈顺序1~n，判断出栈顺序是否合法。
遍历出栈顺序，当前出栈元素tmp，判断可否由未进栈元素cur，或栈顶元素sk.top()直接得到。
如若不能直接得到，则循环进栈，直到找到该元素，或者找不到置答案false。