ตรวจสอบลำดับกองซ้อนใน C ++

สมมติว่าเรามีลำดับการผลักและแตกสองครั้งด้วยค่าที่แตกต่างกัน เราต้องหาว่าจริงหรือไม่ก็ต่อเมื่อสิ่งนี้เป็นผลมาจากลำดับของการดำเนินการพุชและป๊อปในสแต็กว่างในตอนแรก ดังนั้นหากอินพุตเป็น push =[1,2,3,4,5] และ pop =[4,5,3,2,1] ผลลัพธ์จะเป็นจริง เราสามารถใช้ push(1), push(2), push(3), push(4), pop() :4, push(5), pop() :5, pop() :3, pop() :2, ป๊อป() :1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างเมธอดหนึ่งวิธีที่เรียกว่า Solve() การดำเนินการนี้จะใช้อาร์เรย์พุชและป๊อปอัป

• กำหนด stack st, set index :=0

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของอาร์เรย์พุช

  • ผลัก[i] เข้าสู่ st

  • ถ้า popped[index] =stack top element แล้ว

    • ดัชนี :=ดัชนี + 1

    • ป๊อปจากสแต็ก

    • ในขณะที่ st ไม่ว่างเปล่า และปรากฏขึ้น[index] =ด้านบนของ st

      • ดัชนี :=ดัชนี + 1

    • ลบออกจาก st

• ในขณะที่ดัชนี <ขนาดของแตก

  • ถ้าเด้ง[index] =stack top แล้ว

    • เพิ่มดัชนีขึ้น 1

    • ลบออกจากสแต็ก

  • มิฉะนั้นออกมาจากลูป

• คืนค่า จริง เมื่อสแต็กว่างเปล่า

• วิธีการแก้ปัญหานี้จะถูกเรียกจากส่วนหลักดังนี้ -

• กลับมาแก้(ดัน,โผล่)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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