Une pile, deux files d'attente

60

Contexte

Il y a plusieurs années, lorsque j'étais étudiant de premier cycle, on nous a confié un devoir d'analyse en amortissement. J'ai été incapable de résoudre l'un des problèmes. Je l’avais demandé en théorie , mais aucun résultat satisfaisant n’a été obtenu. Je me souviens du cours TA a insisté sur quelque chose qu'il ne pouvait pas prouver, et a dit qu'il avait oublié la preuve, et ... [vous savez quoi].

Aujourd'hui, j'ai rappelé le problème. J'avais encore hâte de savoir, alors la voici ...

La question

Est-il possible d'implémenter une pile utilisant deux files d'attente , de sorte que les opérations PUSH et POP s'exécutent dans le temps amorti O (1) ? Si oui, pourriez-vous me dire comment?

Note: La situation est assez facile si nous voulons implémenter une file d’ attente avec deux piles (avec les opérations correspondantes ENQUEUE et DEQUEUE ). S'il vous plaît observer la différence.

PS: Le problème ci-dessus n’est pas le devoir à la maison. Les devoirs ne nécessitaient aucune limite inférieure; juste une implémentation et l'analyse du temps d'exécution.

MS Dousti
la source
2
Je suppose que vous ne pouvez utiliser qu'un espace limité autre que les deux files d'attente (O (1) ou O (log n)). Cela me semble impossible, car nous n'avons aucun moyen d'inverser l'ordre d'un long flux d'entrée. Mais bien sûr, ce n’est pas une preuve à moins de pouvoir en faire une réclamation rigoureuse….
Tsuyoshi Ito
@Tsuyoshi: Vous avez raison à propos de l'hypothèse d'espace limité. Et oui, c'est ce que j'ai dit à TA (obstiné), mais il a refusé :(
MS Dousti
2
@Tsuyoshi: Je ne pense pas que vous ayez à assumer une limite d'espace en général, vous devez seulement supposer que vous n'êtes pas autorisé à stocker les objets poussés et sortis de la pile à un endroit autre que les deux files d'attente (et probablement un nombre constant de variables).
Kaveh
@SadeqDousti À mon avis, cela ne serait possible que si vous utilisiez une implémentation de liste liée d'une liste chaînée et que vous utilisiez des pointeurs pour toujours pointer en haut de la "pile"
Charles Addis
2
Il semble que le TA ait effectivement voulu dire "Mettre en oeuvre une file d'attente à l'aide de deux piles", ce qui est en effet possible précisément dans "O (1) amortited time".
Thomas Ahle

Réponses:

45

Je n'ai pas de réponse réelle, mais voici quelques preuves que le problème est ouvert:

  • Ce n'est pas mentionné dans Ming Li, Luc Longpré et Paul MB Vitányi, "Le pouvoir de la file d'attente", Structures 1986, qui considère plusieurs autres simulations étroitement liées

  • Martin Hühne n’a pas mentionné "Sur le pouvoir de plusieurs files", Theor. Comp. Sci. 1993, un article de suivi.

  • Ce n'est pas mentionné dans Holger Petersen, "Stacks versus Deques", COCOON 2001.

  • Burton Rosenberg, "Reconnaissance rapide non déterministe de langages sans contexte utilisant deux files", Inform. Proc. Lett. 1998, donne un algorithme O (n log n) à deux files d’attente permettant de reconnaître toute CFL utilisant deux files d'attente. Mais un automate à pression non déterministe peut reconnaître les LFC en temps linéaire. Donc, s'il y avait une simulation d'une pile avec deux files d'attente plus rapidement que O (log n) par opération, Rosenberg et ses arbitres auraient dû être au courant.

David Eppstein
la source
4
+1 pour d'excellentes références. Il y a cependant quelques détails techniques: certains articles, comme le premier, ne considèrent pas le problème de la simulation d'une pile à l'aide de deux files d'attente (autant que je puisse en dire de manière abstraite). D'autres considèrent l'analyse du pire des cas, pas le coût amorti.
MS Dousti
13

La réponse ci-dessous est "tricher", en ce sens qu'elle n'utilise pas d'espace entre les opérations mais les opérations elles-mêmes peuvent utiliser plus que l' espace . Voir ailleurs dans ce fil pour une réponse qui n'a pas ce problème.O(1)

Bien que je n’aie pas de réponse à votre question exacte, j’ai trouvé un algorithme qui fonctionne en temps au lieu de . Je crois que c'est serré, bien que je n'ai pas de preuve. Si quelque chose se passe, l'algorithme montre qu'essayer de prouver une borne inférieure de est futile, cela pourrait donc aider à répondre à votre question.O(n)O(n)O(n)O(n)O(n)

Je présente deux algorithmes, le premier étant un algorithme simple avec un temps d'exécution pour Pop et le second avec un temps d'exécution pour Pop. Je décris le premier principalement en raison de sa simplicité, de sorte que le second est plus facile à comprendre.O ( O(n)O(n)

Pour être plus précis: le premier n’utilise pas d’espace supplémentaire, a un push pire (et amorti) et un pop (et amorti), mais le pire comportement n’est pas toujours déclenché. Dans la mesure où elle n'utilise pas d'espace supplémentaire au-delà des deux files d'attente, elle est légèrement "meilleure" que la solution proposée par Ross Snider.O ( n )O(1)O(n)

La seconde utilise un seul champ entier (donc espace supplémentaire), a un cas le plus défavorable (et amorti) et un amorti Pop. Son temps de fonctionnement est donc nettement meilleur que celui de l'approche «simple», mais il utilise encore un peu d'espace supplémentaire.O ( 1 ) O ( O(1)O(1)O(n)

Le premier algorithme

Nous avons deux files d'attente: file d'attente en et file d'attente . sera notre "file d'attente", le sera la file déjà en ordre de pile.s e c o n d f i r s t s e c o n dfirstsecondfirstsecond

  • Pousser se fait par enqueueing simplement le paramètre sur .first
  • Le saut est fait comme suit. Si est vide, nous retirons simplement les et renvoyons le résultat. Sinon, on inverse en , on ajoute tout le au et on échange les et . Nous retirons ensuite et renvoyons le résultat de la file d'attente.s e c o n dfirstseconds e c o n d f i r s t f i r s t s e c o n d s e c o n dfirstsecondfirstfirstsecondsecond

Code C # pour le premier algorithme

Cela pourrait être assez lisible, même si vous n’avez jamais vu C # auparavant. Si vous ne savez pas ce que sont les génériques, remplacez toutes les occurrences de «T» par «chaîne» dans votre esprit, pour une pile de chaînes.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            // Reverse first
            for (int i = 0; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();    
            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            // Append second to first
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());

            // Swap first and second
            Queue<T> temp = first; first = second; second = temp;

            return second.Dequeue();
        }
    }
}

Une analyse

De toute évidence, Push fonctionne dans le temps . Pop peut toucher tout ce qui est à l'intérieur en et en un nombre de fois constant, nous avons donc dans le pire des cas. L’algorithme présente ce comportement (par exemple) si l’on place éléments sur la pile, puis exécute de manière répétée une opération Push unique et une seule opération Pop successivement.f i r s t s e c o n d O ( n ) nO(1)firstsecondO(n)n

Le deuxième algorithme

Nous avons deux files d'attente: file d'attente en et file d'attente . sera notre "file d'attente", le sera la file déjà en ordre de pile.firstsecondfirstsecond

Il s'agit d'une version adaptée du premier algorithme, dans laquelle nous ne «brassons» pas immédiatement le contenu de à . Au lieu de cela, si contient un nombre suffisamment petit d’éléments par rapport à (à savoir la racine carrée du nombre d’éléments en ), nous ne le réorganisons qu’en dans l’ordre de pile et ne le fusionnons pas avec .firstsecondfirstsecondsecondfirstsecond

  • Pousser est toujours fait par enqueueing simplement le paramètre sur .first
  • Le saut est fait comme suit. Si est vide, nous retirons simplement les et renvoyons le résultat. Sinon, nous réorganisons le contenu de afin qu'il soit placé dans l'ordre de la pile. Si nous avons simplement dequeue et renvoie le résultat. Sinon, nous ajoutons le au , permutons le et le , retirons la et renvoyons le résultat.firstsecondfirst|first|<|second|firstsecondfirstfirstsecondsecond

Code C # pour le premier algorithme

Cela pourrait être assez lisible, même si vous n’avez jamais vu C # auparavant. Si vous ne savez pas ce que sont les génériques, remplacez toutes les occurrences de «T» par «chaîne» dans votre esprit, pour une pile de chaînes.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    int unsortedPart = 0;
    public void Push(T value) {
        unsortedPart++;
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            for (int i = nrOfItemsInFirst - unsortedPart - 1; i >= 0; i--)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - unsortedPart; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            unsortedPart = 0;
            if (first.Count * first.Count < second.Count)
                return first.Dequeue();
            else {
                while (second.Count > 0)
                    first.Enqueue(second.Dequeue());

                Queue<T> temp = first; first = second; second = temp;

                return second.Dequeue();
            }
        }
    }
}

Une analyse

De toute évidence, Push fonctionne dans le temps .O(1)

Pop fonctionne en temps amorti . Il y a deux cas: if , puis nous mélangeons d' dans l'ordre des piles dans le temps . Si , nous devons avoir reçu au moins appels Push. Par conséquent, nous ne pouvons frapper ce cas que tous les appels à Push et Pop. Le temps d'exécution réel pour ce cas est , le temps amorti est donc .O(n)|first|<|second|firstO(|first|)=O(n)|first||second|nnO(n)O(nn)=O(n)

Note finale

Il est possible d’éliminer la variable supplémentaire au prix de la transformation Pop en une opération , en ayant Pop réorganisé d’ à chaque appel au lieu de laisser Push effectuer tout le travail.O(n)first

Alex ten Brink
la source
J'ai édité les premiers paragraphes afin que ma réponse soit formulée comme une réponse réelle à la question.
Alex ten Brink
6
Vous utilisez un tableau (inverseur) pour inverser! Je ne pense pas que vous ayez le droit de faire ça.
Kaveh
Certes, j'utilise davantage d'espace lors de l'exécution des méthodes, mais je pensais que ce serait autorisé: si vous souhaitez implémenter une file d'attente à l' aide de deux piles de manière simple, vous devez inverser l'une des piles à un moment donné et autant que possible. Je sais que vous avez besoin d'espace supplémentaire pour le faire. C'est pourquoi, comme cette question est similaire, j'ai pensé qu'il serait permis d'utiliser de l'espace supplémentaire lors de l'exécution d'une méthode, à condition de ne pas utiliser d'espace supplémentaire entre les appels de méthode.
Alex ten Brink
6
"si vous voulez implémenter une file d'attente en utilisant deux piles de manière simple, vous devez inverser l'une des piles à un moment donné et, autant que je sache, vous avez besoin d'espace supplémentaire pour le faire" --- Vous ne le faites pas. Il existe un moyen de ramener le coût amorti de Enqueue à 3 et le coût amorti de Dequeue à 1 (c'est-à-dire à la fois O (1)) avec une cellule de mémoire et deux piles. La partie difficile est vraiment la preuve, pas la conception de l'algorithme.
Aaron Sterling
Après avoir réfléchi un peu plus, je me rends bien compte que je triche et que mon commentaire précédent est vraiment faux. J'ai trouvé un moyen de le corriger: j'ai imaginé deux algorithmes avec les mêmes temps d'exécution que les deux précédents (bien que Push prenne maintenant longtemps et que Pop se fasse maintenant à temps constant) sans utiliser d'espace supplémentaire du tout. Je posterai une nouvelle réponse une fois que je l'aurai tout écrit.
Alex ten Brink
12

Après quelques commentaires sur ma réponse précédente, il m'est apparu clairement que je trichais plus ou moins: j'ai utilisé un espace supplémentaire ( espace supplémentaire dans le deuxième algorithme) lors de l'exécution de ma méthode Pop.O(n)

L'algorithme suivant n'utilise aucun espace supplémentaire entre les méthodes et uniquement un espace supplémentaire lors de l'exécution de Push et Pop. Push a un temps d'exécution amorti et Pop a un temps d'exécution cas le plus défavorable (et amorti).O(1)O(n)O(1)

Note aux modérateurs: Je ne suis pas tout à fait sûr si ma décision d’en faire une réponse distincte est correcte. J'ai pensé que je ne devrais pas effacer ma réponse originale, car elle pourrait encore être pertinente pour la question.

L'algorithme

Nous avons deux files d'attente: file d'attente en et file d'attente . sera notre "cache", le sera notre "stockage" principal. Les deux files d'attente seront toujours dans "l'ordre des piles". contiendra les éléments au sommet de la pile et le contiendra les éléments au bas de la pile. La taille du sera toujours au plus la racine carrée du .firstsecondfirstsecondfirstsecondfirstsecond

  • Poussée se fait par « l' insertion » du paramètre au début de la file d' attente de la façon suivante: on Enqueue le paramètre à , puis dequeue et re-file d' attente le tous les autres éléments en . De cette façon, le paramètre se termine au début du .firstfirstfirst
  • Si devient plus grande que la racine carrée de , nous ENQUEUE tous les éléments du ONTO , un par un, puis échangeons et . De cette façon, les éléments du (le haut de la pile) se retrouvent en tête du .firstsecondsecondfirstfirstsecondfirstsecond
  • Le pop est fait en commençant d' par la file d'attente et en renvoyant le résultat si la n'est pas vide, sinon par la file d'attente en et en renvoyant le résultat.firstfirstsecond

Code C # pour le premier algorithme

Ce code devrait être assez lisible, même si vous n'avez jamais vu C # auparavant. Si vous ne savez pas ce que sont les génériques, remplacez toutes les occurrences de «T» par «chaîne» dans votre esprit, pour une pile de chaînes.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        // I'll explain what's happening in these comments. Assume we pushed
        // integers onto the stack in increasing order: ie, we pushed 1 first,
        // then 2, then 3 and so on.

        // Suppose our queues look like this:
        // first: in 5 6 out
        // second: in 1 2 3 4 out
        // Note they are both in stack order and first contains the top of
        // the stack.

        // Suppose value == 7:
        first.Enqueue(value);
        // first: in 7 5 6 out
        // second: in 1 2 3 4 out

        // We restore the stack order in first:
        for (int i = 0; i < first.Count - 1; i++)
            first.Enqueue(first.Dequeue());
        // first.Enqueue(first.Dequeue()); is executed twice for this example, the 
        // following happens:
        // first: in 6 7 5 out
        // second: in 1 2 3 4 out
        // first: in 5 6 7 out
        // second: in 1 2 3 4 out

        // first exeeded its capacity, so we merge first and second.
        if (first.Count * first.Count > second.Count) {
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());
            // first: in 4 5 6 7 out
            // second: in 1 2 3 out
            // first: in 3 4 5 6 7 out
            // second: in 1 2 out
            // first: in 2 3 4 5 6 7 out
            // second: in 1 out
            // first: in 1 2 3 4 5 6 7 out
            // second: in out

            Queue<T> temp = first; first = second; second = temp;
            // first: in out
            // second: in 1 2 3 4 5 6 7 out
        }
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else
            return first.Dequeue();
    }
}

Une analyse

De toute évidence, Pop fonctionne en temps dans le pire des cas.O(1)

Push fonctionne en temps amorti . Il y a deux cas: if alors Push prend un temps . Si puis appuyez sur prend temps, mais après cette opération sera vide. Il faudra un temps pour obtenir ce cas à nouveau. Le temps amorti est donc .O(n)|first|<|second|O(n)|first||second|O(n)firstO(n)O(nn)=O(n)

Alex ten Brink
la source
Pour supprimer une réponse, consultez la page meta.cstheory.stackexchange.com/q/386/873 .
MS Dousti
Je ne peux pas comprendre la ligne first.Enqueue(first.Dequeue()). Avez-vous mal tapé quelque chose?
MS Dousti
Merci pour le lien, j'ai mis à jour ma réponse originale en conséquence. Deuxièmement, j'ai ajouté beaucoup de commentaires à mon code décrivant ce qui se passe pendant l'exécution de mon algorithme. J'espère que cela dissipe toute confusion.
Alex ten Brink
pour moi, l'algorithme était plus lisible et plus facile à comprendre avant le montage.
Kaveh
9

Je prétends que nous avons un coût amorti par opération . L'algorithme d'Alex donne la limite supérieure. Pour prouver la limite inférieure, je donne une séquence dans le pire des cas de mouvements PUSH et POP.Θ(N)

La séquence la plus défavorable consiste en opérations PUSH, suivies des opérations PUSH et des opérations POP, suivies à nouveau des opérations PUSH et des opérations POP, etc. est:NNNNN

PUSHN(PUSHNPOPN)N

Considérez la situation après les opérations initiales de PUSH. Quel que soit le fonctionnement de l’algorithme, au moins une des files d’attente doit contenir au moins entrées.NN/2

Examinons maintenant la tâche consistant à traiter avec le (premier ensemble de) opérations PUSH et POP. Toute tactique algorithmique, quelle qu'elle soit, doit tomber dans l'un des deux cas suivants:N

Dans le premier cas, l'algorithme utilisera les deux files d'attente. La plus grande de ces files d'attente contient au moins entrées; nous devons donc encourir un coût d'au moins opérations de file d'attente afin de récupérer même un seul élément que nous ENQUEUONS et que nous devrons extraire ultérieurement de cette file d'attente plus longue.N/2N/2

Dans le second cas, l'algorithme n'utilise pas les deux files d'attente. Cela réduit le problème à la simulation d'une pile avec une seule file d'attente. Même si cette file d’attente est initialement vide, nous ne pouvons pas faire mieux que l’utiliser comme une liste circulaire avec accès séquentiel, et il semble évident que nous devons utiliser au moins opérations de file d’attente en moyenne pour chacun des éléments suivants: les opérations de pile.N/22N

Dans les deux cas, nous avons eu besoin d'au moins fois (opérations de file d'attente) pour pouvoir gérer opérations de pile . Comme nous pouvons répéter ce processus fois, nous avons besoin de fois pour traiter au total les opérations de pile , ce qui donne une limite inférieure de temps amorti par opération. .N/22NNNN/23NΩ(N)

Shaun Harker
la source
Jack a édité ceci pour que le nombre de tours (exposant sur les parenthèses) soit au lieu de comme je l’avais eu. C’est parce que ce que j’avais auparavant pour montrer que vous ne pouviez pas amortir la séquence entière était "overkill" et vous pouvez le voir uniquement à partir des itérations. Merci, Jack! NN
Shaun Harker
Qu'en est-il du mélange de ces deux cas? Par exemple, nous poussons les entrées alternativement dans (celui avec au moins entrées) et (l'autre file d'attente)? Je suppose que ce modèle coûte plus cher, mais comment en discuter? Et dans le second cas, je pense que le coût moyen (amorti) pour chacune des opérations de pile est au moins de . nQ1N/2Q22nn4:1+2++n+n2n
Hengxin
Apparemment, la réponse de Peter contredit cette limite inférieure?
Joe
@ Joe Je ne pense pas que la réponse de Peter contredit cette limite inférieure puisque les premiers N poussées ne sont jamais apparus dans cette séquence. Toute procédure de brassage nécessite au moins O (N) temps. Par conséquent, si elle doit avoir lieu à chaque "phase" (séquence des opérations ), nous avons encore ont amorti pour la phase. En particulier, un tel algorithme relève du "premier cas" dans mon analyse. PUSHNPOPNO(N)
Shaun Harker
@hengxin Votre commentaire m'a fait comprendre que je n'avais pas exprimé mon argument aussi clairement que je l'aurais souhaité. Je l'ai édité, donc maintenant il devrait être clair que le motif que vous proposez est couvert par le premier cas. L'argument est que si nous ENQUEUONS même un seul élément dans la plus grande file d'attente, nous devons obliger les opérations à le récupérer. O(N)
Shaun Harker
6

Vous pouvez obtenir un ralentissement (amorti) si, après plusieurs et aucun , lorsque vous voyez un vous effectuez une séquence de mélanges parfaits à l'aide des deux files d'attente. Il a été prouvé par Diaconis, Graham et Cantor dans "The Mathematics of Perfect Shuffles" en 1983 que, avec un mélange parfait pouvait être réorganisé dans n'importe quel ordre. Par conséquent, vous pouvez conserver une file d'attente en tant que "file d'attente d'entrée" et une file d'attente en tant que "file d'attente de sortie" (similaire au cas des deux piles), puis lorsqu'un - est demandé et que la file d'attente de sortie est vide, vous effectuez une séquence de shuffle pour inverser la file d’entrée et la stocker dans la file d’attente.O(lgn)pushpoppopO(lgn)pop

La seule question qui reste est de savoir si le schéma particulier de mélange parfait requis est suffisamment régulier pour ne pas nécessiter plus que mémoire.O(1)

Pour autant que je sache, c'est une nouvelle idée ...

Peter Boothe
la source
Argh! J'aurais dû chercher une question mise à jour ou liée. Les documents auxquels vous avez lié dans votre réponse précédente établissaient une relation entre k piles et k +1 piles. Est-ce que cette astuce finit par placer la puissance de k files d'attente entre k et k + 1 piles? Si c'est le cas, c'est une sorte de sidenote soigné. Quoi qu'il en soit, merci de m'avoir lié à votre réponse afin que je ne perde pas trop de temps à l'écrire pour un autre lieu.
Peter Boothe
1

Sans utiliser d'espace supplémentaire, peut-être en utilisant une file d'attente priorisée et en forçant chaque nouvelle poussée à lui donner une priorité plus grande que la précédente? Ne serait toujours pas O (1) cependant.

Alpha
la source
0

Je ne peux pas obtenir les files d'attente pour implémenter une pile en temps constant amorti. Cependant, je peux penser à un moyen de faire en sorte que deux files d'attente implémentent une pile au pire moment linéaire.

  • En utilisant un bit de données externe, conservez un enregistrement de la dernière file d'attente utilisée, la file d'attente gauche ou la file d'attente droite .AB
  • Chaque fois qu'il y a une opération push, retournez le bit et insérez l'élément dans la file d'attente qu'il délimite. Déposez tout ce qui se trouve dans l'autre file et placez-le dans la file actuelle.
  • Une opération contextuelle enlève l'avant de la file actuelle et ne touche pas le bit d'état externe.

Bien sûr, nous pouvons ajouter un autre bit d'état externe qui nous dit si la dernière opération a été une poussée ou un pop. Nous pouvons retarder le transfert de tout d'une file d'attente à l'autre jusqu'à ce que nous ayons deux opérations push consécutives. Cela rend également l'opération pop légèrement plus compliquée. Cela nous donne une complexité amortie de O (1) pour l'opération pop. Malheureusement, la poussée reste linéaire.

Tout cela fonctionne car chaque fois qu'une opération push est effectuée, le nouvel élément est placé en tête d'une file vide et la file d'attente complète est ajoutée à la fin de celui-ci, inversant ainsi les éléments.

Si vous souhaitez obtenir des opérations amorties à temps constant, vous devrez probablement faire quelque chose de plus intelligent.

Ross Snider
la source
4
Bien sûr, je peux utiliser une seule file d'attente avec la même complexité de temps dans les cas les plus critiques et sans complication, la traitant essentiellement comme une liste circulaire avec un élément de file d'attente supplémentaire représentant le haut de la pile.
Dave Clarke
On dirait que tu peux! Cependant, il semble que plus d’une file d’attente classique soit nécessaire pour simuler une pile de cette façon.
Ross Snider
0

Il existe une solution triviale, si votre file d'attente autorise le chargement en amont, qui ne nécessite qu'une seule file d'attente (ou, plus précisément, deque.) Peut-être est-ce le type de file d'attente que le cours du TA avait à l'esprit dans la question initiale?

Sans permettre le chargement frontal, voici une autre solution:

Cet algorithme nécessite deux files d'attente et deux pointeurs. Nous les appellerons respectivement Q1, Q2, primaire et secondaire. Lors de l'initialisation, Q1 et Q2 sont vides, les points principaux sont Q1 et les points secondaires sont Q2.

L'opération PUSH est triviale, elle consiste simplement:

*primary.enqueue(value);

L’opération POP est légèrement plus impliquée; il faut spouler tout le dernier élément de la file primaire, sauf le dernier, sur la deuxième file, échanger les pointeurs et renvoyer le dernier élément restant de la file initiale:

while(*primary.size() > 1)
{
    *secondary.enqueue(*primary.dequeue());
}

swap(primary, secondary);
return(*secondary.dequeue());

Aucune vérification des limites n'est effectuée et ce n'est pas O (1).

Pendant que je tape ceci, je vois que cela pourrait être fait avec une seule file d'attente utilisant une boucle for à la place d'une boucle while, comme Alex l'a fait. Dans les deux cas, l’opération PUSH est O (1) et l’opération POP devient O (n).


Voici une autre solution utilisant deux files d'attente et un pointeur, appelés respectivement Q1, Q2 et queue_p:

Lors de l'initialisation, Q1 et Q2 sont vides et queue_p pointe sur Q1.

Là encore, l'opération PUSH est simple, mais nécessite une étape supplémentaire consistant à pointer queue_p sur l'autre file d'attente:

*queue_p.enqueue(value);
queue_p = (queue_p == &Q1) ? &Q2 : &Q1;

L’opération POP est similaire à celle d’avant, mais il faut maintenant faire pivoter n / 2 éléments dans la file d’attente:

queue_p = (queue_p == &Q1) ? &Q2 : &Q1;
for(i=0, i<(*queue_p.size()-1, i++)
{
    *queue_p.enqueue(*queue_p.dequeue());
}
return(*queue_p.dequeue());

L'opération PUSH est toujours O (1), mais maintenant l'opération POP est O (n / 2).

Personnellement, pour ce problème, je préfère l’idée de mettre en oeuvre une seule file d’attente à deux extrémités (deque) et de l’appeler pile lorsque nous le voulons.

Oosterwal
la source
Votre deuxième algorithme est utile pour comprendre le plus impliqué d’Alex.
Hengxin
0

kΘ(n1/k)

k
n
O(1)

Dans une direction (c. -à- limite supérieure), la ème file d' attente aura taille , et en même temps que les files d' attente inférieures de numéro, aura la plus récente éléments par pile (sauf si une pile a moins d'éléments; les éléments sont uniquement déplacés et non copiés). Nous maintenons cette contrainte en déplaçant des éléments entre les files d'attente, en effectuant les mouvements en bloc de manière à obtenir un temps par élément déplacé vers la file d'attente et vers la file d'attente . Chaque article est annoté par l'identité de sa pile et sa hauteur dans la pile; ceci n'est pas nécessaire si nous permettons à push d'être (ou si nous avons juste une pile et permettons un temps de saut amorti).iΘ(ni/k)Θ(ni/k)O(1)i+1O(n1/k)i1Θ(n1/k)

Dans l’autre direction (c’est-à-dire la limite inférieure), nous pouvons continuer à ajouter des éléments jusqu’à ce que, pour certains , le ième élément le plus récent soit à la fin de chaque file le contenant, puis nous le demandons et répétons. Supposons que cela n'arrive pas assez. Ensuite, un nouvel élément doit généralement être ajouté à une file d'attente de taille . Pour conserver cette taille de file d'attente, les éléments doivent être déplacés avec la fréquence vers une autre file d'attente, dont la taille doit généralement être pour permettre une extraction suffisamment rapide des éléments après le déplacement. . En répétant cet argument, nous obtenons files d'attente d'une taille totale de (et en croissance), selon les besoins.m Ω ( m n 1 / k ) o ( n 1 / k ) Ω ( n 1 / k ) o ( n 2 / k ) k o ( n )mmΩ(mn1/k)o(n1/k)Ω(n1/k)o(n2/k)ko(n)

De plus, si une pile doit être vidée en une seule fois (avant de commencer à ajouter des éléments à nouveau), la performance optimale après amortissement est de (une pile utilisant deux files d'attente ou plus); cette performance peut être obtenue en utilisant (essentiellement) le tri par fusion.Θ(logn)

Dmytro Taranovsky
la source
-3

Une pile peut être mise en œuvre en utilisant deux files d'attente en utilisant la seconde file d'attente comme exemple. Lorsque des éléments sont placés dans la pile, ils sont ajoutés à la fin de la file d'attente. Chaque fois qu'un élément est affiché, les n - 1 éléments de la première file d'attente doivent être déplacés vers le second tandis que l'élément restant est renvoyé. classe publique QueueStack implemen ts IStack {IQueue privée q1 = new Queue (); IQueue privée q2 = nouvelle file d'attente (); public vide push (E e) {q1.enqueue (e) // O (1)} public E pop (E e) {while (1 <q1.size ()) // O (n) {q2.enqueue ( q1.dequeue ()); } sw apQueues (); return q2.dequeue (); } p rivate void swapQueues () {IQueue Q = q2; q2 = q1; q1 = Q; }}

Pradeepkumar
la source
2
Avez-vous oublié la partie de la question sur le temps amorti O (1)?
David Eppstein