Comment implémenter une file d'attente FIFO en utilisant deux piles de sorte que chaque opération FIFO prenne un temps constant amorti?Analyse amortie: FIFO avec deux piles
0
A
Répondre
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.
0
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;
}
Questions connexes
- 1. AJAX et Rails: deux piles ou une?
- 2. concernant l'analyse amortie?
- 3. Problème avec fifo non bloquant dans bash
- 4. Synchronisation Linux avec file d'attente FIFO
- 5. Chiffrement SERVER utilisant FIFO
- 6. mise en œuvre FIFO
- 7. Exécution d'une simulation FIFO
- 8. Basculer entre plusieurs piles dans gdb 6.3
- 9. UNIX FIFO: Comment permettre à une seule paire d'écriture/lecteur d'utiliser une FIFO?
- 10. Prototype JavaScript Ajax FIFO Queue
- 11. Interprétation des piles dans Windows Minidumps
- 12. écrire dans fifo/pipe depuis shell, avec timeout
- 13. Informix: Evaluation de Fifo avec des procédures SQL/Stockées
- 14. analyse json avec rhomobile
- 15. analyse syntaxique avec dom4j
- 16. Analyse JSON avec jQuery
- 17. Analyse XML avec AS2
- 18. Analyse XML avec jQuery
- 19. Analyse avec MaltParser engmalt
- 20. Analyse XML avec AS3
- 21. Analyse JSON avec Javascript
- 22. Analyse XML avec REXML
- 23. Analyse d'une chaîne dans Date avec DateFormat pas analyse correcte
- 24. Comment analyser les piles de tas
- 25. Explication du fonctionnement des piles dans C
- 26. Problème PHP avec DOM analyse
- 27. Analyse d'une boucle avec ANTLR
- 28. analyse xml avec php, enfants
- 29. Analyse XML CDATA avec Xmllite
- 30. Analyse XML avec C#, XPath
S'il vous plaît suivre la question [général] (http://tinyurl.com/so-hints) [lignes directrices] (http://meta.stackexchange.com/q/10812), énoncez toutes les restrictions spéciales, montrez ce que vous avez essayé jusqu'à présent et posez des questions sur ce qui vous trouble particulièrement. –