是否可以用Stack实现多个Queue？具体实现方法及逻辑说明

可行性结论 #

完全可以用栈实现队列，如需实现多个相互独立的队列，仅需为每个队列单独分配两个专属栈实例即可，不同队列的操作完全互不干扰。

单队列实现逻辑（基于你提供的示例代码） #

你给出的代码就是标准的「双栈实现单队列」方案，完整代码如下：

// 用数组实现栈，自带push、pop方法
var Stack1 = [];
var Stack2 = [];

// 仅用栈的push、pop能力实现入队方法
function Enqueue(element) {
  Stack1.push(element);
}

// 出队方法：将栈1的所有元素倒入栈2反转顺序，再从栈2弹出
function Dequeue() {
  if (Stack2.length === 0) {
    if (Stack1.length === 0) { return 'Cannot dequeue because queue is empty'; }
    while (Stack1.length > 0) {
      var p = Stack1.pop();
      Stack2.push(p);
    }
  }
  return Stack2.pop();
}

// 测试代码
Enqueue('a');
Enqueue('b');
Enqueue('c');
Dequeue();

双栈的分工 #

• 入队栈（Stack1）：专门承接所有入队请求，新元素直接压入栈顶，入队操作时间复杂度为O(1)
• 出队栈（Stack2）：专门处理出队请求，利用栈「后进先出」的特性倒转入队栈的元素，最终实现队列「先进先出」的特性

核心操作逻辑 #

入队操作

不管出队栈当前有没有元素，直接调用Stack1.push(element)压入新元素即可，不需要额外操作，效率极高。

出队操作

1. 先检查出队栈（Stack2）是否有元素：如果有，直接弹出栈顶元素，就是当前队列的队首元素
2. 如果出队栈为空，先检查入队栈（Stack1）是否也为空：如果两个栈都空，说明队列没有元素，返回空队提示
3. 如果入队栈有元素，就把入队栈的元素逐个弹出、逐个压入出队栈，完成后出队栈的元素顺序和入队顺序完全相反，原本最先入队的元素会跑到出队栈的栈顶，直接弹出即可完成出队。

示例代码执行过程 #

你给出的测试代码执行顺序如下：

1. 依次入队a、b、c后，Stack1内容为['a','b','c']，Stack2为空
2. 调用Dequeue时，Stack2为空，开始倒转Stack1的元素：依次弹出c、b、a压入Stack2，此时Stack2内容为['c','b','a']
3. 弹出Stack2栈顶元素a，正好是最先入队的元素，符合队列先进先出的特性。

多队列实现方案 #

你给出的示例是全局单队列的实现，要扩展为多个独立队列，只需要把双栈和操作逻辑封装为类，每个队列实例独享自己的两个栈即可，示例实现如下：

class QueueByStack {
  constructor() {
    // 每个队列实例专属两个栈，和其他队列完全隔离
    this.inStack = [];
    this.outStack = [];
  }
  // 入队
  enqueue(element) {
    this.inStack.push(element);
  }
  // 出队
  dequeue() {
    if (this.outStack.length === 0) {
      if (this.inStack.length === 0) return 'Cannot dequeue because queue is empty';
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }
}

// 生成多个独立队列，操作互不干扰
const queue1 = new QueueByStack();
const queue2 = new QueueByStack();

queue1.enqueue('a');
queue2.enqueue('x');
console.log(queue1.dequeue()); // 输出a
console.log(queue2.dequeue()); // 输出x

内容的提问来源于stack exchange，提问作者Sarnavo Saha Sardar