Ein Stapel, zwei Warteschlangen

59

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.

MS Dousti
quelle
2
Ich vermute, dass Sie nur eine begrenzte Menge an Speicherplatz außer den beiden Warteschlangen (O (1) oder O (log n)) verwenden können. Klingt für mich unmöglich, da wir die Reihenfolge eines langen Eingabestreams nicht umkehren können. Aber dies ist natürlich kein Beweis, es sei denn, es kann eine strenge Behauptung aufgestellt werden.
Tsuyoshi Ito
@ Tsuyoshi: Sie haben Recht mit der Annahme, dass der Speicherplatz begrenzt ist. Und ja, das war es, was ich zu diesem (hartnäckigen) TA gesagt habe, aber er lehnte ab :(
MS Dousti 30.10.10
2
@Tsuyoshi: Ich glaube nicht, dass Sie generell von einer Begrenzung des Speicherplatzes ausgehen müssen. Sie müssen lediglich davon ausgehen, dass Sie die Objekte, die vom Stapel verschoben und abgelegt wurden, nicht an einem anderen Ort als den beiden Warteschlangen (und wahrscheinlich auch nicht dort) speichern dürfen eine konstante Anzahl von Variablen).
Kaveh
@SadeqDousti Meiner Meinung nach wäre dies nur möglich, wenn Sie eine Linked-List-Implementierung einer Warteschlange verwenden und einige Zeiger verwenden, um immer auf die Spitze des "Stapels" zu zeigen
Charles Addis
2
Es hört sich so an, als hätte der TA eigentlich sagen wollen "Implementiere eine Warteschlange mit zwei Stapeln", was tatsächlich genau in "O (1) Amortized Time" möglich ist.
Thomas Ahle

Antworten:

45

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.

David Eppstein
quelle
4
+1 für exzellente Referenzen. Es gibt jedoch einige technische Aspekte: Einige der Artikel, wie der erste, betrachten nicht das Problem, einen Stapel mit zwei Warteschlangen zu simulieren (so viel ich aus dem Abstract sagen kann). Andere betrachten die Worst-Case-Analyse, nicht die fortgeführten Anschaffungskosten.
MS Dousti 30.10.10
13

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(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(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(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.fichrstsecOndfichrstsecOnd

  • Das Drücken erfolgt durch einfaches Aufrufen des Parameters auf .fichrst
  • 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 efichrstsecOndfichrstsecOndfichrstfichrstsecOnd 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ücktO(1)fichrstsecOndO(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 dfichrstsecOndfichrstsecOnd 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 mitfichrstsecOndfichrstsecOndsecOndfichrst .secOnd

  • Das Drücken erfolgt weiterhin durch einfaches Aufrufen des Parameters auf .fichrst
  • 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 | < fichrstsecOndfichrstwir einfach dequeuefirstund das Ergebnis zurück. Andernfalls wir appendsecondauffirst, swapfirstundsecond, dequeuesecondund das Ergebnis zurück.|fichrst|<|secOnd|fichrstsecOndfichrstfichrstsecOndsecOnd

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(n)Und mische dann wirfirstin Stapelordnung inO(|first|)=O(|fichrst|<|secOnd|fichrstzeit. Wenn| first| O(|fichrst|)=O(n), dann müssen wir mindestensgehabt haben|fichrst||secOnd| ruft nach Push. Daher können wir diesen Fall nur alle treffenn Anrufe zu Push and Pop. Die tatsächliche Laufzeit für diesen Fall istO(n), die amortisierte Zeit ist alsoO( n)nO(n).O(nn)=O(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(n)fichrst

Alex ten Brink
quelle
Ich habe die ersten Absätze so bearbeitet, dass meine Antwort als tatsächliche Antwort auf die Frage formuliert ist.
Alex ten Brink
6
Sie verwenden ein Array (Umkehrer) zum Umkehren! Ich glaube nicht, dass du das darfst.
Kaveh
Zwar verwende ich zusätzlichen Speicherplatz beim Ausführen der Methoden, aber ich dachte, das wäre zulässig: Wenn Sie eine Warteschlange mit zwei Stapeln auf einfache Weise implementieren möchten , müssen Sie einen der Stapel an einer Stelle umkehren und so weit wie möglich Ich weiß, dass Sie dafür zusätzlichen Speicherplatz benötigen. Da diese Frage ähnlich ist, habe ich angenommen, dass die Verwendung von zusätzlichem Speicherplatz während der Ausführung einer Methode zulässig ist, solange Sie keinen zusätzlichen Speicherplatz zwischen Methodenaufrufen verwenden.
Alex ten Brink
6
"Wenn Sie eine Warteschlange mit zwei Stapeln auf einfache Weise implementieren möchten, müssen Sie einen der Stapel an einer Stelle umkehren, und soweit ich weiß, benötigen Sie dafür zusätzlichen Platz." Es gibt eine Möglichkeit, die amortisierten Kosten von Enqueue auf 3 und die amortisierten Kosten von Dequeue auf 1 (dh beide O (1)) mit einer Speicherzelle und zwei Stapeln zu bringen. Der schwierige Teil ist wirklich der Beweis, nicht das Design des Algorithmus.
Aaron Sterling
Nachdem ich noch etwas darüber nachgedacht habe, merke ich, dass ich tatsächlich betrüge und mein vorheriger Kommentar in der Tat falsch ist. Ich habe einen Weg gefunden, dies zu korrigieren: Ich habe mir zwei Algorithmen ausgedacht, die die gleichen Laufzeiten wie die beiden oben genannten haben (obwohl Push jetzt lange dauert und Pop jetzt in konstanter Zeit ausgeführt wird), ohne zusätzlichen Platz zu verbrauchen. Ich werde eine neue Antwort posten, sobald ich alles aufgeschrieben habe.
Alex ten Brink
12

Nach einigen Kommentaren zu meiner vorherigen Antwort wurde mir klar, dass ich mehr oder weniger betrogen habe: Ich habe zusätzlichen Platz ( O(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(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 sfirstsecondfirstsecondfirstsecond wird immer höchstens die Quadratwurzel von s e c o n d sein .firstsecond

  • 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 .firstfirstfirst
  • 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 efirstsecondsecondfirstfirstsecondfirst .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.firstfirstsecond

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(n)dann nimmt PushO(|first|<|second|zeit. Wenn| first| O(n)|first||second|O(n)firstO(n)O(nn)=O(n)

Alex ten Brink
quelle
Informationen zum Löschen einer Antwort finden Sie unter meta.cstheory.stackexchange.com/q/386/873 .
MS Dousti
Ich kann die Zeile nicht verstehen first.Enqueue(first.Dequeue()). Hast du etwas falsch geschrieben?
MS Dousti
Danke für den Link, ich habe meine ursprüngliche Antwort entsprechend aktualisiert. Zweitens habe ich meinem Code viele Kommentare hinzugefügt, die beschreiben, was während der Ausführung meines Algorithmus vor sich geht. Ich hoffe, dass dies Verwirrung beseitigt.
Alex ten Brink
Für mich war der Algorithmus vor der Bearbeitung besser lesbar und verständlicher.
Kaveh
9

Θ(N)

NNNNN

PUSHN(PUSHNPOPN)N

NN/2

N

N/2N/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.

N/22N

N/22NNNN/23NΩ(N)

Shaun Harker
quelle
Jack hat dies so bearbeitet, dass die Anzahl der Runden (Exponent in Klammern) beträgtNN
nQ.1N/2Q.22nn4:1+2++n+n2n
Anscheinend widerspricht Peters Antwort dieser Untergrenze?
Joe
PUSHNPOPNO(N)
O(N)
6

O(lgn)pushpOppOpO(lgn)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 ...

Peter Boothe
quelle
Argh! Ich hätte nach einer aktualisierten oder verwandten Frage suchen sollen. Die Papiere, auf die Sie in Ihrer früheren Antwort verwiesen haben, stellten eine Beziehung zwischen k Stapeln und k + 1 Stapeln auf. Führt dieser Trick dazu, dass die Leistung von k Warteschlangen zwischen k und k + 1 Stapeln liegt? Wenn ja, ist das eine nette Randbemerkung. Wie auch immer, danke, dass Sie mich mit Ihrer Antwort verknüpft haben, damit ich nicht zu viel Zeit damit verschwendete, dies für einen anderen Veranstaltungsort zu schreiben.
Peter Boothe
1

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).

Alpha
quelle
0

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.

  • EINB
  • 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.

Ross Snider
quelle
4
Sicherlich kann ich eine einzelne Warteschlange mit der gleichen Zeitkomplexität und ohne Komplikation verwenden und die Warteschlange im Wesentlichen als eine zirkuläre Liste mit einem zusätzlichen Warteschlangenelement behandeln, das den oberen Bereich des Stapels darstellt.
Dave Clarke
Sieht aus wie du kannst! Es scheint jedoch, dass mehr als eine klassische Warteschlange erforderlich ist, um einen Stapel auf diese Weise zu simulieren.
Ross Snider
0

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.

Oosterwal
quelle
Ihr zweiter Algorithmus ist hilfreich, um den involvierteren von Alex zu verstehen.
Hengxin
0

kΘ(n1/k)

k
n
O(1)

ichΘ(nich/k)Θ(nich/k)O(1)ich+1O(n1/k)ich-1Θ(n1/k) zulässt (oder wenn wir nur einen Stack haben und amortisierte Pop-Zeit zulassen).

mmΩ(mn1/k)O(n1/k)Ω(n1/k)O(n2/k)kO(n) , erhalten Sie je nach Bedarf (und größer).

Θ(Logn)

Dmytro Taranovsky
quelle
-3

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

Pradeepkumar
quelle
2
Haben Sie den Teil in der Frage nach der Amortisationszeit O (1) verpasst?
David Eppstein