c#中的解决方案

public class Queue<T> where T : class
{
    private Stack<T> input = new Stack<T>();
    private Stack<T> output = new Stack<T>();
    public void Enqueue(T t)
    {
        input.Push(t);
    }

    public T Dequeue()
    {
        if (output.Count == 0)
        {
            while (input.Count != 0)
            {
                output.Push(input.Pop());
            }
        }

        return output.Pop();
    }
}

队列中的两个堆栈定义为stack1和stack2。

排队: euqueued的元素总是被推入stack1

出列: stack2的顶部可以被弹出，因为它是在stack2不为空时插入队列的第一个元素。当stack2为空时，我们从stack1中弹出所有元素，并将它们逐个推入stack2。队列中的第一个元素被压入stack1的底部。由于它位于stack2的顶部，所以在弹出和推入操作后可以直接弹出。

下面是相同的c++示例代码:

template <typename T> class CQueue
{
public:
    CQueue(void);
    ~CQueue(void);

    void appendTail(const T& node); 
    T deleteHead();                 

private:
    stack<T> stack1;
    stack<T> stack2;
};

template<typename T> void CQueue<T>::appendTail(const T& element) {
    stack1.push(element);
} 

template<typename T> T CQueue<T>::deleteHead() {
    if(stack2.size()<= 0) {
        while(stack1.size()>0) {
            T& data = stack1.top();
            stack1.pop();
            stack2.push(data);
        }
    }


    if(stack2.size() == 0)
        throw new exception("queue is empty");


    T head = stack2.top();
    stack2.pop();


    return head;
}

这个解决方案是从我的博客中借来的。我的博客网页上有详细的操作模拟分析。

public class QueueUsingStacks<T>
{
    private LinkedListStack<T> stack1;
    private LinkedListStack<T> stack2;

    public QueueUsingStacks()
    {
        stack1=new LinkedListStack<T>();
        stack2 = new LinkedListStack<T>();

    }
    public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
    {
        while(source.Head!=null)
        {
            dest.Push(source.Head.Data);
            source.Head = source.Head.Next;
        }
    }
    public void Enqueue(T entry)
    {

       stack1.Push(entry);
    }
    public T Dequeue()
    {
        T obj;
        if (stack2 != null)
        {
            Copy(stack1, stack2);
             obj = stack2.Pop();
            Copy(stack2, stack1);
        }
        else
        {
            throw new Exception("Stack is empty");
        }
        return obj;
    }

    public void Display()
    {
        stack1.Display();
    }


}

对于每一个入队列操作，我们都将其添加到stack1的顶部。每次出队列时，我们都将stack1的内容清空到stack2中，并删除堆栈顶部的元素。出队列的时间复杂度是O(n)，因为我们必须将stack1复制到stack2。队列的时间复杂度与常规堆栈相同

下面是使用ES6语法的javascript语言解决方案。

Stack.js

//stack using array
class Stack {
  constructor() {
    this.data = [];
  }

  push(data) {
    this.data.push(data);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }

  size(){
    return this.data.length;
  }
}

export { Stack };

QueueUsingTwoStacks.js

import { Stack } from "./Stack";

class QueueUsingTwoStacks {
  constructor() {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }

  enqueue(data) {
    this.stack1.push(data);
  }

  dequeue() {
    //if both stacks are empty, return undefined
    if (this.stack1.size() === 0 && this.stack2.size() === 0)
      return undefined;

    //if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty
    if (this.stack2.size() === 0) {
      while (this.stack1.size() !== 0) {
        this.stack2.push(this.stack1.pop());
      }
    }

    //pop and return the element from stack 2
    return this.stack2.pop();
  }
}

export { QueueUsingTwoStacks };

用法如下:

index.js

import { StackUsingTwoQueues } from './StackUsingTwoQueues';

let que = new QueueUsingTwoStacks();
que.enqueue("A");
que.enqueue("B");
que.enqueue("C");

console.log(que.dequeue());  //output: "A"

不过，时间的复杂性会更糟。一个好的队列实现在常数时间内完成所有事情。

Edit

不知道为什么我的答案在这里被否决了。如果我们编程，我们会关心时间复杂度，使用两个标准堆栈来创建队列是低效的。这是一个非常有效和相关的观点。如果有人觉得有必要再投反对票，我很想知道为什么。

更详细一点:关于为什么使用两个堆栈比使用一个队列更糟糕:如果您使用两个堆栈，并且有人在发件箱为空时调用dequeue，则需要线性时间才能到达收件箱的底部(正如您可以在Dave的代码中看到的那样)。

您可以将队列实现为单链表(每个元素指向下一个插入的元素)，保留一个额外的指针指向最后一个插入的元素进行推操作(或使其成为循环列表)。在此数据结构上实现队列和出队列非常容易，只需常数时间即可完成。这是最坏情况的常数时间，不是平摊。而且，正如注释中要求澄清的那样，最坏情况下常数时间严格来说比平摊常数时间要好。

设要实现的队列为q，用于实现q的堆栈为stack1和stack2。

Q可以通过两种方式实现:

方法1(通过使enQueue操作成本高)

该方法确保新输入的元素始终位于堆栈1的顶部，这样deQueue操作就会从堆栈1弹出。要将元素放在stack1的顶部，可以使用stack2。

enQueue(q, x)
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.

方法2(通过提高deQueue操作的成本)

在此方法中，在队列操作中，新元素在stack1的顶部输入。在去队列操作中，如果stack2为空，则所有元素都被移动到stack2，最后返回stack2的顶部。

enQueue(q,  x)
 1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
 1) If both stacks are empty then error.
 2) If stack2 is empty
   While stack1 is not empty, push everything from stack1 to stack2.
 3) Pop the element from stack2 and return it.

方法二肯定比方法一好。方法1在enQueue操作中移动所有元素两次，而方法2(在deQueue操作中)移动元素一次，并且仅在stack2为空时移动元素。