ตรวจสอบลำดับการกดป๊อปใน JavaScript

ปัญหา

ฟังก์ชัน JavaScript ที่รับในสองอาร์เรย์ แบบพุชและป๊อปอัพ เป็นอาร์กิวเมนต์แรกและอาร์กิวเมนต์ที่สอง อาร์เรย์ทั้งสองนี้รับประกันว่าจะประกอบด้วยองค์ประกอบที่ไม่ซ้ำกัน

ฟังก์ชันของเราควรคืนค่าเป็น จริง หากสิ่งนี้อาจเป็นผลมาจากลำดับของการดำเนินการพุชและป๊อปในสแต็กว่างในตอนแรก มิฉะนั้น จะเป็นเท็จ

ตัวอย่างเช่น หากอินพุตของฟังก์ชันคือ −

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