[UVA] 514 - Rails

題意:
火車有n節車廂，
每個車廂都有依序的編號1...n，
現在這些車廂要從A到B，這個火車可以重組，
重組的方法如下:
車廂是一個一個到車站，
來到車站後可以往B方向去，也可以先暫放在車站。
輸入往另一個方向的車廂編號，
問是否可以藉由重組，
往另一個方向去。
範例輸入:
5           //5節車廂
1 2 3 4 5
5 4 1 2 3
0           //結束
問是否可以以1 2 3 4 5的順序往B方向，
一開始從A方向也是1 2 3 4 5
所以1先進車站，直接往B去，
接著2進車站，直接往B去，
接著3進車站，直接往B去，
接著4進車站，直接往B去，
接著5進車站，直接往B去，
就可以以1 2 3 4 5的順序往B方向去，
所以輸出Yes
而5 4 1 2 3，
1先進車站，先暫放，
2進車站，先暫放，
3進車站，先暫放，
4進車站，先暫放，
5進車站，往B方向去，
接著4往B方向去，
再來車站只能把3往B送，不能送1 2(因為3還沒出)，
不可能以5 4 1 2 3的順序重組輸出，
所以輸出No

方法:
車站是一個stack
直接模擬操作，使用一個queue儲存輸入，
依序將1 2 ...n送入stack，
若stack.top==queue.front，那就pop
若stack最後不為空就是No，反之就是Yes



/* 20150814
 * hanting
 * UVa 514 - Rails
 * C++
 */
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
bool CanRestructure(queue<int> &que)
{
    vector<int> from(que.size());
    for(int i=0;i<from.size();i++)
    {//給予from初始值1 2 ...n
        from[i]=i+1;
    }
    stack<int> stk;
    for(int i=0;i<from.size();i++)
    {
        stk.push(from[i]);//車廂一個個進車站
        while(stk.size() and que.front()==stk.top())
        {//若與B的頭一樣就輸出，也就是pop車站的車廂
            stk.pop();
            que.pop();
        }
    }
    if(stk.size()) return false;
    else return true;
}
int main()
{
    int N;
    while(cin>>N and N)
    {
        while(true)
        {
            queue<int> que;
            int num;
            cin>>num;
            if(!num) break;//0跳出
            que.push(num);
            for(int i=1;i<N;i++)
            {
                cin>>num;
                que.push(num);
            }
            if(CanRestructure(que))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
        cout<<endl;
    }
    return 0;
}