JavaScript에서 푸시 팝 시퀀스 유효성 검사

문제

첫 번째 및 두 번째 인수로 두 개의 배열(푸시 및 팝)을 취하는 JavaScript 함수입니다. 이 두 배열은 모두 고유한 요소로 구성됩니다.

우리의 함수는 이것이 초기에 빈 스택에 대한 푸시 및 팝 작업의 결과일 수 있는 경우에만 true를 반환해야 하고 그렇지 않으면 false를 반환해야 합니다.

예를 들어, 함수에 대한 입력이 -

const pushed = [1, 2, 3, 4, 5];
const popped = [4, 5, 3, 2, 1];

그러면 출력은 다음과 같아야 합니다. -

const output = true;

출력 설명

우리는 다음 순서를 할 수 있습니다 -

push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

예시

이에 대한 코드는 -

const pushed = [1, 2, 3, 4, 5];
const popped = [4, 5, 3, 2, 1];
const validateSequence = (pushed = [], popped = []) => {
   let pushedIndex = 0
   let poppedIndex = 0
   const stack = []
   while (pushedIndex < pushed.length) {
      if (stack[stack.length - 1] !== popped[poppedIndex]) {
         stack.push(pushed[pushedIndex++])
      } else {
         stack.pop()
         poppedIndex += 1
      }
   }
   while (stack.length) {
      if (stack.pop() !== popped[poppedIndex++]) {
         return false
      }
   }
   return true;
};
console.log(validateSequence(pushed, popped));

출력

콘솔의 출력은 -

true