Xác thực trình tự push pop trong JavaScript

Mô tả vấn đề

Hàm JavaScript nhận vào hai mảng pushed và popped (các phần tử duy nhất). Trả về true nếu và chỉ nếu đây có thể là kết quả của trình tự push/pop trên stack ban đầu rỗng.

Ví dụ, nếu đầu vào là:

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

Thì đầu ra nên là:

const output = true;

Giải thích đầu ra

Trình tự có thể: push(1), push(2), push(3), push(4), pop()→4, push(5), pop()→5, pop()→3, pop()→2, pop()→1.

Ví dụ minh họa

Mã thực hiện (mô phỏng stack):

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

Đầu ra

Kết quả trong console:

true