Amortized analysis: FIFO with two stacks

How to implement a FIFO queue using开发者_开发百科 two stacks so that each FIFO operation takes amortized constant time?

At the risk of giving the whole answer (I'm hoping the exercise is to write the code, not to just give this answer)...

Push onto one to enqueue, pop off of the other to poll. When the output stack is empty, move all of the items one-by-one from the input stack to the output stack.

Something like that:

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;
}