摊销分析：具有两个堆栈的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; 
}