在C ++中验证堆栈序列

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有两个带有不同值的推入和弹出序列，则当且仅当这可能是在最初为空的堆栈上进行推入和弹出操作序列的结果时，我们才必须找到true。因此，如果输入为push = [1,2,3,4,5]，而pop为[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()的方法。这将需要推送和弹出数组

  • 定义一个堆栈st，设置index：= 0

  • 对于范围在0到推入数组大小的i

    • 索引：=索引+ 1

    • 从堆栈弹出

    • 当st不为空且popped [index] = st的顶部时

    • 从st删除

    • 索引：=索引+ 1

    • 将推[i]推入st

    • 如果popped [index] =堆栈顶部元素，则

    • 而索引<弹出的大小

      • 指数增加1

      • 从堆栈中删除

      • 如果popped [index] =堆栈顶部，则

      • 否则从循环中出来

    • 当堆栈为空时返回true

    • 该解决方法将在下面的主要部分中调用-

    • 返回solve（按下，弹出）

    让我们看下面的实现以更好地理解-

    示例

    #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

    以上是 在C ++中验证堆栈序列 的全部内容， 来源链接： utcz.com/z/351570.html

    回到顶部