Comment mettre en œuvre une file d'attente avec trois piles ?

Question

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

File d'attente avec trois piles. Implémentez une file d'attente avec trois piles de façon à ce que chaque opération de la file d'attente nécessite un nombre constant (dans le pire des cas) d'opérations sur la pile. Attention : degré élevé de difficulté.

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

(oh et, ce n'est pas un devoir :) )

Answer 1

RÉSUMÉ

• Un algorithme O(1) est connu pour 6 piles
• Un algorithme O(1) est connu pour 3 piles, mais il utilise une évaluation paresseuse qui, en pratique, correspond à avoir des structures de données internes supplémentaires, ce qui ne constitue pas une solution.
• Les habitants de Sedgewick ont confirmé qu'ils n'avaient pas connaissance d'une solution à trois étages respectant 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'une d'entre elles est O(1) avec trois piles MAIS elle utilise l'exécution paresseuse, ce 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, elle fonctionne sans l'exécution paresseuse.

MISE À JOUR : l'article 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 l'é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 apparenté 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 sur Google Books. Consultez les pages 225-226. Mais l'algorithme n'est pas une simulation en temps réel, c'est une simulation en temps linéaire d'une file d'attente à double extrémité 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. Je lui ai donc écrit. Je viens de recevoir une réponse (bien qu'elle ne vienne pas de lui mais d'un collègue de Princeton) que j'aimerais partager avec vous tous. Il a dit essentiellement qu'il ne connaissait aucun algorithme utilisant trois piles ET les autres contraintes imposées (comme ne pas utiliser l'évaluation paresseuse). Il connaissait un algorithme utilisant 6 piles comme nous le savons déjà en regardant les réponses ici. Je suppose donc que la question reste ouverte pour trouver un algorithme (ou prouver qu'il est impossible d'en trouver un)."

Answer 2

Ok, c'est vraiment difficile, et la seule solution que j'ai pu trouver me rappelle la solution de Kirk au test du Kobayashi Maru (j'ai en quelque sorte triché) : L'idée est d'utiliser une pile de piles (et de l'utiliser pour modéliser une liste). J'appelle les opérations en/dequeue et push et 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 la référence. C'est juste pour le décrire facilement. Vous pourriez également utiliser un tableau de 3 piles et y accéder par l'intermédiaire de l'index, il vous suffirait alors de changer la valeur de la variable index). Tout est en O(1) en termes d'opérations sur les piles.

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

EDIT : Exemple d'explication :

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

J'ai essayé ici avec un petit ASCII-art pour montrer Stack1.

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

Vous voyez que pour enlever, nous devons d'abord ouvrir le premier élément (la pile contenant ici les éléments 1 et 2). Ensuite, on ouvre l'élément suivant et on enlève le 1. Ensuite, on dit que la première pile ouverte est maintenant notre nouvelle pile 1. Pour parler de manière un peu plus fonctionnelle, il s'agit de listes mises en œuvre par des piles de 2 éléments où l'élément supérieur est cdr et l'élément supérieur premier/bas est voiture . Les 2 autres sont des piles d'aide.

L'insertion est plus délicate, car il faut en quelque sorte plonger profondément dans les piles imbriquées pour ajouter un autre élément. C'est pourquoi la pile 2 est là. La pile 2 est toujours la pile la plus interne. L'ajout se résume alors à pousser un élément à l'intérieur, puis à pousser au-dessus une nouvelle pile 2 (et c'est pourquoi nous ne sommes pas autorisés à toucher à la pile 2 dans notre opération de dequeue).

Answer 3

Je vais tenter une démonstration pour montrer que c'est impossible.

---

Suppose there is a queue Q that is simulated by 3 stacks, A, B and C.

Assertions
ASRT0 := Furthermore, assume that Q can simulate operations {queue,dequeue} in O(1). This means that there exists a specific sequence of stack push/pops for every queue/dequeue operation to be simulated.

Without loss of generality
WLOG0, assume the queue operations are deterministic

Let the elements queued into Q be numbered 1, 2, ..., based on their order of queue, with the first element that is queued into Q being defined as 1, the second one as 2, and so on.

Define
Q(0) := The state of Q when there are 0 elements in Q (and thus 0 elements in A, B and C)
Q(1) := The state of Q (and A, B and C) after 1 queue operation on Q(0)
Q(n) := The state of Q (and A, B and C) after n queue operations on Q(0)

Define
|Q(n)| := the number of elements in Q(n) (therefore |Q(n)| = n)
A(n) := the state of the stack A when the state of Q is Q(n)
|A(n)| := be the number of elements in A(n)
And similar definitions for stacks B and C.

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

---

|Q(n)| is obviously unbounded on n.
Therefore, at least one of |A(n)|, |B(n)| or |C(n)| is unbounded on n.

WLOG1, suppose stack A is unbounded and stacks B and C are bounded.

Define
B_u := an upper bound of B
C_u := an upper bound of C
K := B_u + C_u + 1

WLOG2, for an n such that |A(n)| > K, select K elements from Q(n). Suppose that 1 of those elements is in A(n + x), for all x >= 0, i.e. the element is always in stack A no matter how many queue operations are done.
X := that element

Then we can define 
Abv(n) := the number of items in stack A(n) that is above X
Blo(n) := the number of elements in stack A(n) that is below X

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

ASRT1 := The number of pops required to dequeue X from Q(n) is at least Abv(n)

From (ASRT0) and (ASRT1),
ASRT2 := Abv(n) must be bounded.
If Abv(n) is unbounded, then if 20 dequeues are required to dequeue X from Q(n), it will require at least Abv(n)/20 pops. Which is unbounded. 20 can be any constant.

Therefore,
ASRT3 := Blo(n) = |A(n)| - Abv(n)
must be unbounded.

--- ---

WLOG3, we can select the K elements from the bottom of A(n), and one of them is in A(n + x) for all x >= 0
X(n) := that element, for any given n

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

Whenever an element is queued into Q(n)...

WLOG4, suppose B and C are already filled to their upper bounds. Suppose that the upper bound for elements above X(n) has been reached. Then, a new element enters A.
WLOG5, suppose that as a result, the new element must enter below X(n).

ASRT5 := The number of pops required to put an element below X(n) >= Abv(X(n))

From (ASRT4), Abv(n) is unbounded on n.

Therefore, the number of pops required to put an element below X(n) is unbounded.

---

This contradicts ASRT1, therefore, it is not possible to simulate an O(1) queue with 3 stacks.

---

I.e.

Au moins une pile doit être non limitée.

Pour un élément qui reste dans cette pile, le nombre d'éléments au-dessus de lui doit être limité, sinon l'opération de dequeue pour retirer cet élément ne sera pas limitée.

Cependant, si le nombre d'éléments au-dessus de lui 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 les quelques éléments les plus bas de cette pile, il peut y avoir un nombre illimité d'éléments au-dessus de lui (sur la base de la taille illimitée de la pile illimitée).

Pour introduire un nouvel élément en dessous, puisqu'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 déclarations WLOG (Without loss of generality). Dans un certain sens, on peut comprendre intuitivement qu'elles sont vraies (mais étant donné qu'elles sont au nombre de 5, cela peut prendre un certain temps). La preuve formelle qu'aucune généralité n'est perdue peut être dérivée, mais elle est extrêmement longue. Elles sont omises.

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

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

Enfin, si j'ai raison de dire qu'il n'y a pas de preuve, alors une preuve inductive plus facile devrait être disponible. Probablement en se basant sur ce qui se passe après chaque file d'attente (suivre comment cela affecte le pire cas de dequeue étant donné l'ensemble de tous les éléments de la file d'attente).

Answer 4

Note : Ceci est censé être un commentaire sur l'implémentation fonctionnelle des files d'attente en temps réel (temps constant dans le pire des cas) avec des listes singulièrement liées. Je ne peux pas ajouter de commentaires à cause de ma réputation, mais ce serait bien si quelqu'un pouvait changer ceci en un commentaire ajouté à la réponse de antti.huima. Mais bon, c'est un peu long pour un commentaire.

@antti.huima : Les listes chaînées ne sont pas identiques à une pile.

• s1 = (1 2 3 4) --- une liste liée avec 4 noeuds, chacun pointant vers celui de droite, et contenant les valeurs 1, 2, 3 et 4

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

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

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

Nous pouvons toujours regarder dans s1 pour obtenir 1, alors que dans une implémentation correcte de la pile, l'élément 1 a disparu de s1 !

Qu'est-ce que cela signifie ?

• 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 à la troisième ...

Les listes lié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/codes, les algorithmes utilisent tous cette propriété des listes liées pour conserver les références.

Edit : Je me réfère uniquement aux algorithmes de listes liées 2 et 3 qui utilisent cette propriété des listes liées, car je les ai lus en premier (ils avaient l'air plus simples). Ce n'est pas pour montrer qu'ils sont ou non applicables, juste pour expliquer que les linked-lists ne sont pas forcément identiques. Je lirai celui avec 6 quand je serai libre. @Welbog : Merci pour la correction.

---

La paresse peut également simuler la fonctionnalité des pointeurs de manière similaire.

---

L'utilisation de linked-list 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 en Lisp (ou du moins en Lisp qui insiste pour tout construire à partir de listes liées) : Reportez-vous à "Real Time Queue Operations in Pure Lisp" (accessible par les liens d'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).

Answer 5

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

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

L'ajout est O(1) et la suppression est O(1) si le côté que vous voulez prendre n'est pas vide et O(n) sinon (diviser l'autre pile en deux).

L'astuce consiste à s'assurer que le O(n) L'opération ne sera effectuée que tous les O(n) temps (si vous le divisez, par exemple, en deux). Ainsi, le temps moyen d'une opération est O(1)+O(n)/O(n) = O(1) .

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