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 次浏览

开启你的 职业 生涯

完成课程获得认证

开始
广告