data-structures - 償却分析: 2 つのスタックを持つ FIFO

Question

各 FIFO 操作に一定の償却時間がかかるように、2 つのスタックを使用して FIFO キューを実装する方法は?

Answer 1

全体の答えを与えるリスクがあります（この答えを与えるだけでなく、コードを書くことが演習になることを願っています）...

一方を押してエンキューし、もう一方をポップしてポーリングします。出力スタックが空になったら、すべてのアイテムを入力スタックから出力スタックに 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;
}