两个队列模拟栈

class StackWithQueues {
  constructor() {
    this.queue1 = []; // 主队列（始终存储数据）
    this.queue2 = []; // 辅助队列（用于操作时临时存储）
  }

  // 入栈操作：直接加入主队列
  push(x) {
    this.queue1.push(x);
  }

  // 出栈操作：将主队列元素转移到辅助队列，留最后一个弹出
  pop() {
    if (this.empty()) return undefined;
    while (this.queue1.length > 1) {
      this.queue2.push(this.queue1.shift());
    }
    const popped = this.queue1.shift();
    // 交换队列引用，保证下次操作时 queue1 仍是主队列
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
    return popped;
  }

  // 查看栈顶元素：类似出栈，但将元素放回主队列
  top() {
    if (this.empty()) return undefined;
    while (this.queue1.length > 1) {
      this.queue2.push(this.queue1.shift());
    }
    const topElement = this.queue1[0];
    this.queue2.push(this.queue1.shift());
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
    return topElement;
  }

  // 判断栈是否为空
  empty() {
    return this.queue1.length === 0;
  }
}

使用示例

const stack = new StackWithQueues();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.top());   // 输出 3
console.log(stack.pop());   // 输出 3
console.log(stack.pop());   // 输出 2
console.log(stack.empty()); // 输出 false
console.log(stack.pop());   // 输出 1
console.log(stack.empty()); // 输出 true

核心逻辑说明

1. 入栈 ( push )
   直接将要插入的元素加入主队列 queue1 ，时间复杂度 O(1)。

2. 出栈 ( pop )

   • 将主队列 queue1 的前 n-1 个元素转移到辅助队列 queue2 。
   • 弹出并返回主队列最后一个元素（即栈顶元素）。
   • 交换 queue1 和 queue2 的引用，保证下次操作时 queue1 仍是主队列，时间复杂度 O(n)。

3. 查看栈顶 ( top )

   • 类似出栈操作，但将最后一个元素也转移到辅助队列后再交换队列引用，时间复杂度 O(n)。

4. 判空 ( empty )
   直接检查主队列 queue1 是否为空，时间复杂度 O(1)。

实现特点

• 主辅队列动态切换：通过交换队列引用，确保操作后主队列始终有效。
• 严格遵循 LIFO：每次出栈和查看栈顶都保证操作的是最后加入的元素。
• 时间复杂度权衡：入栈操作高效（O (1)），出栈和查看栈顶牺牲效率（O (n)）以满足队列特性限制。