首页 > 代码库 > POJ_1363_模拟

POJ_1363_模拟

题目描述:

  列车出入站是一种栈的机制,每组数据给予一个n,进站按1-n顺序,给定一组出站顺序,判断能否实现。

思路:

  直接用了queue,in记录当前准备入站的列车编号,out记录已经出站的辆数+1。

  若in == 第out辆的编号,则当前入站的直接出站。

  若栈顶的编号 == 第out辆的编号,则该车出站。

  若in < 第out辆的编号,则须将in和后面out编号之前的车全都进站。

  若in > 第out辆的编号,说明当需要出站的车被堵在车站里了。

 

#include<cstdio>#include<iostream>#include<stack>using namespace std;int a[1005];int main(){    stack<int> s;    int n;    while(cin >> n && n)    {        while(cin >> a[1] && a[1])        {            while(!s.empty())   s.pop();            for(int i = 2;i <= n;i++)   cin >> a[i];            int flag = 1,in = 1,out = 1;            while(out <= n)            {                if(in == a[out])                {                    in++;                    out++;                }                else if(!s.empty() && s.top() == a[out])                {                    s.pop();                    out++;                }                else if(a[out] > in)                {                    s.push(in++);                }                else                {                    flag = 0;                    break;                }            }            if(flag)    cout << "Yes" << endl;            else    cout << "No" << endl;        }        cout << endl;    }    return 0;}

 

POJ_1363_模拟