棧的壓入、彈出

02-26

棧的壓入、彈出

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是不是棧的彈出順序。

思路：需要藉助輔助棧，

1.將第一個序列壓入棧中，

2.判斷棧頂元素是否和第二個序列是否相等，

如果相等，那麼將棧中元素彈出，繼續2

不想等，繼續1

3.判斷棧是否為空。空，true;不空，false。

參考代碼：

#include <iostream>#include <stack>#include <vector>using namespace std;bool ispoporder(vector<int> pushV,vector<int> popV){ if(pushV.size() == 0 || popV.size() == 0) return false; vector<int> stack; for(int i = 0,j = 0;i < pushV.size();) { stack.push_back(pushV[i++]); while(j < popV.size() && stack.back() == popV[j]) { stack.pop_back(); j++; } } return stack.empty();}int main(){ vector<int> pushV = {1,2,3,4,5}; vector<int> popV = {4,5,3,2,1}; bool res = false; res = ispoporder(pushV,popV); cout << res << endl; return 0;}