【問題描述】

　　某城市有一個(gè)火車站，鐵軌鋪設(shè)如圖所示。有n節(jié)車廂從A方向駛?cè)胲囌?#xff0c;按進(jìn)站順序編號(hào)為1~n。你的任務(wù)是讓它們按照某種特定的順序進(jìn)入B方向的鐵軌并駛出車站。為了重組車廂，你可以借助中轉(zhuǎn)站C。這是一個(gè)可以停放任意多節(jié)車廂的車站，但由于末端封頂，駛?cè)隒的車廂必須按照相反的順序駛出。對(duì)于每個(gè)車廂，一旦從A移入C，就不能再回到A了；一旦從C移入B，就不能回到C了。換句話說，在任意時(shí)刻，只有兩種選擇：A→C和C→B。

?

這個(gè)問題和之前數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的火車入軌類似，而且較之簡(jiǎn)化。自己嘗試寫了下，和書上參考答案的代碼量仍有較大差距。代碼如下：

1 #include<iostream> 2 using namespace std; 3 const int MAXSIZE=100; 4 void main() 5 { 6 int n; 7 cin>>n; 8 int a[MAXSIZE],b[MAXSIZE]; 9 int stack[MAXSIZE]; 10 for(int i=0;i<n;i++) 11 { 12 a[i]=i+1; 13 cin>>b[i]; 　　 //出棧順序 14 } 15 int top=-1; 16 int count=0; 17 int i=0; 18 for(;;) 19 { 20 if(i<n) 21 { 22 ++top; 23 stack[top]=a[i++]; //入棧 24 cout<<"PUSH"<<endl; 25 } 26 27 if(stack[top]==b[count]) 28 { 29 top--;count++; 30 cout<<"POP"<<endl; 31 } 32 else if(i==n) 33 { 34 cout<<"NO"<<endl; 35 break; 36 } 37 if(count==n) 38 { 39 cout<<"YES"<<endl; 40 break; 41 } 42 if(top<-1) 43 { 44 cout<<"NO"<<endl; 45 break; 46 } 47 } 48 49 }

?書中參考代碼如下：

1 #include<iostream> 2 using namespace std; 3 const int MAXN=1000+10; 4 int n,target[MAXN]; 5 void main() 6 { 7 while(cin>>n) 8 { 9 int stack[MAXN],top=0; 10 int A=1,B=1; 　　 //A用來記錄入棧次數(shù)，B用來記錄出軌的火車序號(hào) 11 for(int i=1;i<=n;i++) 12 cin>>target[i]; //記錄出軌順序 13 int ok=1; 14 while(B<=n) 15 { 16 if(A==target[B]){A++;B++;} 17 else if(top && stack[top]==target[B]){top--;B++;} 　　//出棧 18 else if((A<=n)) stack[++top]=A++; 　　 //入棧 19 else {ok=0;break;} 20 } 21 if(ok) 22 cout<<"Yes"<<endl; 23 else 24 cout<<"No"<<endl; 25 }

同樣，可以用STL來實(shí)現(xiàn)，只需對(duì)書中參考答案作微小改動(dòng)，代碼如下：

1 /*STL棧來實(shí)現(xiàn)*/ 2 #include<iostream> 3 #include<stack> 4 using namespace std; 5 const int MAXN=1000+10; 6 int n,target[MAXN]; 7 int main() 8 { 9 while(cin>>n) 10 { 11 stack<int> s; 12 int A=1,B=1; 13 for(int i=1;i<=n;i++) 14 cin>>target[i]; 15 int ok=1; 16 while(B<=n) 17 { 18 if(A==target[B]){A++;B++;} 19 else if(!s.empty() && s.top()==target[B]){s.pop();B++;} 20 else if(A<=n) s.push(A++); 21 else {ok=0;break;} 22 } 23 if(ok) 24 cout<<"YES"<<endl; 25 else 26 cout<<"NO"<<endl; 27 } 28 }

【總結(jié)】

　　自己寫的代碼仍有優(yōu)化的空間。學(xué)習(xí)參考答案的清晰邏輯的表達(dá)。學(xué)習(xí)STL棧的使用。

　　聯(lián)系數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)中關(guān)于火車入軌的提升，對(duì)緩沖軌的限制，應(yīng)該增加一個(gè)判斷即可。

轉(zhuǎn)載于:https://www.cnblogs.com/anthozoan77/p/3464363.html

總結(jié)

以上是生活随笔為你收集整理的火车入轨_算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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