Xác thực chuỗi cửa sổ đẩy trong JavaScript

Vấn đề

Hàm JavaScript nhận vào hai mảng, được đẩy và bật lên, làm đối số thứ nhất và thứ hai. Cả hai mảng này đều được đảm bảo chứa các phần tử duy nhất.

Hàm của chúng ta sẽ trả về true 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, ngược lại là false.

Ví dụ:nếu đầu vào của hàm là -

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

Sau đó, đầu ra phải là -

const output = true;

Giải thích đầu ra

Chúng ta có thể thực hiện theo trình tự sau -

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

Ví dụ

Mã cho điều này sẽ là -

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

Và đầu ra trong bảng điều khiển sẽ là -

true