ตรวจสอบลำดับ Push Pop ใน JavaScript

ปัญหา

ฟังก์ชัน JavaScript ที่รับอาร์เรย์สองอัน pushed และ popped เป็นอาร์กิวเมนต์แรกและสอง ทั้งสองอาร์เรย์รับประกันว่ามีสมาชิกไม่ซ้ำกัน

ฟังก์ชันควรคืนค่า true ก็ต่อเมื่อลำดับนี้อาจเป็นผลลัพธ์ของลำดับการ push และ pop บน stack ว่างเริ่มต้น มิฉะนั้น 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