題目鏈接：http://poj.org/problem?id=1363

題目大意：
A站有編號(hào)為1到N，N最大1000，的車(chē)廂，車(chē)廂進(jìn)入中轉(zhuǎn)station了就不能回到A，只能停在station內(nèi)或者進(jìn)入B站，問(wèn)能不能按照給定的順序排成那樣的車(chē)廂號(hào)。

解題：
每次一個(gè)新車(chē)廂進(jìn)入station前，檢查棧內(nèi)棧頂元素是否與B站沒(méi)有匹配的車(chē)廂頭是否相等（如果有，則彈棧，重復(fù)此步驟），沒(méi)有匹配的直接入棧。最后棧為空則可以排成給定次序。

舉個(gè)例子：（2,1,3,5,4）能不能排成這樣











AC代碼如下：

#include <stack> #include <iostream> #define N 1001 using namespace std; int main() {int Barr[N], i = 0, j = 0, len;while(cin >> len && len) //輸入火車(chē)長(zhǎng)度{while (1){stack<int> station;for(i = 0; i < len; ++i) //輸入火車(chē)B站的車(chē)廂順序{cin >> Barr[i]; if(Barr[0] == 0) //第一個(gè)車(chē)廂是0，結(jié)束break;}if(Barr[0] == 0) //第一個(gè)車(chē)廂是0，結(jié)束{break;}for(i = 1, j = 0; i <= len; ++i) //對(duì)1-N的車(chē)廂進(jìn)行操作{while(!station.empty() && station.top() == Barr[j]) //中轉(zhuǎn)站（棧）不為空則，比較棧頂與B的車(chē)廂的號(hào)碼{station.pop(); //相等的話，車(chē)廂出棧j++; //可以比較下一個(gè)車(chē)廂號(hào)碼了}station.push(i); //棧為空或者棧頂車(chē)廂號(hào)與要求的不等，則直接把A站的車(chē)壓入棧內(nèi)}while(!station.empty() && station.top() == Barr[j]) //當(dāng)1-N都?jí)簵Ｍ炅?#xff0c;棧內(nèi)還有車(chē)廂的話，順次和棧頂比較{station.pop();j++;}if(station.empty()) //最后棧內(nèi)為空則，可以匹配要求的順序cout << "Yes" << endl;elsecout << "No" << endl;}cout << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 1363 火车厢排队问题（栈）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。