在 JavaScript 中验证推送弹出序列
javascriptweb developmentfront end technology
问题
JavaScript 函数接受两个数组，推送和弹出，作为第一个和第二个参数。这两个数组都保证由唯一元素组成。
我们的函数应该返回 true，当且仅当这可能是对最初为空的堆栈进行推送和弹出操作的结果时，否则返回 false。
例如，如果函数的输入是 −
const push = [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
