輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。 輸入： 每個測試案例包括3行： 第一行為1個整數n(1<=n<=100000)，表示序列的長度。 第二行包含n個整數，表示棧的壓入順序。 第三行包含n個整數，表示棧的彈出順序。 輸出： 對應每個測試案例，如果第二個序列是第一個序列的彈出序列輸出Yes，否則輸出No。 樣例輸入： 5 1 2 3 4 5 4 5 3 2 1 5 1 2 3 4 5 4 3 5 1 2 樣例輸出： Yes No 代碼AC： 思想：掃描 + 入棧 + 彈棧：當前的輸出==棧頂元素，彈棧，若當前輸出的不是棧頂元素，那麼就要將元素入棧直到此元素，如果入棧中沒有發現此元素，那麼就是錯誤的序列。 [cpp] #include <stdio.h> #include <stdlib.h> int main() { int n, *stack1, *stack2, *stack, i, j, top = -1, flag, f; while( scanf("%d", &n) != EOF ) { stack1 = ( int * )malloc( sizeof( int ) * n ); stack2 = ( int * )malloc( sizeof( int ) * n ); stack = ( int * )malloc( sizeof( int ) * n ); for( i = 0; i < n; i++ ) { scanf("%d", &stack1[i]); } for( i = 0; i < n; i++ ) { scanf("%d", &stack2[i]); } top = -1; i = 0; j = 0; flag = 1; while( stack1[i] != stack2[j] ) { stack[++top] = stack1[i]; if( ( ++i ) >= n ) { printf("No\n"); flag = 0; break; } } if( !flag ) { continue; } i++; j++; while( j < n ) { f = 0; if( top > -1 ) { if( stack2[j] == stack[top] ) { top--; j++; } else { f = 1; } } else { f = 1; } if( f ) { while( stack2[j] != stack1[i] ) { stack[++top] = stack1[i]; i++; if( i >= n ) { printf("No\n"); flag = 0; break; } } if( flag ) { stack[++top] = stack1[i]; } } if( !flag ) { break; } } if( !flag ) { continue; } printf("Yes\n"); } return 0; }
