数据结构
网络
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 浏览量
广告