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

更新於: 09-Apr-2021

322 次瀏覽

開啟你的 職業 生涯

完成課程獲得認證

開始
廣告