資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時裝設計
法學用 C++ 驗證棧的順序
假設我們有兩個元素不同的序列 push 和 popped，如果這可能是最初為空的棧上的一系列 push 和 pop 操作的結果，就返回 true。因此，如果輸入 push = [1,2,3,4,5]，且 popped = [4,5,3,2,1]，則輸出將為 true。我們可以使用 push(1), push(2), push(3), push(4), pop() : 4, push(5), pop() : 5, pop() : 3, pop() : 2, pop() : 1
為解決這個問題，我們將遵循以下步驟：
建立一個名為 solve() 的方法。這將採用 pushed 和 popped 陣列
定義棧 st，將索引 := 0
對於 i 從 0 迴圈到 pushed 陣列的大小
將 pushed[i] 推入 st
如果 popped[index] = 棧頂元素，則
index := index + 1
從棧中彈出
當 st 不為空且 popped[index] = st 的頂部時
index := index + 1
從 st 中刪除
當 index < popped 的大小時
如果 popped[index] = 棧頂，則
增加索引值 1
從棧中刪除
否則從迴圈中退出
當棧為空時，返回 true
可以透過如下方式從主部分呼叫此求解方法 −
return solve(pushed, popped)
讓我們看看以下實現，以更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int>& pushed, vector<int>& popped){
stack <int> st;
int currentIndexOfPopped = 0;
for(int i =0;i<pushed.size();i++){
st.push(pushed[i]);
if(popped[currentIndexOfPopped] == st.top()){
currentIndexOfPopped++;
st.pop();
while(!st.empty() && popped[currentIndexOfPopped]==st.top()){
currentIndexOfPopped++;
st.pop();
}
}
}
while(currentIndexOfPopped <popped.size()){
if (popped[currentIndexOfPopped]==st.top()){
currentIndexOfPopped++;
st.pop();
}else{
break;
}
}
return st.empty();
}
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
Solution s;
bool flag = s.solve(pushed, popped);
return flag;
}
};
main(){
vector<int> v = {1,2,3,4,5};
vector<int> v1 = {4,5,3,2,1};
Solution ob;
cout << (ob.validateStackSequences(v, v1));
}輸入
[1,2,3,4,5] [4,5,3,2,1]
輸出
1
更新於:02-May-2020
330 瀏覽量
廣告