使用栈实现队列的经典算法问题 | 栈与队列的转换

使用栈来实现队列是一个经典的算法问题。栈（Stack）是一种后进先出（LIFO）的数据结构，而队列（Queue）是一种先进先出（FIFO）的数据结构。由于它们的特性不同，我们需要通过两个栈来模拟队列的行为。

实现思路

我们可以使用两个栈来实现一个队列：

1. 入队操作：将所有元素压入第一个栈（stack1）。
2. 出队操作：
   • 如果第二个栈（stack2）为空，则将第一个栈（stack1）中的所有元素依次弹出并压入第二个栈（stack2），这样第二个栈的栈顶元素就是队列的队首元素。
   • 如果第二个栈不为空，则直接从第二个栈弹出栈顶元素。

代码实现

以下是使用 JavaScript 实现的代码：

class QueueUsingStacks {
  constructor() {
    this.stack1 = []; // 用于入队
    this.stack2 = []; // 用于出队
  }

  // 入队操作
  enqueue(element) {
    this.stack1.push(element);
  }

  // 出队操作
  dequeue() {
    if (this.stack2.length === 0) {
      // 如果 stack2 为空，将 stack1 中的所有元素转移到 stack2
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    // 如果 stack2 仍然为空，说明队列为空
    if (this.stack2.length === 0) {
      throw new Error("Queue is empty");
    }
    // 返回 stack2 的栈顶元素
    return this.stack2.pop();
  }

  // 查看队首元素
  peek() {
    if (this.stack2.length === 0) {
      // 如果 stack2 为空，将 stack1 中的所有元素转移到 stack2
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    // 如果 stack2 仍然为空，说明队列为空
    if (this.stack2.length === 0) {
      throw new Error("Queue is empty");
    }
    // 返回 stack2 的栈顶元素
    return this.stack2[this.stack2.length - 1];
  }

  // 判断队列是否为空
  isEmpty() {
    return this.stack1.length === 0 && this.stack2.length === 0;
  }
}

// 示例用法
const queue = new QueueUsingStacks();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue.dequeue()); // 输出 1
console.log(queue.peek());    // 输出 2
console.log(queue.isEmpty()); // 输出 false

复杂度分析

• 入队操作：时间复杂度为 O(1)，因为只需要将元素压入 stack1。
• 出队操作：
  • 最坏情况下，时间复杂度为 O(n)，因为需要将 stack1 中的所有元素转移到 stack2。
  • 平均情况下，时间复杂度为 O(1)，因为大多数情况下 stack2 不为空，可以直接弹出栈顶元素。

总结

通过使用两个栈，我们可以有效地模拟队列的行为。虽然出队操作在某些情况下需要 O(n) 的时间复杂度，但整体上这种实现方式在大多数情况下是高效的。这种设计在需要队列功能但只能使用栈的场景中非常有用。