C++에서 스택 시퀀스 검증

<시간/>

두 개의 시퀀스를 푸시하고 고유한 값으로 팝한다고 가정하면 이것이 초기에 비어 있는 스택에 대한 푸시 및 팝 작업 시퀀스의 결과일 수 있는 경우에만 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, 팝() :1

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

solve()라는 메서드를 하나 만듭니다. 푸시 및 팝된 배열을 사용합니다.
스택 st 정의, 인덱스 설정 :=0
범위 0에서 푸시된 배열의 크기까지의 i에 대해
- push push[i] st
- popped[인덱스] =스택 맨 위 요소인 경우
  - 인덱스 :=인덱스 + 1
  - 스택에서 팝
  - st가 비어 있지 않은 동안 popped[index] =st의 상단
    - 인덱스 :=인덱스 + 1
  - st에서 삭제
동안 인덱스 <팝업 크기
- popped[인덱스] =스택 맨 위인 경우
  - 인덱스 1 증가
  - 스택에서 삭제
- 그렇지 않으면 루프에서 나옵니다.
스택이 비어 있으면 true를 반환합니다.
이 해결 방법은 아래와 같이 메인 섹션에서 호출됩니다 -
해결 반환(푸시, 팝)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]