Discussion :

[Baptiste Wicht]

Bonjour,

On nous as donné comme problème de créer une implémentation de FIFO en utilisant exclusivement une LIFO. Jusque là, pas de problèmes, c'est très simple à implémenter, mais la consigne indique qu'on doit fournir toutes les opérations en O(1) en complexité amortie.

J'ai beau retourner le problème dans tous les sens, je n'ai pas trouvé de solution avec cette complexité.

Est-ce que quelqu'un sait comment on pourrait faire ? Je suis sûr qu'il doit exister une solution même pas trop compliqué, mais j'arrive pas à voir comment

Merci d'avance

[pseudocode]

Il suffit de prendre 2 FIFO :

- une FIFO "input" dans laquelle on "push()" les nouveaux éléments.
- une FIFO "ouput" depuis laquelle on "pop()" les éléments.
- un algo extrêmement complexe qui transfert "input" dans "output" lorsque on fait un "pop()" et que "ouput" est vide.

Le worst case est donc le 1er pop() apres une suite de N push(), ce qui nous fait une compléxité amortie de :

(N*push() + N*transfert() + 1*Pop()) / (N+1 opérations) = (2N+1)/(N+1) = O(1)

[Baptiste Wicht]

C'est plus compliqué que je pensais

Par contre, tu me dis de prendre deux FIFO, mais j'ai besoin d'implémenter une FIFO avec une (ou plusieurs LIFO). Est-ce que la technique reste la même ?

[Obsidian]

Il suffit de prendre 2 FIFO :

- une FIFO "input" dans laquelle on "push()" les nouveaux éléments.
- une FIFO "ouput" depuis laquelle on "pop()" les éléments.

FIFO → LIFO, dans ce cas, non ? :-)

[pseudocode]

Par contre, tu me dis de prendre deux FIFO, mais j'ai besoin d'implémenter une FIFO avec une (ou plusieurs LIFO). Est-ce que la technique reste la même ?

Ah, excuse-moi. Habituellement c'est dans l'autre sens qu'on pose l'exercice.

On peut également résoudre ton problème avec 2 LIFO, mais l'algo est un poil plus complexe. Le but c'est de créer une LIFO "renversée" au moment du pop():

- push() : on fait un "enqueue" classique dans la LIFO "input"

- pop(): on fait un "reverse" de la LIFO "input", et on transfère le contenu (eventuel) de la LIFO "output" dans la LIFO "input". A ce stade, la LIFO "input" contient toutes les entrées a l'envers, et la LIFO output est vide. Il ne nous reste qu'a swapper les deux LIFO et faire un "dequeue" de la LIFO "output".

Par contre je ne suis pas sur qu'on puisse avoir facilement une complexité amortie en O(1). Ca doit pouvoir se faire en optimisant les cas.

[Baptiste Wicht]

Oki, merci beaucoup pour tes réponses