Xác thực chuỗi ngăn xếp trong C ++

Giả sử chúng ta có hai chuỗi được đẩy và bật lên với các giá trị khác nhau, chúng ta phải tìm đúng nếu và chỉ khi điều này có thể là kết quả của một chuỗi các hoạt động đẩy và bật trên một ngăn xếp trống ban đầu. Vì vậy, nếu đầu vào là push =[1,2,3,4,5] và pop =[4,5,3,2,1], thì đầu ra sẽ là true. Chúng ta có thể sử dụng push (1), push (2), push (3), push (4), pop ():4, push (5), pop ():5, pop ():3, pop ():2, pop ():1

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một phương thức gọi là giải quyết (). Điều này sẽ lấy các mảng được đẩy và bật lên

• xác định một ngăn xếp, đặt chỉ mục:=0

• cho tôi trong phạm vi 0 đến kích thước của mảng được đẩy

  • push đã đẩy [i] vào st

  • nếu popped [index] =phần tử trên cùng của ngăn xếp, thì

    • index:=index + 1

    • bật ra từ ngăn xếp

    • trong khi st không trống và popped [index] =top of st

      • index:=index + 1

    • xóa khỏi st

• trong khi chỉ mục

  • nếu popped [index] =stack top, thì

    • tăng chỉ số lên 1

    • xóa khỏi ngăn xếp

  • nếu không thì ra khỏi vòng lặp

• trả về true, khi ngăn xếp trống

• phương pháp giải này sẽ được gọi từ phần chính như bên dưới -

• trả về giải quyết (được đẩy, bật lên)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[1,2,3,4,5]
[4,5,3,2,1]

Đầu ra

1