題目描述：

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列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

用一個棧來模擬，可以做到O(n) 1 #include <iostream> 2 #include <stack> 3 using namespace std; 4 5 int main() 6 { 7 int a[100000]; 8 int b[100000]; 9 int n; 10 stack<int> s; 11 12 while(cin >> n) 13 { 14 for(int i = 0; i < n; i++) 15 cin >> a[i]; 16 17 for(int i = 0; i < n; i++) 18 cin >> b[i]; 19 20 bool flag = true; 21 int index = 0; 22 while(!s.empty()) 23 s.pop(); 24 25 for(int i = 0; i < n; i++) 26 { 27 if (!s.empty() && s.top() == b[i]) 28 s.pop(); 29 else 30 { 31 bool findIt = false; 32 while(index < n) 33 { 34 s.push(a[index]); 35 if (a[index] == b[i]) 36 { 37 index++; 38 findIt = true; 39 break; 40 } 41 42 index++; 43 } 44 45 if (!findIt) 46 { 47 flag = false; 48 break; 49 } 50 else 51 s.pop(); 52 } 53 } 54 55 if (flag) 56 cout << "Yes" << endl; 57 else 58 cout << "No" << endl; 59 } 60 }

?

總結

以上是生活随笔為你收集整理的[九度][何海涛] 栈的压入压出的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。