Train Problem I

時間限制：3000?ms ?|? 內存限制：65535?KB 難度：2 描述

As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2.
輸入

The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.

輸出

The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.", and then output your way in exchanging the order(you should output "in" for a train getting into the railway, and "out" for a train getting out of the railway). Print a line contains "FINISH" after each test case. More details in the Sample Output.

樣例輸入

3 123 321 3 123 312

樣例輸出

Yes. in in in out out out FINISH No. FINISH

題意：給出兩個字符串，問第一個字符串能否經過棧轉化為第二個字符串。?如果可以，輸出進棧和出棧的順序。

? ? ? 這是一個關于棧的問題。棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進先出表。

#include<stdio.h> #include<string.h> #include<stack> /*定義棧*/ using namespace std; /*千萬不要忘記*/ int main() {int n,i,j,k,flag[20];char s1[10],s2[10];stack<char> s;while(~scanf("%d%s %s",&n,s1,s2)){memset(flag,-1,sizeof(flag));j=k=0;for(i=0;i<n;i++){s.push(s1[i]);flag[k++]=1; /*1為進棧，in*/while(!s.empty()&&s.top()==s2[j]) /*棧非空且棧頂元素與s2中的元素相等*/{flag[k++]=0; /*0為出棧，out*/s.pop(); /*清除棧頂元素*/j++; /*與s2中的下一個元素比較*/}}if(j==n) /*可以轉換*/{printf("Yes.\n");for(i=0;i<k;i++){if(flag[i]) /*flag[i]==1*/printf("in\n");elseprintf("out\n");}printf("FINISH\n");}else /*不能轉換*/printf("No.\nFINISH\n");}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 150 Train Problem I STL栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。