用 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

Arnab Chakraborty

更新于:02-May-2020

330 浏览量

启动您的 职业

完成课程后获得认证

开始