某城市有一個火車站，鐵軌鋪設如下圖所示。有n節車廂從A方向駛入車站，按進站順序編號為1~n。你的任務是讓它們按照某種特定的順序進入B方向的鐵軌並使出車站。為了重組車廂，你可以借助中轉站C；這是一個可以停放任意多節車廂的車站，但由於末端封頂，駛入C的車廂必須按照相反的順序駛出C。對於每個車廂，一旦從A進入C，就不能再回到A了；一旦從C進入B，就不能回到C了。換言之，在任意時刻，只有兩種選擇：A->C和C->B。 1 #include <stdio.h>
2 #define MAXN 1000 + 10
3 int n, target[MAXN];
4
5 int main(void)
6 {
7 while(scanf("%d", &n) == 1)
8 {
9 int stack[MAXN], top = 0;
10 int A = 1, B = 1;
11 for(int i = 1; i <= n; i++)
12 scanf("%d", &target[i]);
13 int ok = 1;
14 while(B <= n)
15 {
16 if(A == target[B]) { A++; B++; } //車廂按順序進出中轉站C，則跳出循環
17 else if(top && stack[top] == target[B]) { top--; B++; }//若車廂按逆序進中轉站C，則跳出循環
18 else if(A <= n) stack[++top] = A++; //調整車廂為逆序出中轉站C
19 else { ok = 0; break; } //車廂既不是按順序，也不是按逆序進出中轉站C
20 }
21 printf("%s\n", ok ? "Yes" : "No");
22 }
23 return 0;
24 }
View Code
分析：
1.棧：在中轉站C中，車廂符合後進先出的原則，稱為棧，即LIFO表；其中LIFO代表Last In First Out。由於棧只有一端生長，實現時只需要一個數組stack和棧頂指針（始終指向棧頂元素）。
2.對於第二種輸入情況：
B <= n A <= n stack[++top] = A++;
1 <= 5 1 <= 5 stack[1] = 1; top = 1; A = 2;
2 <= 5 stack[2] = 2; top = 2; A = 3;
3 <= 5 stack[3] = 3; top = 3; A = 4;
4 <= 5 stack[4] = 4; top = 4; A = 5;
5 <= 5 stack[5] = 5; top = 5; A = 6;
top&&stack[top]==target[B] top--; B++;
5 && 5==5 top = 4 ; B = 2;
4 && 4==4 top = 3 ; B = 3;
3 && 3==1 跳出while循環
3.為了方便，數組下標均從1開始。例如：target[1]是指目標序列中第一個車廂的編號，stack[1]是指棧底元素（棧空當且僅當top=0）。
C++提供了一種更加簡單的處理方式—STL隊列：
