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

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

File d'attente avec trois piles. Mettre en œuvre une file d'attente avec trois piles de sorte que chaque file d'attente, l'opération prend une constante (dans le pire des cas), le nombre de pile opérations. Avertissement : degré de difficulté élevé.

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

(oh, et, ce n'est pas de devoirs 🙂 )

  • Êtes-vous vraiment sûr que votre 2 pile solution est vraiment une file d'attente, et que la queue de la file d'attente n'est pas l'alternance de son ordre?
  • Oui mes 2 pile solution est une file d'attente. Une pile est utilisée pour mettre en file d'attente, les autres à la file d'attente. Si la sortie de la pile est vide, l'entrée de la pile est poussé vers la sortie de la pile, de manière efficace de l'inverser.
  • Je suppose que c'est un Tour de Hanoi variante.
  • Je pense que vous avez raison, mais ce que signifie "constante ops" dans le TOH?
  • Ah en effet !
  • Si vous avez compris, vous pouvez écrire votre propre réponse et de l'accepter;)
  • utilisez votre 2 approche de la pile avec une pile sans utilisation, vous pourrez l'étendre pour n > 2 de la file d'attente 😀
  • double possible de la Conception d'une pile qui peut également retirer en O(1) amorti temps?
  • ...ou peut-être pas. En tout cas, la référence est algs4.cs.princeton.edu/13stacks article 43.
  • Cette question n'est pas un doublon, car il demande O(1) amorti temps tandis que celui-ci demande O(1) le pire des cas pour chaque opération. DuoSRX deux-pile solution est déjà en O(1) amorti temps par opération.
  • Pour les trois piles, je pense que le troisième ajout d'une pile de mise en œuvre est pour inserts qui seraient normalement rester vide et quand itérer seraient retirés, & ajouté à l'une des deux autres, mais dans le cas de plusieurs insertions et pas de l'itération dans / à travers l'un des deux autres, vous feriez courir dans des problèmes. Bonne question.
  • BTW, pouvez-vous citer le titre du livre c'est?
  • c'est à partir des "Algorithmes" 4ème Édition de Robert Sedgewick et Kevin Wayne.
  • Le texte ici dire que seule la "file d'attente" de l'opération doivent être des constantes de temps? c'est à dire, file d'attente peut être O(n)? Je suppose que non, car cela peut être résolu avec seulement 2 piles.
  • Tout d'abord, votre solution à deux pile cas a amorti (pas "normal") d'un coût de O(1) pour chaque opération - est-ce acceptable pour votre question? Si oui, alors quel est l'inconvénient de l' @Saeed son idée? 🙂 Juste Essayer de undertand la question.
  • L'auteur assurer de ne plaisantait pas quand il a dit "Avertissement : degré de difficulté élevé."
  • Je ne suis pas sûr de ce que l'auteur veut dire par cette déclaration-> prend constante (dans le pire des cas), le nombre de pile de l'exploitation. Veut-il dire qu'il veut dans le pire des cas, les délais de complexité, ou veut-il dire que dans le pire des cas , la complexité du temps doit être constante??Si le cas est le dernier de la de deux, puis de l'hôpital d'ottawa semble être une solution pour moi.
  • Pire-cas du temps de la complexité désigne le pire moment de la complexité pour toutes les entrées possibles. Par exemple, si une opération a été constante, et la plupart du temps, mais linéaire, à certains moments, son pire des cas est linéaire. Le "pire" dans ce contexte signifie "moins efficace". Ainsi, l'auteur demande une file d'attente mis en œuvre à l'aide de trois piles telles que toutes les opérations de mise en attente peut être fait dans un constant nombre de mesures, comme quelque chose de moins performant que celui, par définition, être le pire des cas.
  • Donc ce qu'il fait dire , qu'il veut que l'opération peut se faire en O(1) le temps de la complexité.. j'.e constante de temps.Ou je me trompe encore?
  • Oui, c'est ma compréhension de la question.
  • malheureusement, la complexité du temps de la Tour de Hanoï est nulle part près de la constante de temps!
  • Le nombre de piles de vraiment aider? Je ne suis pas convaincu que si le fait d'avoir 100 piles de même rendre le problème plus facile (ou valide)
  • Peut-être qu'il est temps d'écrire au prof. Sedgewick et lui demander comment résoudre cette question.
  • Je viens de le premier (allemand) édition de la Sedgewick-il cette cession n'est pas dans. C'est que l'exacte et complète libellé, ou est-il comme "et dans le cas où il n'est pas possible, la preuve il"?
  • Quand il dit "file d'attente" de l'opération, est-ce que signifie "mettre en file d'attente" et de la "file d'attente" ou seulement l'un d'eux? Je sais que c'est un daft question, mais à la file d'attente de quelque chose est de le placer dans une ligne ou "mettre en file d'attente", auquel cas ce serait problème trivial.
  • la file d'attente de l'opération". Si toutes les méthodes d'une classe de File d'attente: mettre en file d'attente, file d'attente, vide, etc.
  • Jason S. du lien dans le commentaire n ° 9 va vous prendre pour le texte complet du problème.
  • elle peut être faite avec 6 piles
  • Je pense que c'est un jeu de mots, par les auteurs des livres...
  • Pourquoi? Parce que vous ne pouvez pas le résoudre?
  • Non... parce que quand vous regardez la littérature académique fonctionnelles pour les implémentations de la file d'attente, qui sont basés généralement sur immuable contre-structuré listes, j'.e des piles, du mieux que je peux trouver est un avec 6 piles. J'imagine que si une solution avec 3 piles existé, il aurait été publié quelque part, comme un 6-pile solution a été au-dessus de la publication académique seuil. Je ne peux pas résoudre le problème, soit, mais qui n'a pas d'importance ici.
  • Capot–Melville, qui est essentiellement rien de plus qu'une note de bas de page Leong–Seiferas, a été publié en tant que tech rapport et dans le journal de Traitement de l'Information des Lettres, ce qui n'est pas à distance prestigieux maintenant (et n'était probablement pas à l'époque). Il n'y a aucune raison de penser qu'une établi académique comme Sedgewick se donne la peine d'écrire un trois-pile de solution.
  • Bien sûr, je n'ai pas de problèmes avec ça. Espérons que les trois-pile solution est trouvée à partir de quelque part, ou que quelqu'un obtient à partir de Sedgewick. Il nous serait cool d'apprendre comment il fonctionne, et comment il a été dérivé.
  • Comme @Leonel a dit il y a quelques jours, j'ai pensé qu'il serait juste de vérifier avec le prof. Sedgewick si il connaissait une solution ou il y avait une erreur. J'ai donc fait de lui écrire. Je viens de recevoir une réponse (qui n'est certes pas de lui-même mais à partir d'un collègue à Princeton) donc je tiens à partager avec vous tous.Il a dit essentiellement qu'il ne connaissait aucun des algorithmes à l'aide de trois piles ET les autres contraintes imposées (comme de ne pas utiliser d'évaluation différée). Il n'a connaissance d'un algorithme à l'aide de 6 piles comme nous le savons en regardant les réponses ici. Donc je suppose que la question est encore ouverte pour trouver un algorithme (ou à prouver que l'on ne peut pas être trouvé).
  • Merci beaucoup --- je suppose que c'est près de s'installer ensuite. 6 piles solution existe (j'en référence dans ma solution) et les personnes proches de l'original de l'auteur de la question ne sont pas conscients de 3 piles solution.
  • J'ai changé ma réponse à une communauté wiki
  • Et copié @gusbro commentaire il
  • Remarque: La question posée dans le texte a été mis à jour à: mettre en Œuvre une file d'attente avec un constant nombre de piles [pas de "3"] de sorte que chaque file d'attente des opérations prend une constante (dans le pire des cas), le nombre de pile opérations. Avertissement: degré de difficulté élevé. (algs4.cs.princeton.edu/13stacks - Section 1.3.43). Il semble que le prof. Sedgewick a concédé le défi d'origine.

InformationsquelleAutor DuoSRX | 2011-04-04
  1. 41

    RÉSUMÉ

    • Algorithme O(1) est connu pour 6 piles
    • Algorithme O(1) est connu pour 3 piles, mais l'utilisation de l'évaluation différée qui en pratique correspond à avoir des structures de données internes, de sorte qu'il ne constitue pas une solution
    • Personnes près de Sedgewick ont confirmé qu'ils ne sont pas conscients de 3 pile de solution au sein de toutes les contraintes de la question d'origine

    DÉTAILS

    Il existe 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 paresseux exécution, qui, dans la pratique crée extra intermédiaire des structures de données (fermetures).

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

    Mise à JOUR: Okasaki du papier est ici: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps et il semble qu'il utilise seulement 2 piles pour le O(1) version d'évaluation différée. Le problème, c'est que c'est vraiment basé sur l'évaluation différée. La question est de savoir si elle peut être traduite en un 3-pile algorithme sans évaluation différée.

    Mise à JOUR: un Autre algorithme est décrit dans le document "Piles rapport Deques" de Holger Petersen, publié dans la 7ème Conférence Annuelle de l'Informatique et de la Combinatoire. Vous pouvez retrouver l'article de Google Books. Vérification des pages 225-226. Mais l'algorithme n'est pas fait de simulation en temps réel, c'est linéaire en temps de simulation d'un double-clos de la file d'attente sur trois piles.

    gusbro: "Comme @Leonel a dit il y a quelques jours, j'ai pensé qu'il serait juste de vérifier avec le prof. Sedgewick si il connaissait une solution ou il y avait une erreur. J'ai donc fait de lui écrire. Je viens de recevoir une réponse (qui n'est certes pas de lui-même mais à partir d'un collègue à Princeton) donc je tiens à partager avec vous tous.Il a dit essentiellement qu'il ne connaissait aucun des algorithmes à l'aide de trois piles ET les autres contraintes imposées (comme de ne pas utiliser d'évaluation différée). Il n'a connaissance d'un algorithme à l'aide de 6 piles comme nous le savons en regardant les réponses ici. Donc je suppose que la question est encore ouverte pour trouver un algorithme (ou à prouver que l'on ne peut pas être trouvé)."

    • J'ai juste survolé les documents et les programmes dans votre lien. Mais si je vois qu'ils n'utilisez pas de piles, ils utilisent des listes de type de base. Et l'esp. dans ces listes sont construits avec en-tête et le reste, bref il ressemble à ma solution (et je pense n'est pas droit).
    • Salut, les implémentations sont dans un langage fonctionnel où les listes correspondent à piles, tant que les pointeurs ne sont pas partagés, et ils ne sont pas; les six de la pile de version peut être vraiment mis en œuvre à l'aide de six "plaine" piles. Le problème avec les deux/trois piles de version, c'est qu'il utilise caché des structures de données (fermetures).
    • Êtes-vous sûr que le six-pile solution ne partage pas les pointeurs? Dans rotate, il semble que la front liste est affectée à la fois oldfront et f, et ce sont alors modifiés séparément.
    • Hmm eh bien, j'ai effectivement construit six de la pile de solution dans ma tête avant que je l'ai trouvé à partir de la littérature, donc je suis assez sûr qu'il pourrait être mis en œuvre. De toute façon, plus j'analyse la littérature, plus il devient difficile de croire qu'un O(1) simulation il existe en fait pour trois piles, parce que la seule chose qui est visé est la 6-pile version aussi longtemps que vous assumez calcul déterministe. Peut-être qu'il existe encore, bien que. Ou c'est une erreur dans le livre à partir de laquelle la question vient de.
    • Je suis passé par cette mise en œuvre, et je suis d'accord que ses activités sont en O(1). De même, je ne peux pas trouver un moyen de modifier une solution de ce type à utiliser trois piles au lieu de six.
    • Oui! Ne peux!
    • +1. Okasaki et Tarjan sont deux des pionniers de la "unamortizing" amorti-pire-cas des algorithmes.
    • Le matériel source est algs4.cs.princeton.edu/13stacks a été changé: 43. Mettre en œuvre une file d'attente avec un nombre constant de [pas de "3"] piles de sorte que chaque file d'attente des opérations prend une constante (dans le pire des cas), le nombre de pile opérations. Avertissement: degré de difficulté élevé. Le titre du défi encore dit "File d'attente avec trois piles" toutefois :-).
    • Les six piles lien est mort, savez-vous si cela existe quelque part?
    • Je crois que c'est le document mentionné ci-dessus: westpoint.edu/eecs/SiteAssets/SitePages/...
    • Ici est une fonctionnelle de la mise en œuvre avec 3 piles (avec lazy fonctionnalité). Mais je ne comprends pas comment le convertir à un 6-pile version.

    InformationsquelleAutor
  2. 12

    Ok, c'est vraiment dur, et la seule solution que je pouvais venir, se souvient de moi de Kirk solution du Kobayashi Maru test (en quelque sorte trompé):
    L'idée, c'est que nous utilisons empilement de piles (et l'utilisation de ce modèle dans une liste).
    J'appelle les opérations fr/file d'attente et de push et pop, alors nous obtenons:

    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 est pas de la copie du contenu, juste une copie de référence. Sa viens de décrire, c'est facile. Vous pouvez également utiliser un tableau de 3 piles et d'y accéder via l'index, il vous suffit de changer la valeur de la variable d'index). Tout est en O(1) dans la pile-fonctionnement-conditions.

    Et oui je sais que sa argueable, parce que nous avons implicite plus de 3 piles, mais peut-être donner d'autres bonnes idées.

    EDIT: Explication exemple:

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

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

    Chaque élément enveloppé dans un seul élément de la pile (nous avons seulement typesafe empilement de piles).

    Vous voir pour supprimer nous avons d'abord pop le premier élément (la pile contenant ici l'élément 1 et 2). Puis pop à l'élément suivant et déballez-le, il y le 1er. Ensuite, nous avons dit que la première poped pile est maintenant notre nouveau Stack1. Pour parler un peu plus fonctionnelles, ce sont des listes de mettre en œuvre par des piles de 2 éléments où l'élément supérieur ist cdr et la première/en dessous de l'élément supérieur est voiture. Les 2 autres sont d'aider les piles.

    Esp difficile de l'insertion, comme vous l'avez en quelque sorte avoir à plonger dans l'imbriqués piles pour ajouter un autre élément. C'est pourquoi Stack2 est là. Stack2 est toujours la plus interne de la pile. L'ajout est alors une simple pression sur un élément, puis en les poussant ontop une nouvelle Stack2 (et c'est pourquoi nous ne sommes pas autorisés à toucher Stack2 dans notre file d'attente de l'opération).

    • Pourriez-vous expliquer comment cela fonctionne? Peut-être la trace hors poussant 'A','B','C','D' et puis popping 4 fois?
    • Ok, j'essaie de modifier des explications supplémentaires, mais de prendre quelques instants.
    • Si l'une des opérations dans enqueue (), reportez-vous à Stack1? Comme il est, il me semble que enqueueing vous fera perdre des références à des Piles existantes.
    • Pas de Stack2 est droit. Ils ne sont pas perdu, car la Pile se réfère toujours au plus profond de la pile dans Stack1, de sorte qu'ils sont toujours implicite dans Stack1.
    • Je suis d'accord que c'est de la triche :-). Ce n'est pas 3 piles, c'est 3 pile références. Mais une agréable lecture.
    • Ses un savant système, mais si je comprends bien, il va devoir n tapis quand il y a n éléments poussé dans la file d'attente. La question demande exactement 3 piles.
    • Je sais, c'est pourquoi explicitement déclaré que ses triché (j'ai même passé réputation sur une prime parce que je suis aussi curieux de voir le niveau réel de la solution). Mais au moins prusswan commentaire peut être répondu: Le nombre de piles est important, parce que ma solution est en effet valide, lorsque vous pouvez en utiliser autant que vous le souhaitez.
    • qui a du sens, j'avais oublié le Stack2 = Stack1 dans le constructeur. Merci.
    • +1 pour courageusement la validation de la première réponse.
    • +1 Kobayashi Maru n'était pas de la triche - juste à la pensée latérale

    InformationsquelleAutor flolo
  3. 4

    Je vais tenter une preuve pour montrer qu'il ne peut pas être fait.

    Suppose qu'il y a une file d'attente Q qui est simulé par 3 piles, A, B et C.

    Affirmations

    • ASRT0 := en Outre, supposons que Q peut simuler des opérations {file d'attente file d'attente} en O(1). Cela signifie qu'il existe une séquence spécifique de la pile push/pop pour chaque file d'attente/résorption de l'opération de simulation.

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

    Laisser les éléments de la file d'attente Q être numérotés 1, 2, ..., en fonction de leur ordre de la file d'attente, avec le premier élément qui est mis en file d'attente Q étant définie comme 1, le second 2, et ainsi de suite.

    Définir

    • Q(0) := L'état de Q quand il y a 0 d'éléments de Q (et donc 0 éléments A, B et C)
    • Q(1) := L'état de Q (A, B et C) après le 1er de la file d'attente de l'opération sur Q(0)
    • Q(n) := L'état de Q (A, B et C) après la n de la file d'attente des opérations 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 lorsque l'état de Q est Q(n)
    • |A(n)| := le nombre d'éléments dans A(n)

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

    Trivialement,

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

---

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

    Donc, au moins l'un des |A(n)|, |B(n)| ou |C(n)| est illimitée sur n.

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

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

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

    • X := cet élément

    Alors on peut définir

    • Abv(n) := le nombre d'éléments dans la pile A(n) qui est au-dessus de X

    • Blo(n) := le nombre d'éléments dans la pile A(n) qui est en dessous de X

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

    ASRT1 := Le nombre de pop nécessaires à la résorption de l'X à partir de Q(n) est au moins Abv(n)

    De (ASRT0) et (ASRT1), ASRT2 := Abv(n) doit être limitée.

    Si Abv(n) est illimité, alors si 20 retire sont nécessaires à la résorption de l'X à partir de Q(n), il faudra au moins Abv(n)/20 pop. Qui est sans bornes. 20 peut être n'importe quelle constante.

    Par conséquent,

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

    doit être sans bornes.

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

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

    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 sont déjà remplis à leur limite supérieure. Supposons que la limite supérieure pour les éléments ci-dessus X(n) a été atteint. Ensuite, un nouvel élément entre en A.

    WLOG5, supposons que, par suite, le nouvel élément doit entrer ci-dessous X(n).

    ASRT5 := Le nombre de pop nécessaires pour mettre un élément en dessous de X(n) >= Abv(X(n))

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

    Par conséquent, le nombre de pop nécessaires pour mettre un élément en dessous de X(n) est illimitée.

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

    I. e.

    Au moins 1 pile doit être sans bornes.

    Pour un élément qui reste dans la pile, le nombre d'éléments ci-dessus, il doit être limitée, ou de la résorption de l'opération pour retirer cet élément sera sans bornes.

    Toutefois, si le nombre d'éléments ci-dessus, il est borné, alors il sera d'atteindre une limite. À un certain point, un nouvel élément doit entrer ci-dessous il.

    Parce que nous pouvons toujours choisir l'ancien élément parmi l'un des plus faibles de quelques éléments de la pile, il peut y avoir un nombre illimité d'éléments au-dessus d'elle (basé sur la surabondance de la taille de la surabondance de la pile).

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

    Et donc de la contradiction.

    Il y a 5 WLOG (Sans perte de généralité) consolidés. Dans un certain sens, ils peuvent être intuitivement compris pour être vrai (mais vu qu'ils sont 5, il pourrait prendre un certain temps). La preuve formelle qu'aucune généralité est perdu peut être établie, mais il est extrêmement longue. Ils sont omis.

    Je dois admettre que cette omission pourrait quitter l'WLOG déclarations en question. Avec un programmateur de paranoïa pour les bugs, s'il vous plaît ne vérifier l'WLOG déclarations, si vous le souhaitez.

    La troisième pile est également hors de propos. Ce qui compte c'est qu'il y a un ensemble de délimité les piles, et d'un ensemble d'une surabondance de piles. Le minimum requis pour un exemple est de 2 piles. Le nombre de piles doit être, bien sûr, fini.

    Enfin, si je suis en droit qu'il n'y a pas de preuve, alors il devrait être plus facile inductive de preuve disponibles. Probablement basée sur ce qui se passe après chaque file d'attente (garder une trace de la façon dont il affecte le pire des cas de file d'attente compte tenu de l'ensemble de tous les éléments dans la file d'attente).

    • Je pense que la preuve des œuvres de ces hypothèses - mais je ne suis pas sûr que toutes les piles doivent être vides pour la file d'attente à vide, ou que la somme des tailles des piles doit être égale à la taille de la file d'attente.
    • "WLOG1, supposons que la pile est illimitée, et les piles B et C sont bornées." Vous ne pouvez pas supposer que certains des piles sont bornées, que cela les rendrait inutile (ils seraient les mêmes que O(1) espace de stockage supplémentaire).
    • Parfois, les choses triviales ne sont pas trivial: |Q| = |A|+|B|+|C| est juste, si l'on suppose que pour chaque entrée dans Q vous ajoutez exact on en A, B ou C, mais peut être que vous remarquez est un algorithme, qui a toujours ajouter un élément à deux reprises pour deux piles ou même tous les trois. Et si cela fonctionne de cette façon, vous WLOG1 ne pas tenir plus longtemps (par exemple, imaginez que C une copie d'un (pas que ça fait du sens, mais peut-être qu'il existe un algorithme, avec un ordre différent ou quoi que...)
    • et @mikeb: vous êtes tous Deux à droite. |Q(n)| doit être défini en tant que |A(n)|+|B(n)|+|C(n)|. Et alors |Q(n)| >= n. Par la suite, la preuve serait de travailler avec n, et notez que tant que |Q(n)| plus grande, la conclusion s'applique.
    • Vous pouvez avoir 3 illimité piles et non délimitée piles. Alors au lieu de "B_u + C_u + 1", la preuve peut tout simplement utiliser "1". Fondamentalement, l'expression représente "la somme de la limite supérieure dans délimitée piles + 1", donc le nombre de délimité les piles ne serait pas question.
    • Je pense que c'est l'idée de base de la preuve. Si des piles sont bornés, ils seraient sans valeur. Mais si une pile est illimité, l'accès à certains de ses éléments ne peut jamais être O(1) dans le pire des cas.

    InformationsquelleAutor Dingfeng Quek
  4. 3

    Note: Ceci est destiné à être un commentaire sur la fonctionnelle de la mise en œuvre en temps réel ( temps constant pire des cas ) les files d'attente avec individuellement les listes liées. Je ne peux pas ajouter des commentaires en raison de la réputation, mais il serai sympa si quelqu'un pouvait le changer pour un commentaire annexé à la réponse par antti.huima. Puis de nouveau, c'est un peu long pour un commentaire.

    @antti.huima:
    Les listes chaînées sont pas le même comme une pile.

    • s1 = (1 2 3 4) --- une liste liée avec 4 nœuds, chacun pointant vers la droite, et la tenue des valeurs 1, 2, 3 et 4

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

    À ce point, s2 est équivalent à sauté(s1), qui se comporte comme une pile. Cependant, s1 est toujours disponible pour la référence!

    • s3 = sauté(sauté(s1)) --- s3 (3 4)

    On peut encore lire dans s1 pour obtenir 1, alors que dans une bonne pile de mise en œuvre, l'élément 1 est passé de s1!

    Qu'est-ce que cela signifie?

    • s1 est la référence vers le haut de la pile
    • s2 est la référence pour le deuxième élément de la pile
    • s3 est la référence à la troisième ...

    Supplémentaires listes liées créé maintenant, chacun sert de référence/pointeur! Un nombre fini de piles peuvent pas le faire.

    De ce que je vois dans les journaux/code, les algorithmes utilisent cette propriété de listes liées à conserver les références.

    Edit: je suis en se référant uniquement aux 2 et 3 de liste liée à des algorithmes de faire usage de cette propriété de listes liées, comme je l'ai lu en premier (ils ont regardé plus simple). Ce n'est pas là pour montrer qu'ils sont ou ne sont pas applicables, juste pour expliquer que les listes liées ne sont pas nécessairement identiques. Je vais vous lire l'un avec 6 quand je suis libre. @Welbog: Merci pour la correction.

    La paresse peut également simuler le pointeur de la fonctionnalité de la même façon.

    À l'aide de liste liée résout un problème différent. Cette stratégie peut être utilisée pour mettre en œuvre en temps réel les files d'attente en Lisp (Ou au moins Lisps, qui insistent sur la construction de tout, de listes liées): reportez-vous à "Temps Réel de la File d'attente des Opérations dans le plus Pur Lisp" (liés à travers antti.huima de liens). C'est aussi une belle façon de concevoir immuable listes de O(1) temps de fonctionnement et partagée (immuable) des structures.

    • Je ne peux pas parler pour les autres algorithmes dans antti réponse, mais les six-pile constante de temps de la solution (eecs.usma.edu/webs/people/okasaki/jfp95/queue.hm.sml) ne pas utiliser cette propriété de listes, comme je l'ai re-mise en oeuvre en Java à l'aide de java.util.Stack objets. Le seul endroit où cette fonction est utilisée est une optimisation qui permet immuable piles à être "doublé" en temps constant, qui de base Java piles ne peuvent pas le faire (mais qui peut être mis en œuvre en Java), car ils sont mutables structures.
    • Si c'est une optimisation qui n'est pas de réduire la complexité de calcul, il ne devrait pas influer sur la conclusion. Heureux d'avoir enfin une solution, maintenant pour le vérifier: Mais je n'aime pas la lecture de LMS. L'esprit de partage de votre code java? (:
    • Ce n'est pas une solution définitive, car il utilise six piles au lieu de trois, malheureusement. Toutefois, il pourrait être possible de prouver que les six piles est une solution minimale...
    • Pouvez-vous partager votre 6 de la pile de la mise en œuvre? 🙂 Ce serait cool de le voir 🙂
    InformationsquelleAutor Dingfeng Quek
  5. 1

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

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

    Ajout est O(1) et la suppression est O(1) si le côté que vous souhaitez utiliser dans n'est pas vide et O(n) autrement (split l'autre pile en deux).

    Le truc, c'est de voir que le O(n) opération ne se fait que tous les O(n) le temps (si vous split, par exemple, en moitiés). Par conséquent, le temps moyen d'une opération est O(1)+O(n)/O(n) = O(1).

    Bien que cela puisse couture comme un problème, si vous êtes en utilisant un langage impératif avec un tableau en fonction de la pile (le plus rapide), vous allez avoir seulement amorti de la constante de temps de toute façon.

    • Quant à la question de départ: le Fractionnement d'une pile nécessite en réalité un extra intermédiaire de la pile. Cela explique peut-être pourquoi votre tâche comprend trois piles.
    InformationsquelleAutor Thomas Ahle