Амортизированный анализ: 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;
}