Analyse amortie: FIFO avec deux piles

Question

Comment implémenter une file d'attente FIFO en utilisant deux piles de sorte que chaque opération FIFO prenne un temps constant amorti?

Answer 1

Au risque de donner toute réponse (j'espère que l'exercice est d'écrire le code, pas simplement donner cette réponse) ...

pousser sur un à ENQUEUE, pop hors de l'autre pour interroger. Lorsque la pile de sortie est vide, déplacez tous les éléments un par un de la pile d'entrée vers la pile de sortie.

Answer 2

Quelque chose comme ça:

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