Was bringt es, einen Stack mit zwei Warteschlangen zu implementieren?

34

Ich habe folgende Hausaufgabenfrage:

Implementieren Sie die Stack-Methoden push (x) und pop () in zwei Warteschlangen.

Das kommt mir merkwürdig vor, weil:

  • Ein Stack ist eine (LIFO-) Warteschlange
  • Ich verstehe nicht, warum Sie zwei Warteschlangen benötigen würden, um es zu implementieren

Ich habe gesucht:

und fand ein paar Lösungen. Dies ist, was ich am Ende mit:

public class Stack<T> {
    LinkedList<T> q1 = new LinkedList<T>();
    LinkedList<T> q2 = new LinkedList<T>();

    public void push(T t) {
        q1.addFirst(t);
    }

    public T pop() {
        if (q1.isEmpty()) {
            throw new RuntimeException(
                "Can't pop from an empty stack!");
        }

        while(q1.size() > 1) {
            q2.addFirst( q1.removeLast() );
        }

        T popped = q1.pop();

        LinkedList<T> tempQ = q1;
        q1 = q2;
        q2 = tempQ;

        return popped;
    }
}

Aber ich verstehe nicht, was der Vorteil gegenüber der Verwendung einer einzelnen Warteschlange ist. Die Version mit zwei Warteschlangen scheint sinnlos kompliziert zu sein.

Angenommen, wir möchten, dass Pushs die effizientere der beiden sind (wie ich es oben getan habe), pushdass sie gleich bleiben und popdass wir einfach bis zum letzten Element iterieren und es zurückgeben müssen. In beiden Fällen pushwäre das O(1)und das popwäre O(n); aber die Single Queue-Version wäre drastisch einfacher. Es sollte nur eine einzige for-Schleife erforderlich sein.

Vermisse ich etwas? Einsicht hier wäre dankbar.

Karzigenat
quelle
17
Eine Warteschlange bezieht sich normalerweise auf eine FIFO-Struktur, während der Stapel eine LIFO-Struktur ist. Die Schnittstelle für LinkedList in Java ist die einer Deque (Double-Ended-Queue), die sowohl FIFO- als auch LIFO-Zugriff ermöglicht. Versuchen Sie, die Programmierung auf die Warteschlangenschnittstelle und nicht auf die LinkedList-Implementierung umzustellen.
12
Das üblichere Problem besteht darin, eine Warteschlange mit zwei Stapeln zu implementieren. Das Buch von Chris Okasaki über rein funktionale Datenstrukturen könnte interessant sein.
Eric Lippert
2
Aufbauend auf dem, was Eric gesagt hat, kann es vorkommen, dass Sie sich in einer stapelbasierten Sprache befinden (z. B. DC oder ein Push-Down-Automat mit zwei Stapeln (entspricht einer Turing-Maschine, weil Sie mehr tun können)), in der Sie sich möglicherweise befinden mehrere Stapel, aber keine Warteschlange.
1
@MichaelT: Oder du findest dich auch auf einer Stack-basierten CPU wieder
slebetman
11
"Ein Stack ist eine (LIFO) Warteschlange" ... ähm, eine Warteschlange ist eine Warteschlange. Wie die Linie für die Nutzung einer öffentlichen Toilette. Verhalten sich die Zeilen, in denen Sie warten, jemals LIFO-artig? Stoppen Sie die Verwendung des Begriffs "LIFO-Warteschlange", es ist unsinnig.
Mehrdad

Antworten:

44

Es gibt keinen Vorteil: Dies ist eine rein akademische Übung.

Vor sehr langer Zeit, als ich ein Neuling auf dem College war, hatte ich eine ähnliche Übung 1 . Ziel war es, den Schülern beizubringen, wie man mit objektorientierter Programmierung Algorithmen implementiert, anstatt iterative Lösungen mithilfe von forSchleifen mit Schleifenzählern zu schreiben . Kombinieren und verwenden Sie stattdessen vorhandene Datenstrukturen, um Ihre Ziele zu erreichen.

Sie werden diesen Code niemals in der Real World TM verwenden . Was Sie von dieser Übung mitnehmen müssen, ist, wie Sie "über den Tellerrand hinaus denken" und Code wiederverwenden können.


Bitte beachten Sie, dass Sie sollten den unter Verwendung java.util.Queue Schnittstelle in Ihrem Code stattdessen die Umsetzung direkt zu verwenden:

Queue<T> q1 = new LinkedList<T>();
Queue<T> q2 = new LinkedList<T>();

Auf diese Weise können Sie bei Bedarf auch andere QueueImplementierungen verwenden und 2 Methoden ausblenden, LinkedListdie möglicherweise den Geist der QueueBenutzeroberfläche umgehen. Dies beinhaltet get(int)und pop()(während Ihr Code kompiliert wird, gibt es dort einen logischen Fehler in Anbetracht der Einschränkungen Ihrer Zuweisung. Wenn Sie Ihre Variablen als deklarieren, Queueanstatt LinkedListsie preiszugeben). Zugehörige Lektüre: Grundlegendes zum Programmieren mit einer Schnittstelle und Warum sind Schnittstellen nützlich?

1 Ich erinnere mich noch: Die Übung bestand darin, einen Stapel nur mit Methoden auf der Stapelschnittstelle und ohne Dienstprogrammmethoden in java.util.Collectionsoder anderen "nur statischen" Dienstprogrammklassen umzukehren . Die richtige Lösung besteht darin, andere Datenstrukturen als temporäre Aufbewahrungsobjekte zu verwenden: Sie müssen die verschiedenen Datenstrukturen, ihre Eigenschaften und deren Kombination kennen. Den größten Teil meiner CS101-Klasse, der noch nie programmiert hatte, überfordert.

2 Die Methoden sind noch vorhanden, aber Sie können nicht ohne Typumwandlungen oder Reflexionen darauf zugreifen. Es ist also nicht einfach , diese Nicht-Warteschlangen-Methoden zu verwenden.

Gemeinschaft
quelle
1
Vielen Dank. Ich denke, das macht Sinn. Ich habe auch festgestellt, dass ich im obigen Code "illegale" Operationen verwende (indem ich mich an den Anfang eines FIFOs drücke), aber ich denke, das ändert nichts. Ich habe alle Vorgänge rückgängig gemacht, und es funktioniert weiterhin wie beabsichtigt. Ich werde ein bisschen warten, bis ich akzeptiere, da ich andere Menschen nicht davon abhalten möchte, Beiträge zu leisten. Trotzdem danke.
Carcigenicate,
19

Es gibt keinen Vorteil. Sie haben richtig erkannt, dass die Verwendung von Warteschlangen zur Implementierung eines Stacks zu einer schrecklichen Zeitkomplexität führt. Kein (kompetenter) Programmierer würde so etwas jemals im "echten Leben" tun.

Aber es ist möglich. Sie können eine Abstraktion verwenden, um eine andere zu implementieren, und umgekehrt. Ein Stapel kann in Form von zwei Warteschlangen implementiert werden, und Sie können auch eine Warteschlange in Form von zwei Stapeln implementieren. Der Vorteil dieser Übung ist:

  • Sie rekapitulieren Stapel
  • Sie rekapitulieren Warteschlangen
  • man gewöhnt sich an algorithmisches Denken
  • Sie lernen stapelbezogene Algorithmen
  • Sie müssen sich Gedanken über Kompromisse bei Algorithmen machen
  • Indem Sie die Gleichwertigkeit von Warteschlangen und Stapeln erkennen, verbinden Sie verschiedene Themen Ihres Kurses
  • Sie sammeln praktische Programmiererfahrung

Tatsächlich ist dies eine großartige Übung. Ich sollte es jetzt selbst machen :)

amon
quelle
3
@JohnKugelman Danke für deine Bearbeitung, aber ich meinte wirklich "schreckliche Zeitkomplexität". Für eine verkettete Liste basierten Stapel push, peekund popOperationen sind in O (1). Dasselbe gilt für einen auf Array-Basis skalierbaren Stapel, mit der Ausnahme, dass dieser pushin O (1) amortisiert ist, wobei O (n) der schlimmste Fall ist. Im Vergleich dazu ist ein auf Warteschlangen basierender Stapel O (n) Push, O (1) Pop und Peek oder alternativ O (1) Push, O (n) Pop und Peek weit unterlegen.
amon
1
"schreckliche zeitliche Komplexität" und "weit unterlegen" ist nicht genau richtig. Amortisierte Komplexität ist immer noch O (1) für Push und Pop. Es gibt eine lustige Frage in TAOCP (vol1?) Dazu (im Grunde muss man zeigen, dass die Häufigkeit, mit der ein Element von einem Stapel zum anderen wechseln kann, konstant ist). Die Leistung im schlimmsten Fall für eine Operation ist unterschiedlich, aber dann höre ich selten jemanden, der über die O (N) -Leistung für das Pushen von ArrayLists spricht - nicht die normalerweise interessante Zahl.
Voo
5

Es gibt definitiv einen wirklichen Zweck, eine Warteschlange aus zwei Stapeln zu bilden. Wenn Sie unveränderliche Datenstrukturen aus einer funktionalen Sprache verwenden, können Sie einen Stapel von Push-fähigen Elementen verschieben und aus einer Liste von Popp-fähigen Elementen abrufen. Die platzierbaren Elemente werden erstellt, wenn alle Elemente herausgesprungen sind, und der neue platzierbare Stapel ist die Umkehrung des platzierbaren Stapels, in dem der neue platzierbare Stapel jetzt leer ist. Es ist effizient.

Wie für einen Stapel aus zwei Warteschlangen? Dies kann in einem Kontext sinnvoll sein, in dem viele große und schnelle Warteschlangen zur Verfügung stehen. Es ist definitiv nutzlos als diese Art von Java-Übung. Es kann jedoch sinnvoll sein, wenn es sich um Kanäle oder Messaging-Warteschlangen handelt. (dh: N Nachrichten in der Warteschlange mit einer O (1) -Operation, um (N-1) Elemente an der Vorderseite in eine neue Warteschlange zu verschieben.)

rauben
quelle
Hmm .. das brachte mich zum Nachdenken über die Verwendung von Schieberegistern als Grundlage für die Berechnung und über die Riemen / Mühlen-Architektur
slebetman
Wow, die Mill-CPU ist in der Tat interessant. Eine "Queue Machine" auf jeden Fall.
Rob
2

Die Übung ist aus praktischer Sicht unnötig konstruiert. Der Punkt ist, Sie zu zwingen, die Schnittstelle der Warteschlange auf geschickte Weise zu verwenden, um den Stapel zu implementieren. Zum Beispiel erfordert Ihre "One Queue" -Lösung, dass Sie die Warteschlange durchlaufen, um den letzten Eingabewert für die Stapel "Pop" -Operation zu erhalten. In einer Warteschlangendatenstruktur können die Werte jedoch nicht durchlaufen werden. Sie können nur im FIFO (First-In, First-Out) darauf zugreifen.

Destruktor
quelle
2

Wie andere bereits angemerkt haben: Es gibt keinen realen Vorteil.

Wie auch immer, eine Antwort auf den zweiten Teil Ihrer Frage, warum man nicht einfach eine Warteschlange benutzt, ist jenseits von Java.

In Java hat sogar die QueueSchnittstelle eine size()Methode und alle Standardimplementierungen dieser Methode sind O (1).

Dies gilt nicht unbedingt für die naive / kanonische verknüpfte Liste, wie sie ein C / C ++ - Programmierer implementieren würde, der lediglich Zeiger auf das erste und letzte Element und jedes Element einen Zeiger auf das nächste Element enthält.

In diesem Fall size()ist O (n) und sollte in Schleifen vermieden werden. Oder die Implementierung ist undurchsichtig und bietet nur das Nötigste add()und remove().

Bei einer solchen Implementierung müssten Sie zuerst die Anzahl der Elemente zählen, indem Sie sie in die zweite Warteschlange übertragen, n-1Elemente zurück in die erste Warteschlange übertragen und das verbleibende Element zurückgeben.

Das heißt, es würde wahrscheinlich nicht so etwas ausmachen, wenn Sie in Java-Land leben.

Thraidh
quelle
Guter Punkt über die size()Methode. Wenn jedoch keine O (1) size()-Methode vorhanden ist, ist es für den Stapel trivial, die aktuelle Größe selbst zu verfolgen. Nichts, um eine Implementierung mit einer Warteschlange zu stoppen.
18.
Auf die Umsetzung kommt es an. Wenn Sie eine Warteschlange haben, die nur Vorwärtszeiger und Zeiger auf das erste und das letzte Element enthält, können Sie dennoch einen Algorithmus schreiben, der ein Element entfernt, es in einer lokalen Variablen speichert und das zuvor in dieser Variablen befindliche Element in dieselbe Warteschlange einfügt, bis Das erste Element ist wieder zu sehen. Dies funktioniert nur, wenn Sie ein Element eindeutig identifizieren können (z. B. über einen Zeiger) und nicht nur etwas mit demselben Wert. O (n) und verwendet nur add () und remove (). Wie auch immer, es ist einfacher zu optimieren, einen Grund dafür zu finden, außer über Algorithmen nachzudenken.
Thraidh,
0

Eine Verwendung für eine solche Implementierung ist schwer vorstellbar, das stimmt. Es geht aber vor allem darum zu beweisen, dass dies möglich ist .

In Bezug auf die tatsächliche Verwendung dieser Dinge kann ich mir jedoch zwei vorstellen. Eine Verwendung hierfür ist die Implementierung von Systemen in eingeschränkten Umgebungen, die nicht dafür entwickelt wurden : Zum Beispiel die Redstone-Blöcke von Minecraft ein Turing-vollständiges System dar, mit dem Logikschaltungen und sogar ganze CPUs implementiert wurden. In den frühen Tagen des skriptgesteuerten Spielens wurden viele der ersten Spielebots ebenfalls auf diese Weise implementiert.

Aber Sie können auch dieses Prinzip in umgekehrter Richtung gelten, dass etwas Gewährleistung nicht ist in einem System möglich , wenn Sie nicht wollen , es zu sein . Dies kann in Sicherheitskontexten auftreten: Beispielsweise können leistungsstarke Konfigurationssysteme eine Bereicherung sein, es gibt jedoch noch Leistungsgrade, die Sie den Benutzern möglicherweise eher nicht geben. Dies schränkt ein, was Sie der Konfigurationssprache erlauben können, damit sie nicht von einem Angreifer unterlaufen wird. In diesem Fall ist dies jedoch genau das, was Sie möchten.

Der Löffeligste
quelle