Une pile, deux files d'attente

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.

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.

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(\sqrt{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(\sqrt{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(\sqrt{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 $first$$second$$first$$second$

• 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 $first$$second$s 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 $first$$second$$first$$first$$second$$second$

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 ) $O(1)$$first$$second$$O(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.$first$$second$$first$$second$

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 .$first$$second$$first$$second$$second$$first$$second$

• 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.$first$$second$$first$$|first| < \sqrt{|second|}$$first$$second$$first$$first$$second$$second$

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(\sqrt{n})$$|first| < \sqrt{|second|}$$first$$O(|first|) = O(\sqrt{n})$$|first| \geq \sqrt{|second|}$$\sqrt{n}$$\sqrt{n}$$O(n)$$O(\frac{n}{\sqrt{n}}) = O(\sqrt{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(\sqrt{n})$$first$

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(\sqrt{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(\sqrt{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 .$first$$second$$first$$second$$first$$second$$first$$second$

• 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 .$first$$first$$first$
• 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 .$first$$second$$second$$first$$first$$second$$first$$second$
• 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.$first$$first$$second$

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(\sqrt{n})$$|first| < \sqrt{|second|}$$O(\sqrt{n})$$|first| \geq \sqrt{|second|}$$O(n)$$first$$O(\sqrt{n})$$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

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.$\Theta(\sqrt{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:$N$$\sqrt{N}$$\sqrt{N}$$\sqrt{N}$$\sqrt{N}$

$PUSH^N (PUSH^{\sqrt{N}} POP^{\sqrt{N}})^{\sqrt{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.$N$$N/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:$\sqrt{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/2$$N/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.$\sqrt{N}/2$$2\sqrt{N}$

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/2$$2\sqrt{N}$$\sqrt{N}$$N\sqrt{N}/2$$3N$$\Omega(\sqrt{N})$

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(\lg n)$$push$$pop$$pop$$O(\lg n)$$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 ...

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.

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 .$A$$B$
• 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.

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.

$k$$Θ(n^{1/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$$Θ(n^{i/k})$$Θ(n^{i/k})$$O(1)$$i+1$$O(n^{1/k})$$i-1$$Θ(n^{1/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 $m$$m$$Ω(mn^{1/k})$$o(n^{1/k})$$Ω(n^{1/k})$$o(n^{2/k})$$k$$o(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.$Θ(\log n)$

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; }}