极客教程JavaScript 如何使用两个堆栈实现enqueue和dequeue
在本文中，我们将使用两个堆栈（以纯数组的形式）在JavaScript中实现队列的操作（enqueue和dequeue）。在直接进入理解问题陈述之前，让我们简要了解一下堆栈的概念以及队列的概念。
堆栈是一种线性数据结构，它以后进先出（LIFO）的概念工作，最后到达的元素将首先被删除或者出栈。类似地，队列也是一种线性数据结构，它以先进先出（FIFO）的概念工作，首先到达的元素将首先被删除或者出队。一些生活中的示例可以更好地理解堆栈的概念，比如将盘子依次放在一起，直到最后一个盘子放在顶部等等。同样，站在电影票收集队伍中，第一个人会先收集电影票，直到这个人离开队伍，下一个人才能收集电影票，这就是队列的一个示例。
现在，您已经简要了解了堆栈和队列，让我们清楚地理解问题陈述，然后我们将看到解决问题陈述的解决方案。以下图示将清晰地描述问题陈述，即使用两个堆栈实现队列操作（enqueue和dequeue）-
上面的图示表示了对多个元素（如 a、b、c 等）执行入队操作，这些元素被插入到堆栈中（以普通数组的形式声明）。
上述的图示表示了使用多个元素和两个栈执行的出队操作，首先我们会从第一个栈中弹出（删除）最后一个元素，然后将该被删除的元素添加到另一个栈中，然后从另一个栈中进一步移除或弹出元素。基本上，删除并添加到另一个栈是为了使其与队列的功能相反，即将其逻辑反转，而不是像栈一样工作。
现在您已经非常清楚地理解了问题陈述，让我们继续看一下解决上述问题陈述的方法。
方法1：
- 在此方法中，我们将首先初始化两个栈（以两个普通数组的形式）。
- 然后我们将执行入队操作，将几个由用户提供的元素添加到第一个栈中。
- 在执行入队操作后，我们将为上述插入的元素定义出队操作。
- 对于出队操作，我们首先必须弹出或删除第一个栈中的最后一个元素。
- 然后，在从第一个栈中删除或弹出最后一个元素后，我们将该弹出的元素添加到另一个栈中（也是以数组的形式）。
- 然后，在将元素添加到新数组后，我们将从下一个栈中弹出或删除该元素，通过这种方式我们可以执行出队操作。
示例：
JavaScript
<script>
// Two stacks declared in the form of plain array
let stack1 = [];
let stack2 = [];
// Method that will perform our enqueue operation
function enqueue(element) {
stack1.push(element);
console.log("Stack-1 elements are enqueue: ", stack1);
}
// Method that will perform our dequeue operation
function dequeue() {
if (stack2.length === 0) {
if (stack1.length === 0) {
console.log(
"Dequeue not possible because queue is empty..");
}
while (stack1.length > 0) {
let x = stack1.pop();
stack2.push(x);
}
}
console.log("Element after Dequeue: " + stack2.pop());
}
enqueue("a");
enqueue("b");
enqueue("c");
dequeue();
dequeue();
</script>
输出：
Stack-1 elements are enqueue: [ 'a' ]
Stack-1 elements are enqueue: [ 'a', 'b' ]
Stack-1 elements are enqueue: [ 'a', 'b', 'c' ]
Element after Dequeue: a
Element after Dequeue: b
第二种方法：
- 这种方法对于多个入队和出队操作可以动态工作。
- 在这里，我们将处理多种情况，比如在入队之前调用了出队，或者多次调用了出队，或者在出队之后刚刚调用了入队或者只是在出队之后刚刚调用了一个单独的操作。
- 与第一种方法类似，我们也将为入队和出队操作分别创建两个独立的函数或方法。
- 在这两个独立的方法中，我们将分别执行入队和出队的个别逻辑。
示例：
JavaScript
<script>
// Two stacks declared in array form
let stack1 = [];
let stack2 = [];
// Method to implement enqueue operation
function enqueue(element) {
// if dequeue was called before actual
// enqueue operation
if (stack2.length > 0) {
let len = stack2.length;
for (let i = 0; i < len; i++) {
let p = stack2.pop();
stack1.push(p);
}
}
stack1.push(element);
console.log("Elements after Enqueue: ", stack1);
}
// Method to implement dequeue operation......
function dequeue() {
// If dequeue was called consecutively, all
// the elements would be in stack2
if (stack2.length > 0) {
console.log("Element after dequeue : "
+ stack2.pop());
}
// If enqueue was called right before
// this dequeue, stack2 is empty
else if (stack2.length === 0) {
if (stack1.length === 0) {
// If the first operation is
// dequeue itself
console.log("Queue is empty");
} else if (stack1.length === 1) {
// If a single operation as
// enqueue was performed
console.log(stack1.pop());
}
// If enqueue was called before this
// operation, all the elements are in
// stack1, so pop them and push the
// elements into stack2, then pop()
else if (stack1.length > 0) {
let len = stack1.length;
for (let i = 0; i < len; i++) {
let p = stack1.pop();
stack2.push(p);
}
console.log("Element after dequeue: "
+ stack2.pop());
}
}
}
enqueue("a");
enqueue("b");
enqueue("c");
dequeue();
enqueue("d");
enqueue("e");
dequeue();
dequeue();
dequeue();
enqueue("f");
</script>
输出：
Elements after Enqueue: [ 'a' ]
Elements after Enqueue: [ 'a', 'b' ]
Elements after Enqueue: [ 'a', 'b', 'c' ]
Element after dequeue: a
Elements after Enqueue: [ 'b', 'c', 'd' ]
Elements after Enqueue: [ 'b', 'c', 'd', 'e' ]
Element after dequeue: b
Element after dequeue : c
Element after dequeue : d