摊销分析：具有两个堆栈的 FIFO

Question

如何使用两个堆栈实现 FIFO 队列，以便每个 FIFO 操作都需要摊销常数时间？

Answer 1

冒着给出整个答案的风险（我希望练习是编写代码，而不是仅仅给出这个答案）...

推入一个以排队，弹出另一个以进行轮询。当输出堆栈为空时，将所有项目从输入堆栈一一移至输出堆栈。

Answer 2

像这样的东西：

template <class T>
class FIFO
{
  stack<T> myStack;
  stack<T> myStackReversed;

 public:

  void enqueue(T data);
  T    dequeue();
};

template <class T>
void FIFO<T>::enqueue(T data)
{
  myStack.push(data);
}

template <class T>
T FIFO<T>::dequeue()
{
  if (myStackReversed.size() == 0)
  {
    int size = myStack.size();
    for (int i=0; i<size; i++)
    {
      myStackReversed.push(myStack.top());
      myStack.pop();
    }
  }

  T ret = myStackReversed.top();
  myStackReversed.pop();

  return ret;
}