這篇文章主要介紹了C++火車入軌算法的實現代碼，有需要的朋友可以參考一下
【問題描述】 某城市有一個火車站，鐵軌鋪設如圖所示。有n節車廂從A方向駛入車站，按進站順序編號為1~n。你的任務是讓它們按照某種特定的順序進入B方向的鐵軌並駛出車站。為了重組車廂，你可以借助中轉站C。這是一個可以停放任意多節車廂的車站，但由於末端封頂，駛入C的車廂必須按照相反的順序駛出。對於每個車廂，一旦從A移入C，就不能再回到A了；一旦從C移入B，就不能回到C了。換句話說，在任意時刻，只有兩種選擇：A→C和C→B。 這個問題和之前數據結構實驗的火車入軌類似，而且較之簡化。自己嘗試寫了下，和書上參考答案的代碼量仍有較大差距。代碼如下： 代碼如下: #include<iostream> using namespace std; const int MAXSIZE=100; void main() { int n; cin>>n; int a[MAXSIZE],b[MAXSIZE]; int stack[MAXSIZE]; for(int i=0;i<n;i++) { a[i]=i+1; cin>>b[i]; //出棧順序 } int top=-1; int count=0; int i=0; for(;;) { if(i<n) { ++top; stack[top]=a[i++]; //入棧 cout<<"PUSH"<<endl; } if(stack[top]==b[count]) { top--;count++; cout<<"POP"<<endl; } else if(i==n) { cout<<"NO"<<endl; break; } if(count==n) { cout<<"YES"<<endl; break; } if(top<-1) { cout<<"NO"<<endl; break; } } } 書中參考代碼如下： 代碼如下: #include<iostream> using namespace std; const int MAXN=1000+10; int n,target[MAXN]; void main() { while(cin>>n) { int stack[MAXN],top=0; int A=1,B=1; //A用來記錄入棧次數，B用來記錄出軌的火車序號 for(int i=1;i<=n;i++) cin>>target[i]; //記錄出軌順序 int ok=1; while(B<=n) { if(A==target[B]){A++;B++;} else if(top && stack[top]==target[B]){top--;B++;} //出棧 else if((A<=n)) stack[++top]=A++; //入棧 else {ok=0;break;} } if(ok) cout<<"Yes"<<endl; else cout<<"No"<<endl; } 同樣，可以用STL來實現，只需對書中參考答案作微小改動，代碼如下： 代碼如下: /*STL棧來實現*/ #include<iostream> #include<stack> using namespace std; const int MAXN=1000+10; int n,target[MAXN]; int main() { while(cin>>n) { stack<int> s; int A=1,B=1; for(int i=1;i<=n;i++) cin>>target[i]; int ok=1; while(B<=n) { if(A==target[B]){A++;B++;} else if(!s.empty() && s.top()==target[B]){s.pop();B++;} else if(A<=n) s.push(A++); else {ok=0;break;} } if(ok) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } 【總結】 自己寫的代碼仍有優化的空間。學習參考答案的清晰邏輯的表達。學習STL棧的使用。 聯系數據結構實驗中關於火車入軌的提升，對緩沖軌的限制，應該增加一個判斷即可。 不知坑有多深的C++初學者 目前停留在“水題”階段 走一步看一步，摸著石頭過河 向大牛看齊
