Ein Stapel, zwei Warteschlangen

Hintergrund

Vor einigen Jahren, als ich ein Student war, erhielten wir eine Hausaufgabe über die amortisierte Analyse. Ich konnte eines der Probleme nicht lösen. Ich hatte es in comp.theory gefragt , aber es kam kein zufriedenstellendes Ergebnis zustande. Ich erinnere mich an den Kurs, in dem TA auf etwas bestand, das er nicht beweisen konnte, und sagte, er habe den Beweis vergessen, und ... [weißt du was].

Heute habe ich mich an das Problem erinnert. Ich war immer noch gespannt darauf, also hier ist es ...

Die Frage

Ist es möglich, einen Stack mit zwei Warteschlangen zu implementieren , sodass sowohl PUSH- als auch POP- Operationen in der amortisierten Zeit O (1) ausgeführt werden ? Wenn ja, können Sie mir sagen, wie?

Anmerkung: Die Situation ist recht einfach, wenn wir eine Warteschlange mit zwei Stapeln implementieren möchten (mit entsprechenden Operationen ENQUEUE & DEQUEUE ). Bitte beachten Sie den Unterschied.

PS: Das obige Problem ist nicht die Hausaufgabe selbst. Die Hausaufgaben erforderten keine Untergrenzen; Nur eine Implementierung und die Laufzeitanalyse.

Ich habe keine wirkliche Antwort, aber hier sind einige Beweise dafür, dass das Problem offen ist:

• Es wird in Ming Li, Luc Longpré und Paul MB Vitányi, "Die Macht der Warteschlange", Structures 1986, nicht erwähnt, in dem mehrere andere eng verwandte Simulationen betrachtet werden

• Es wird in Martin Hühne nicht erwähnt, "Über die Macht mehrerer Warteschlangen", Theor. Comp. Sci. 1993 ein Nachfolgepapier.

• Es ist nicht in Holger Petersen, "Stacks versus Deques", COCOON 2001 erwähnt.

• Burton Rosenberg, "Schnelle nicht deterministische Erkennung kontextfreier Sprachen mit zwei Warteschlangen", Inform. Proc. Lette. 1998 gibt einen O (n log n) Zwei-Warteschlangen-Algorithmus zum Erkennen einer CFL unter Verwendung von zwei Warteschlangen an. Ein nicht deterministischer Pushdown-Automat kann jedoch CFLs in linearer Zeit erkennen. Wenn es also eine Simulation eines Stacks mit zwei Warteschlangen gegeben hätte, die schneller als O (log n) pro Operation sind, hätten Rosenberg und seine Schiedsrichter davon wissen müssen.

Die Antwort unten lautet "Betrug", da die Operationen selbst zwar keinen Abstand zwischen den Operationen belegen, aber mehr als Leerzeichen verwenden können. An anderer Stelle in diesem Thread finden Sie eine Antwort, bei der dieses Problem nicht auftritt.$O(1)$

Obwohl ich keine Antwort auf Ihre genaue Frage habe, habe ich einen Algorithmus gefunden, der in Zeit anstelle vonO(n). Ich glaube, das ist eng, obwohl ich keinen Beweis habe. Wenn überhaupt, zeigt der Algorithmus, dass der Versuch, eine Untergrenze vonO(n)zu beweisen,vergeblich ist. Daher kann er bei der Beantwortung Ihrer Frage hilfreich sein.$O(\sqrt{n})$$O(n)$$O(n)$

Ich präsentiere zwei Algorithmen, der erste ist ein einfacher Algorithmus mit einer Laufzeit für Pop und der zweite mit einem O ( $O(n)$Laufzeit für Pop. Ich beschreibe den ersten hauptsächlich wegen seiner Einfachheit, damit der zweite leichter zu verstehen ist.$O(\sqrt{n})$

Um genauer zu sein: Der erste verwendet keinen zusätzlichen Platz, hat einen Worst-Case- (und amortisierten) Push und einen O ( n ) Worst-Case- (und amortisierten) Pop, aber das Worst-Case-Verhalten wird nicht immer ausgelöst. Da es keinen zusätzlichen Platz außerhalb der beiden Warteschlangen beansprucht, ist es etwas "besser" als die von Ross Snider angebotene Lösung.$O(1)$$O(n)$

Die zweite verwendet ein einzelnes ganzzahliges Feld (also zusätzliches Leerzeichen), hat einen O ( 1 ) Worst Case (und amortisiert) Push und einen O ( $O(1)$$O(1)$Pop abgeschrieben. Die Laufzeit ist daher erheblich besser als die des "einfachen" Ansatzes, benötigt jedoch zusätzlichen Platz.$O(\sqrt{n})$

Der erste Algorithmus

Wir haben zwei Warteschlangen: Warteschlange und Warteschlangen s e c o n d . f i r s t wird unsere 'Push - Warteschlange' sein, während s e c o n d die Warteschlange bereits in 'Stapelordnung' sein wird.$first$$second$$first$$second$

• Das Drücken erfolgt durch einfaches Aufrufen des Parameters auf .$first$
• Das Poppen wird wie folgt durchgeführt. Wenn ist leer, wir einfach dequeue s e c o n d und das Ergebnis zurück. Andernfalls kehren wir f i r s t , hängen alle von s e c o n d bis f i r s t und Swap f i r s t und s e c o n d . Wir haben dann dequeue s $first$$second$$first$$second$$first$$first$$second$ und gib das Ergebnis der Entschlüsselung zurück.$second$

C # -Code für den ersten Algorithmus

Dies könnte durchaus lesbar sein, auch wenn Sie noch nie C # gesehen haben. Wenn Sie nicht wissen, was Generika sind, ersetzen Sie einfach alle Instanzen von 'T' durch 'string' in Ihrem Kopf, um einen Stapel von Strings zu erhalten.

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

Analyse

Offensichtlich funktioniert Push in Zeit. Pop kann alles im Innern berührt f i r s t und s e c o n d eine konstante Menge an Zeit, so haben wir O ( n ) im schlechtesten Fall. Der Algorithmus zeigt dieses Verhalten (zum Beispiel), wenn man n drückt$O(1)$$first$$second$$O(n)$$n$ Elemente auf den Stapel und dann wiederholt nacheinander einen einzigen Push- und einen einzelnen Pop-Vorgang durchführt.

Der zweite Algorithmus

Wir haben zwei Warteschlangen: Warteschlange und Warteschlangen s e c o n d . f i r s t wird unsere 'Push - Warteschlange' sein, während s e c o n $first$$second$$first$$second$ die Warteschlange bereits in 'Stapelordnung' sein wird.

Dies ist eine angepasste Version des ersten Algorithmus, bei der der Inhalt von nicht sofort in s e c o n d 'gemischt' wird . Stattdessen, wenn f i r s t eine ausreichend kleine Anzahl von Elementen enthält im Vergleich zu s e c o n d (nämlich der Quadratwurzel der Anzahl der Elemente in s e c o n d ), reorganisieren wir nur f i r s t in Stapelreihenfolge und verschmelze es nicht mit$first$$second$$first$$second$$second$$first$ .$second$

• Das Drücken erfolgt weiterhin durch einfaches Aufrufen des Parameters auf .$first$
• Das Poppen wird wie folgt durchgeführt. Wenn ist leer, wir einfach dequeue s e c o n d und das Ergebnis zurück. Andernfalls reorganisieren wir den Inhalt von f i r s t , so dass sie in Stapel Ordnung sind. Wenn | f i r s t | < $first$$second$$first$wir einfach dequeuefirstund das Ergebnis zurück. Andernfalls wir appendsecondauffirst, swapfirstundsecond, dequeuesecondund das Ergebnis zurück.$|first| < \sqrt{|second|}$$first$$second$$first$$first$$second$$second$

C # -Code für den ersten Algorithmus

Dies könnte durchaus lesbar sein, auch wenn Sie noch nie C # gesehen haben. Wenn Sie nicht wissen, was Generika sind, ersetzen Sie einfach alle Instanzen von 'T' durch 'string' in Ihrem Kopf, um einen Stapel von Strings zu erhalten.

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

Analyse

Offensichtlich funktioniert Push in Zeit.$O(1)$

Pop arbeitet in Amortisierte Zeit Es gibt zwei Fälle: if| first| <$O(\sqrt{n})$Und mische dann wirfirstin Stapelordnung inO(|first|)=O($|first| < \sqrt{|second|}$$first$zeit. Wenn| first| ≥$O(|first|) = O(\sqrt{n})$, dann müssen wir mindestens√gehabt haben$|first| \geq \sqrt{|second|}$ ruft nach Push. Daher können wir diesen Fall nur alle √ treffen$\sqrt{n}$ Anrufe zu Push and Pop. Die tatsächliche Laufzeit für diesen Fall istO(n), die amortisierte Zeit ist alsoO($\sqrt{n}$$O(n)$.$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

Schlussbemerkung

Es ist möglich, die zusätzliche Variable zu eliminieren, um Pop zu einem Betrieb, indem Pop reorganisiertfirstbei jedem Aufruf anstelle von Pushdie ganzen Arbeit.$O(\sqrt{n})$$first$

Nach einigen Kommentaren zu meiner vorherigen Antwort wurde mir klar, dass ich mehr oder weniger betrogen habe: Ich habe zusätzlichen Platz ( $O(\sqrt{n})$ zusätzlicher Platz im zweiten Algorithmus) während der Ausführung meiner Pop-Methode.

Der folgende Algorithmus verwendet keinen zusätzlichen Abstand zwischen Methoden und nur zusätzlichen Abstand während der Ausführung von Push und Pop. Push hat ein O ( $O(1)$Laufzeit abgeschrieben und Pop hat einO(1$O(\sqrt{n})$$O(1)$ Worst-Case-Laufzeit (und amortisierte Laufzeit).

Hinweis für Moderatoren: Ich bin mir nicht ganz sicher, ob meine Entscheidung, eine separate Antwort zu erstellen, richtig ist. Ich dachte, ich sollte meine ursprüngliche Antwort nicht löschen, da sie für die Frage immer noch relevant sein könnte.

Der Algorithmus

Wir haben zwei Warteschlangen: Warteschlange und Warteschlangen s e c o n d . f i r s t wird unsere 'Cache' sein, während s e c o n d unsere 'Lagerung' sein wird. Beide Warteschlangen werden immer in "Stapelreihenfolge" sein. f i r s t enthält die Elemente am oberen Rand des Stapels und s e c o n d enthält die Elemente am unteren Rand des Stapels. Die Größe von f i $first$$second$$first$$second$$first$$second$ wird immer höchstens die Quadratwurzel von s e c o n d sein .$first$$second$

• Push wird von ‚Einfügen‘ , um die Parameter zu Beginn der Warteschlange wie folgt durchgeführt: Wir enqueue um den Parameter und dann aus der Warteschlange entfernt und erneut enqueue alle anderen Elemente in f i r s t . Auf diese Weise endet der Parameter am Anfang von f i r s t .$first$$first$$first$
• Wenn größer ist als die Quadratwurzel wird s e c o n d , enqueue wir alle Elemente s e c o n d auf f i r s t eins nach dem anderen , und dann tauschen f i r s t und s e c o n d . Auf diese Weise ist die Elemente von F i r s t (die Spitze des Stapels) an der Spitze am Ende s $first$$second$$second$$first$$first$$second$$first$ .$second$
• Pop erfolgte durch Warteschlangenauflösungs - und Rückkehr des Ergebnisses , wenn f i r s t nicht leer ist, und ansonsten durch Warteschlangenauflösungs s e c o n d und die Rückkehr des Ergebnisses.$first$$first$$second$

C # -Code für den ersten Algorithmus

Dieser Code sollte gut lesbar sein, auch wenn Sie noch nie C # gesehen haben. Wenn Sie nicht wissen, was Generika sind, ersetzen Sie einfach alle Instanzen von 'T' durch 'string' in Ihrem Kopf, um einen Stapel von Strings zu erhalten.

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

Analyse

Offensichtlich arbeitet Pop im schlimmsten Fall in -Zeit.$O(1)$

Push funktioniert in Amortisierte Zeit Es gibt zwei Fälle: if| first| <$O(\sqrt{n})$dann nimmt PushO($|first| < \sqrt{|second|}$zeit. Wenn| first| ≥$O(\sqrt{n})$$|first| \geq \sqrt{|second|}$$O(n)$$first$$O(\sqrt{n})$$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

$\Theta(\sqrt{N})$

$N$$\sqrt{N}$$\sqrt{N}$$\sqrt{N}$$\sqrt{N}$

$PUSH^N (PUSH^{\sqrt{N}} POP^{\sqrt{N}})^{\sqrt{N}}$

$N$$N/2$

$\sqrt{N}$

$N/2$$N/2$ Warteschlangenoperationen anfallen müssen, um schließlich auch nur ein einziges Element abzurufen, das wir ENQUEUE und später aus dieser größeren Warteschlange DEQUEUE müssen.

$\sqrt{N}/2$$2\sqrt{N}$

$N/2$$2\sqrt{N}$$\sqrt{N}$$N\sqrt{N}/2$$3N$$\Omega(\sqrt{N})$

$O(\lg n)$$push$$pop$$pop$$O(\lg n)$$pop$ angefordert und die Ausgabewarteschlange leer ist, führen Sie eine Folge perfekter Mischvorgänge durch, um die Eingabewarteschlange umzukehren und in der Ausgabewarteschlange zu speichern.

$O(1)$

Soweit ich weiß, ist dies eine neue Idee ...

Ohne zusätzlichen Speicherplatz zu belegen, möglicherweise eine priorisierte Warteschlange verwenden und jeden neuen Push zwingen, dieser eine höhere Priorität als der vorherigen zuzuweisen? Wäre trotzdem nicht O (1).

Ich kann die Warteschlangen nicht dazu bringen, einen Stack in amortisierter konstanter Zeit zu implementieren. Ich kann mir jedoch eine Möglichkeit vorstellen, zwei Warteschlangen zum Implementieren eines Stacks im schlimmsten Fall in linearer Zeit zu erstellen.

• $A$$B$
• Bei jeder Push-Operation wird das Bit umgedreht und das Element in die Warteschlange eingefügt, die das Bit jetzt abgrenzt. Pop alles aus der anderen Warteschlange und schieben Sie es in die aktuelle Warteschlange.
• Eine Pop-Operation entfernt die Vorderseite der aktuellen Warteschlange und berührt das externe Statusbit nicht.

Natürlich können wir einen weiteren externen Status hinzufügen, der uns sagt, ob die letzte Operation ein Push oder ein Pop war. Wir können die Verschiebung aller Vorgänge von einer Warteschlange in die andere verzögern, bis wir zwei Push-Vorgänge hintereinander erhalten. Dies macht auch die Pop-Operation etwas komplizierter. Dies gibt uns O (1) amortisierte Komplexität für die Pop-Operation. Push bleibt leider linear.

All dies funktioniert, da jedes Mal, wenn eine Push-Operation ausgeführt wird, das neue Element an den Anfang einer leeren Warteschlange gestellt wird und die volle Warteschlange am hinteren Ende hinzugefügt wird, wodurch die Elemente effektiv umgekehrt werden.

Wenn Sie dauerhafte Operationen amortisieren möchten, müssen Sie wahrscheinlich etwas schlaueres tun.

Es gibt eine triviale Lösung, wenn Ihre Warteschlange Frontloading zulässt, das nur eine Warteschlange (oder genauer gesagt Deque) erfordert. Vielleicht ist dies die Art von Warteschlange, die der Kurs TA in der ursprünglichen Frage im Auge hatte?

Hier ist eine andere Lösung, ohne Frontloading zuzulassen:

Dieser Algorithmus erfordert zwei Warteschlangen und zwei Zeiger. Wir nennen sie Q1, Q2, primär und sekundär. Bei der Initialisierung sind Q1 und Q2 leer, Primärpunkte zu Q1 und Sekundärpunkte zu Q2.

Die PUSH-Operation ist trivial und besteht lediglich aus:

*primary.enqueue(value);

Die POP-Operation ist etwas komplizierter. Sie müssen alle Elemente außer dem letzten Element der primären Warteschlange in die sekundäre Warteschlange spoolen, die Zeiger austauschen und das letzte verbleibende Element aus der ursprünglichen Warteschlange zurückgeben:

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

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

Es wird keine Grenzüberprüfung durchgeführt, und es ist nicht O (1).

Während ich dies schreibe, sehe ich, dass dies mit einer einzelnen Warteschlange unter Verwendung einer for-Schleife anstelle einer while-Schleife erfolgen kann, wie dies Alex getan hat. In beiden Fällen ist die PUSH-Operation O (1) und die POP-Operation wird O (n).

Hier ist eine andere Lösung, die zwei Warteschlangen und einen Zeiger mit den Bezeichnungen Q1, Q2 und queue_p verwendet:

Bei der Initialisierung sind Q1 und Q2 leer und queue_p zeigt auf Q1.

Auch hier ist die PUSH-Operation trivial, erfordert jedoch einen zusätzlichen Schritt, um queue_p auf die andere Warteschlange zu verweisen:

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

Die POP-Operation ähnelt der vorherigen, aber jetzt müssen n / 2 Elemente in der Warteschlange gedreht werden:

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());

Die PUSH-Operation ist immer noch O (1), aber jetzt ist die POP-Operation O (n / 2).

Persönlich bevorzuge ich für dieses Problem die Idee, eine einfache, doppelte Warteschlange (Deque) zu implementieren und sie als Stack zu bezeichnen, wenn wir dies möchten.

$k$$Θ(n^{1/k})$

$k$
$n$
$O(1)$

$i$$Θ(n^{i/k})$$Θ(n^{i/k})$$O(1)$$i+1$$O(n^{1/k})$$i-1$$Θ(n^{1/k})$ zulässt (oder wenn wir nur einen Stack haben und amortisierte Pop-Zeit zulassen).

$m$$m$$Ω(mn^{1/k})$$o(n^{1/k})$$Ω(n^{1/k})$$o(n^{2/k})$$k$$o(n)$ , erhalten Sie je nach Bedarf (und größer).

$Θ(\log n)$

Ein Stapel kann unter Verwendung von zwei Warteschlangen implementiert werden, indem die zweite Warteschlange als Puffer verwendet wird. Wenn Elemente auf den Stapel verschoben werden, werden sie am Ende der Warteschlange hinzugefügt. Bei jedem Auftauchen eines Elements müssen die n - 1 Elemente der ersten Warteschlange in die zweite verschoben werden, während das verbleibende Element zurückgegeben wird. öffentliche Klasse QueueStack implementiert IStack {private IQueue q1 = new Queue (); private IQueue q2 = neue Queue (); öffentlicher nichtiger Push (E e) {q1.enqueue (e) // O (1)} öffentlicher 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; }}