首页 > 学院 > 开发设计 > 正文

铁轨-栈(stack)

2019-11-08 01:05:02
字体:
来源:转载
供稿:网友
有n节车厢从A方向驶入车站,按进站顺序编号1~n。出栈顺序是(5,4,1,2,3)是不可能的,但是(5,4,3,2,1)可以。现让这些火车按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢,可以借助中转站C。C是一个可以停放任意多节车厢的车站,但由于末端封顶,驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢,一旦从A移入C,就不能再回到A了;一旦从C移入B,就不能回到C了。换句话说,在任意时刻,只有两种选择:A→C和C→B。

请编程判断判断:按给定的出站顺序,火车能否出站。 

#include<stack>头文件,STL中的很有用的容器适配器之一,默认基于Deque容器实现,可以在定义时覆盖其默认容器类型,但一般并不需要。包含以下几个成员函数:empty() 堆栈为空则返回真pop() 移除栈顶元素(不会返回栈顶元素的值)push() 在栈顶增加元素size() 返回栈中元素数目top() 返回栈顶元素

5

1 2 3 4 5

Yes

5

5 4 1 2 3

No

#include<cstdio>#include<stack>using namespace std;const int MAXN=100+10;int n,target[MAXN];int main(){    while(scanf("%d",&n)==1)    {        stack<int> s;        int A=1,B=1;        for(int i=1;i<=n;i++)            scanf("%d",&target[i]);        int ok=1;        while(B<=n)        {            if(A==target[B])            {            A++;            B++;            }            else if(!s.empty()&&s.top()==target[B])   {s.pop();B++;}            else if(A<=n)   s.push(A++);            else {ok=0;break;}        }        PRintf("%s/n",ok?"Yes":"No");    }    return 0;}


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表