arrays - verkettete - stack queue array




Array-basierte vs List-basierte Stacks und Warteschlangen (2)

Ich versuche, die Wachstumsraten (Laufzeit und Speicherplatz) für Stapel- und Warteschlangenvorgänge zu vergleichen, wenn sie sowohl als Arrays als auch als verkettete Listen implementiert werden. Bis jetzt konnte ich nur durchschnittliche Durchlaufzeiten für Warteschlangen pop() s finden, aber nichts, das diese beiden Datenstrukturen umfassend untersucht und deren Laufzeit- / Raumverhalten vergleicht.

Genauer gesagt, ich vergleiche push() und pop() sowohl für Warteschlangen als auch für Stapel, implementiert als Arrays und verkettete Listen (also 2 Operationen x 2 Strukturen x 2 Implementierungen oder 8 Werte).

Außerdem würde ich die besten, Durchschnitts- und Worst-Case-Werte für beide und alles, was sich auf den Platzverbrauch bezieht, schätzen.

Die nächste Sache, die ich gefunden habe, ist diese "Mutter aller cs Spickzettel" pdf, die eindeutig ein Master-oder Doktor-Level-Spickzettel von fortschrittlichen Algorithmen und diskrete Funktionen ist.

Ich bin nur auf der Suche nach einer Möglichkeit zu bestimmen, wann und wo ich eine Array-basierte Implementierung im Vergleich zu einer listenbasierten Implementierung für beide Stapel und Warteschlangen verwenden sollte.


Entschuldigung, wenn ich deine Frage missverstanden habe, aber wenn ich es nicht getan habe, dann glaube ich, dass dies die Antwort ist, nach der du suchst.

Mit einem Vektor können Sie Elemente am Ende des Containers nur effizient hinzufügen / löschen. Mit einem Deque können Sie Elemente am Anfang / Ende des Containers effizient hinzufügen / löschen. Mit einer Liste können Sie Elemente überall im Container effizient einfügen / löschen.

Vektoren / Deque ermöglichen Direktzugriffs-Iteratoren. Listen erlauben nur sequentiellen Zugriff.

Wie Sie die Daten verwenden und speichern müssen, hängt davon ab, wie Sie die am besten geeigneten Daten ermitteln.

BEARBEITEN:

Es gibt viel mehr dazu, meine Antwort ist sehr verallgemeinert. Ich kann mehr in die Tiefe gehen, wenn ich überhaupt auf dem richtigen Weg bin, worum es bei Ihrer Frage geht.


Es gibt mehrere Möglichkeiten, Warteschlangen und Stacks mit verknüpften Listen und Arrays zu implementieren, und ich bin mir nicht sicher, nach welchen Sie suchen. Bevor wir jedoch eine dieser Strukturen analysieren, lassen Sie uns einige wichtige Überlegungen zur Laufzeit für die obigen Datenstrukturen anstellen.

In einer einfach verketteten Liste mit nur einem Kopfzeiger sind die Kosten, um einen Wert voranzustellen, O (1) - wir erstellen einfach das neue Element, verdrahten seinen Zeiger, um auf den alten Kopf der Liste zu zeigen, und aktualisieren dann den Kopfzeiger. Die Kosten zum Löschen des ersten Elements sind ebenfalls O (1), was durch Aktualisieren des Kopfzeigers zum Zeigen auf das Element nach dem aktuellen Kopf und dann Freigeben des Speichers für den alten Kopf erfolgt (wenn eine explizite Speicherverwaltung durchgeführt wird). Die konstanten Faktoren in diesen O (1) -Termen können jedoch aufgrund der Kosten von dynamischen Zuordnungen hoch sein. Der Speicheraufwand der verknüpften Liste ist normalerweise O (n) insgesamt zusätzlicher Speicher aufgrund der Speicherung eines zusätzlichen Zeigers in jedem Element.

In einem dynamischen Array können wir auf jedes Element in O (1) -Zeit zugreifen. Wir können auch ein Element in amortisierten O (1) anhängen, was bedeutet, dass die Gesamtzeit für n Einfügungen O (n) ist, obwohl die tatsächliche Zeitgrenze bei jeder Einfügung viel schlechter sein kann. Typischerweise werden dynamische Arrays implementiert, indem die meisten Einfügungen O (1) annehmen, indem sie in vorab zugewiesenen Speicherplatz anhängen, aber eine kleine Anzahl von Einfügungen in Θ (n) -Zeit ausführen, indem die Array-Kapazität verdoppelt und Elemente kopiert werden. Es gibt Techniken, um zu versuchen, dies zu reduzieren, indem Sie zusätzlichen Speicherplatz zuweisen und die Elemente langsam kopieren (siehe zum Beispiel diese Datenstruktur ). In der Regel ist die Speichernutzung eines dynamischen Arrays recht gut - wenn das Array beispielsweise vollständig gefüllt ist, gibt es nur O (1) zusätzlichen Overhead - obwohl direkt nach der Verdoppelung des Arrays O (n) unbenutzt ist Elemente im Array zugewiesen. Da Zuordnungen selten sind und die Zugriffe schnell sind, sind dynamische Arrays in der Regel schneller als verknüpfte Listen.

Lassen Sie uns nun darüber nachdenken, wie Sie einen Stack und eine Warteschlange mithilfe einer verknüpften Liste oder eines dynamischen Arrays implementieren. Es gibt viele Möglichkeiten, dies zu tun, daher nehme ich an, dass Sie die folgenden Implementierungen verwenden:

  • Stapel:
  • Warteschlange:
    • Verknüpfte Liste: Als einfach verkettete Liste mit einem Kopf- und einem Endzeiger.
    • Array: Als Ringpuffer, der von einem Array unterstützt wird.

Betrachten wir uns nacheinander.

Stack wird von einer einfach verknüpften Liste unterstützt. Da eine einfach verkettete Liste O (1) -Zeitvoranstellen und -löscht-zuerst unterstützt, sind die Kosten, um in einen Linked-List-Backed-Stack zu pushen oder aufzuspringen, ebenfalls O (1) Worst-Case. Jedes hinzugefügte neue Element erfordert jedoch eine neue Zuweisung, und Zuordnungen können im Vergleich zu anderen Vorgängen teuer sein.

Stack unterstützt von einem dynamischen Array. Das Aufschieben auf den Stapel kann implementiert werden, indem ein neues Element an das dynamische Array angehängt wird, das die amortisierte O (1) -Zeit und die Worst-Case-O (n) -Zeit benötigt. Popping aus dem Stack kann implementiert werden, indem nur das letzte Element entfernt wird, das im schlimmsten Fall O (1) läuft (oder amortisiertes O (1), wenn Sie versuchen möchten, ungenutzten Speicherplatz zurück zu gewinnen). Mit anderen Worten, die gebräuchlichste Implementierung hat Best-Case O (1) Push und Pop, Worst-Case O (n) Push und O (1) Pop und Amortisated O (1) Push und O (1) Pop.

Warteschlange, die von einer einfach verknüpften Liste unterstützt wird. Das Einreihen in die verknüpfte Liste kann implementiert werden, indem an die Rückseite der einfach verknüpften Liste angefügt wird, was die ungünstigste Zeit O (1) einnimmt. Das Ausreißen kann implementiert werden, indem das erste Element entfernt wird, was ebenfalls die Zeit O (1) im ungünstigsten Fall einnimmt. Dies erfordert auch eine neue Zuweisung pro Warteschlange, die langsam sein kann.

Warteschlange wird von einem wachsenden Ringpuffer unterstützt. Das Einreihen in den Ringpuffer funktioniert, indem etwas an der nächsten freien Position in den Ringpuffer eingefügt wird. Dies funktioniert, indem das Array bei Bedarf vergrößert und dann das neue Element eingefügt wird. Mit einer ähnlichen Analyse für das dynamische Array werden die beste Zeit O (1), die ungünstigste Zeit O (n) und die amortisierte Zeit O (1) verwendet. Die Auslagerung aus dem Puffer funktioniert, indem das erste Element des Ringpuffers entfernt wird, was im schlimmsten Fall Zeit O (1) benötigt.

Zusammenfassend lässt sich sagen, dass alle Strukturen das Drücken und Puffen von n Elementen in O (n) -Zeit unterstützen. Die Versionen mit verketteten Listen haben ein besseres Worst-Case-Verhalten, können aber wegen der Anzahl der durchgeführten Zuweisungen eine schlechtere Gesamtlaufzeit haben. Die Array-Versionen sind im schlimmsten Fall langsamer, haben aber eine bessere Gesamtleistung, wenn die Zeit pro Operation nicht zu wichtig ist.

Eine andere Option, die Sie möglicherweise zum Implementieren von Stapeln untersuchen VList , ist der VList , eine aktuelle Datenstruktur, die eine Mischung aus einer verknüpften Liste und einem dynamischen Array ist. Es macht weniger Zuweisungen als eine verknüpfte Liste und enthält weniger Zeiger, obwohl die Speicherplatzbelegung im schlimmsten Fall etwas höher ist. Möglicherweise möchten Sie auch in Chunklisten suchen, die eine weitere Mischung aus Arrays und verknüpften Listen sind, die für Stapel und Warteschlangen verwendet werden können.

Hoffe das hilft!





linked-list