Comment implémenter une file d'attente avec trois piles?

Je suis tombé sur cette question dans un livre sur les algorithmes ( Algorithmes, 4e édition par Robert Sedgewick et Kevin Wayne).

File d'attente avec trois piles. Implémentez une file d'attente avec trois piles afin que chaque opération de file d'attente prenne un nombre constant (pire des cas) d'opérations de pile. Attention: niveau de difficulté élevé.

Je sais faire une file d'attente avec 2 piles mais je ne trouve pas la solution avec 3 piles. Une idée ?

(oh et, ce ne sont pas des devoirs :))

RÉSUMÉ

• L'algorithme O (1) est connu pour 6 piles
• L'algorithme O (1) est connu pour 3 piles, mais utilisant une évaluation paresseuse qui en pratique correspond à avoir des structures de données internes supplémentaires, il ne constitue donc pas une solution
• Les gens près de Sedgewick ont ​​confirmé qu'ils n'étaient pas au courant d'une solution à 3 piles dans toutes les contraintes de la question initiale

DÉTAILS

Il y a deux implémentations derrière ce lien: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

L'un d'eux est O (1) avec trois piles MAIS il utilise une exécution paresseuse, qui en pratique crée des structures de données intermédiaires supplémentaires (fermetures).

Un autre d'entre eux est O (1) mais utilise SIX piles. Cependant, cela fonctionne sans exécution paresseuse.

MISE À JOUR: Le papier d'Okasaki est ici: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps et il semble qu'il n'utilise en fait que 2 piles pour la version O (1) qui a une évaluation paresseuse. Le problème est qu'il est vraiment basé sur une évaluation paresseuse. La question est de savoir s'il peut être traduit en un algorithme à 3 piles sans évaluation paresseuse.

MISE À JOUR: Un autre algorithme connexe est décrit dans l'article "Stacks versus Deques" par Holger Petersen, publié dans la 7e Conférence annuelle sur l'informatique et la combinatoire. Vous pouvez trouver l'article de Google Livres. Consultez les pages 225-226. Mais l'algorithme n'est pas en fait une simulation en temps réel, c'est une simulation en temps linéaire d'une file d'attente à deux extrémités sur trois piles.

gusbro: "Comme @Leonel l'a dit il y a quelques jours, j'ai pensé qu'il serait juste de vérifier auprès du professeur Sedgewick s'il connaissait une solution ou s'il y avait une erreur. Alors je lui ai écrit. Je viens de recevoir une réponse (mais pas de lui-même mais d'un collègue de Princeton) donc j'aime partager avec vous tous. Il a essentiellement dit qu'il ne connaissait aucun algorithme utilisant trois piles ET les autres contraintes imposées (comme ne pas utiliser d'évaluation paresseuse). Il connaissait un algorithme utilisant 6 piles comme nous le savons déjà en regardant les réponses ici. Donc, je suppose que la question est toujours ouverte pour trouver un algorithme (ou prouver qu'on ne peut pas en trouver). "

Ok, c'est vraiment difficile, et la seule solution que j'ai pu trouver, me rappelle la solution de Kirks au test de Kobayashi Maru (triché en quelque sorte): L'idée, c'est que nous utilisons une pile de piles (et l'utilisons pour modéliser une liste ). J'appelle les opérations en / dequeue et push and pop, puis on obtient:

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

(StackX = StackY n'est pas une copie du contenu, juste une copie de référence. C'est juste pour le décrire facilement. Vous pouvez également utiliser un tableau de 3 piles et y accéder via index, là vous changerez simplement la valeur de la variable d'index ). Tout est en O (1) en termes d'opération de pile.

Et oui, je sais que c'est discutable, car nous avons implicite plus de 3 piles, mais peut-être que cela donne à d'autres de vous de bonnes idées.

EDIT: Exemple d'explication:

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

J'ai essayé ici avec un peu d'art ASCII pour montrer Stack1.

Chaque élément est enveloppé dans une seule pile d'éléments (nous n'avons donc qu'une pile de piles de type sécurisé).

Vous voyez pour supprimer on pop d'abord le premier élément (la pile contenant ici les éléments 1 et 2). Ensuite, faites apparaître l'élément suivant et dépliez-y le 1. Ensuite, nous disons que la première pile affichée est maintenant notre nouvelle Stack1. Pour parler un peu plus fonctionnel - ce sont des listes implémentées par piles de 2 éléments où l'élément supérieur est cdr et le premier élément supérieur / inférieur est voiture . Les 2 autres aident les piles.

L'insertion est particulièrement délicate, car vous devez en quelque sorte plonger profondément dans les piles imbriquées pour ajouter un autre élément. C'est pourquoi Stack2 est là. Stack2 est toujours la pile la plus interne. L'ajout consiste alors simplement à pousser un élément puis à pousser sur un nouveau Stack2 (et c'est pourquoi nous ne sommes pas autorisés à toucher Stack2 dans notre opération de retrait de la file d'attente).

Je vais tenter une preuve pour montrer que cela ne peut pas être fait.

Supposons qu'il existe une file d'attente Q simulée par 3 piles, A, B et C.

Assertions

• ASRT0: = De plus, supposons que Q puisse simuler des opérations {queue, dequeue} dans O (1). Cela signifie qu'il existe une séquence spécifique de push / pop de pile pour chaque opération de file d'attente / de retrait à simuler.

• Sans perte de généralité, supposons que les opérations de file d'attente sont déterministes.

Laissez les éléments mis en file d'attente dans Q numérotés 1, 2, ..., en fonction de leur ordre de file d'attente, le premier élément mis en file d'attente dans Q étant défini comme 1, le second comme 2, et ainsi de suite.

Définir

• Q(0) := L'état de Q quand il y a 0 élément dans Q (et donc 0 élément dans A, B et C)
• Q(1) := L'état de Q (et A, B et C) après 1 opération de file d'attente sur Q(0)
• Q(n) := L'état de Q (et A, B et C) après n opérations de file d'attente sur Q(0)

Définir

• |Q(n)| :=le nombre d'éléments dans Q(n)(donc |Q(n)| = n)
• A(n) := l'état de la pile A lorsque l'état de Q est Q(n)
• |A(n)| := le nombre d'éléments dans A(n)

Et des définitions similaires pour les piles B et C.

Trivialement,

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)| est évidemment illimité sur n.

Par conséquent, au moins un de |A(n)|, |B(n)|ou |C(n)|est illimité sur n.

WLOG1, supposons que la pile A est illimitée et que les piles B et C sont limitées.

Définir * B_u :=une borne supérieure de B * C_u :=une borne supérieure de C *K := B_u + C_u + 1

WLOG2, pour un n tel que |A(n)| > K, sélectionnez K éléments dans Q(n). Supposons que 1 de ces éléments soit dans A(n + x), pour tous x >= 0, c'est-à-dire que l'élément est toujours dans la pile A quel que soit le nombre d'opérations de file d'attente effectuées.

• X := cet élément

Ensuite, nous pouvons définir

• Abv(n) :=le nombre d'articles dans la pile A(n)qui est supérieur à X

• Blo(n) :=le nombre d'éléments dans la pile A(n)qui est inférieur à X

  | A (n) | = Abv (n) + Blo (n)

ASRT1 :=Le nombre de pop requis pour retirer X de la file d'attente Q(n)est d'au moinsAbv(n)

De ( ASRT0) et ( ASRT1), ASRT2 := Abv(n)doivent être délimités.

Si Abv(n)est illimité, alors si 20 sorties de file d'attente sont nécessaires pour retirer X de la file d'attente Q(n), il faudra au moins Abv(n)/20pops. Ce qui est illimité. 20 peut être n'importe quelle constante.

Par conséquent,

ASRT3 := Blo(n) = |A(n)| - Abv(n)

doit être illimité.

WLOG3, nous pouvons sélectionner les éléments K à partir du bas de A(n), et l'un d'eux est A(n + x)pour tousx >= 0

X(n) := cet élément, pour tout n donné

ASRT4 := Abv(n) >= |A(n)| - K

Chaque fois qu'un élément est mis en file d'attente dans Q(n)...

WLOG4, supposons que B et C soient déjà remplis jusqu'à leurs limites supérieures. Supposons que la limite supérieure des éléments ci-dessus X(n)a été atteinte. Ensuite, un nouvel élément entre A.

WLOG5, supposons qu'en conséquence, le nouvel élément doit entrer ci-dessous X(n).

ASRT5 := Le nombre de pops requis pour mettre un élément ci-dessous X(n) >= Abv(X(n))

De (ASRT4), Abv(n)est illimité sur n.

Par conséquent, le nombre de pops requis pour placer un élément ci X(n)- dessous est illimité.

Cela contredit ASRT1, par conséquent, il n'est pas possible de simuler une O(1)file d'attente avec 3 piles.

C'est à dire

Au moins 1 pile doit être illimitée.

Pour un élément qui reste dans cette pile, le nombre d'éléments au-dessus doit être limité, ou l'opération de retrait de la file d'attente pour supprimer cet élément sera illimitée.

Cependant, si le nombre d'éléments au-dessus est limité, il atteindra une limite. À un moment donné, un nouvel élément doit entrer en dessous.

Puisque nous pouvons toujours choisir l'ancien élément parmi l'un des quelques éléments les plus bas de cette pile, il peut y avoir un nombre illimité d'éléments au-dessus (en fonction de la taille illimitée de la pile illimitée).

Pour entrer un nouvel élément en dessous, comme il y a un nombre illimité d'éléments au-dessus, un nombre illimité de pops est nécessaire pour placer le nouvel élément en dessous.

Et donc la contradiction.

Il existe 5 instructions WLOG (sans perte de généralité). Dans un certain sens, ils peuvent être intuitivement compris comme vrais (mais étant donné qu'ils sont 5, cela peut prendre un certain temps). La preuve formelle qu'aucune généralité n'est perdue peut être obtenue, mais elle est extrêmement longue. Ils sont omis.

J'admets qu'une telle omission pourrait laisser les déclarations WLOG en question. Avec la paranoïa d'un programmeur pour les bogues, veuillez vérifier les instructions WLOG si vous le souhaitez.

La troisième pile n'est pas non plus pertinente. Ce qui compte, c'est qu'il y ait un ensemble de piles délimitées et un ensemble de piles illimitées. Le minimum nécessaire pour un exemple est de 2 piles. Le nombre de piles doit être, bien entendu, fini.

Enfin, si j'ai raison de dire qu'il n'y a pas de preuve, alors il devrait y avoir une preuve inductive plus facile disponible. Probablement basé sur ce qui se passe après chaque file d'attente (gardez une trace de la façon dont cela affecte le pire cas de retrait de la file d'attente étant donné l'ensemble de tous les éléments de la file d'attente).

Remarque: Ceci est destiné à être un commentaire sur l'implémentation fonctionnelle des files d'attente en temps réel (dans le pire des cas en temps constant) avec des listes à liaison unique. Je ne peux pas ajouter de commentaires en raison de la réputation, mais ce serait bien si quelqu'un pouvait changer cela en un commentaire ajouté à la réponse par antti.huima. Là encore, c'est un peu long pour un commentaire.

@ antti.huima: Les listes liées ne sont pas les mêmes qu'une pile.

• s1 = (1 2 3 4) --- une liste chaînée avec 4 nœuds, chacun pointant vers celui de droite et contenant les valeurs 1, 2, 3 et 4

• s2 = popped (s1) --- s2 est maintenant (2 3 4)

À ce stade, s2 équivaut à popped (s1), qui se comporte comme une pile. Cependant, s1 est toujours disponible pour référence!

• s3 = popped (popped (s1)) --- s3 est (3 4)

Nous pouvons toujours jeter un œil à s1 pour obtenir 1, alors que dans une implémentation de pile appropriée, l'élément 1 est parti de s1!

Qu'est-ce que ça veut dire?

• s1 est la référence au sommet de la pile
• s2 est la référence au deuxième élément de la pile
• s3 est la référence au troisième ...

Les listes chaînées supplémentaires créées maintenant servent chacune de référence / pointeur! Un nombre fini de piles ne peut pas faire cela.

D'après ce que je vois dans les articles / code, les algorithmes utilisent tous cette propriété des listes liées pour conserver les références.

Edit: Je fais référence uniquement aux algorithmes de liste chaînée 2 et 3 qui utilisent cette propriété des listes liées, comme je les ai lues en premier (elles semblaient plus simples). Cela ne vise pas à montrer qu'elles sont ou ne sont pas applicables, mais simplement à expliquer que les listes chaînées ne sont pas nécessairement identiques. Je lirai celui avec 6 quand je serai libre. @Welbog: Merci pour la correction.

La paresse peut également simuler la fonctionnalité du pointeur de manière similaire.

L'utilisation de la liste chaînée résout un problème différent. Cette stratégie peut être utilisée pour implémenter des files d'attente en temps réel dans Lisp (ou au moins Lisps qui insistent sur la construction de tout à partir de listes liées): Reportez-vous à "Opérations de file d'attente en temps réel dans Pure Lisp" (lié à travers les liens de antti.huima). C'est aussi un bon moyen de concevoir des listes immuables avec un temps d'opération O (1) et des structures partagées (immuables).

Vous pouvez le faire en temps constant amorti avec deux piles:

------------- --------------
            | |
------------- --------------

L'ajout O(1)et la suppression se font O(1)si le côté à partir duquel vous voulez prendre n'est pas vide et O(n)sinon (divisez l'autre pile en deux).

L'astuce est de voir que l' O(n)opération ne sera effectuée qu'à chaque O(n)fois (si vous divisez, par exemple en deux). Par conséquent, la durée moyenne d'une opération est de O(1)+O(n)/O(n) = O(1).

Bien que cela puisse poser problème, si vous utilisez un langage impératif avec une pile basée sur un tableau (la plus rapide), vous n'aurez de toute façon amorti que le temps constant.