Array-Basierte vs-List-Basierten Stapel und Warteschlangen

Gibt es mehrere verschiedene Wege zur Implementierung von Warteschlangen und stacks mit verknüpften Listen und arrays, und ich bin mir nicht sicher, welche Sie suchen. Vor der Analyse alle diese Strukturen, obwohl, lassen Sie uns überprüfen, einige wichtige runtime-überlegungen für die oben genannten Datenstrukturen.

In eine einfach-verkettete Liste mit nur einen Kopf, der Zeiger, die Kosten vorangestellt wird, ein Wert ist O(1) - wir erstellen Sie einfach das neue element, Draht-seine-pointer zu Punkt, an dem alten Kopf der Liste, dann aktualisieren Sie den head-Zeiger. Die Kosten so entfernen Sie das erste element ist auch O(1), der durchgeführt wird, durch die Aktualisierung der head-pointer zu Punkt, um das element nach der aktuellen Kopf -, dann die Speicherfreigabe für den alten Kopf (wenn die explizite Speicherverwaltung durchgeführt wird). Allerdings ist die Konstante Faktoren in O(1) Bedingungen kann hoch sein, bedingt durch die Kosten der dynamischen Zuweisungen. Der Speicher-overhead von die verlinkte Liste ist in der Regel O(n) insgesamt zusätzliche Speicher durch die Speicher einer extra Zeiger in jedem element.

In ein dynamisches array ist, können wir auf ein element in O(1) Zeit. Wir können auch hängen ein element in amortisiert O(1), was bedeutet, dass die Gesamtzeit für n Einfügeoperationen O(n), obwohl die tatsächliche Zeit, die Grenzen auf jede insertion kann viel schlimmer sein. In der Regel werden dynamische arrays zu implementieren, dass die meisten Einfügungen nehmen O(1) - Anhängen in vorbelegte Platz, aber mit einer kleinen Anzahl von Einfügungen führen in Θ(n) Zeit durch die Verdoppelung der array-Kapazität und kopieren von Elementen über. Es gibt Techniken, um zu versuchen, um dies zu reduzieren werden durch die Zuweisung zusätzlicher Raum und träge kopieren Sie die Elemente über (siehe diese Datenstruktur, zum Beispiel). In der Regel, die Speichernutzung eines dynamischen Arrays ist ziemlich gut, wenn das array komplett voll ist, zum Beispiel, gibt es nur O(1) zusätzlichen Aufwand - aber direkt nach dem array hat sich verdoppelt in der Größe kann es O(n) nicht verwendeten Elemente zugeordnet, die in das array. Denn die Zuweisungen sind selten und Zugriffe sind schnelle, dynamische arrays sind in der Regel schneller als verknüpfte Listen.

Nun, lassen Sie uns darüber nachdenken, wie implementieren Sie einen stack und eine Warteschlange mit einer verknüpften Liste oder dynamisches array. Es gibt viele Möglichkeiten, dies zu tun, also gehe ich davon aus, dass Sie die folgenden Implementierungen:

• Stack:
  • Verkettete Liste: Als einfach-verkettete Liste mit einem head-Zeiger.
  • Array: Als dynamische array
• Warteschlange:
  • Verkettete Liste: Als eine einfach-verkettete Liste mit head-und tail-Zeiger.
  • Array: Als Ringpuffer unterstützt durch ein array.

Betrachten wir jeweils in Reihe.

Stack unterstützt durch eine einfach-verkettete Liste. Da eine einfach-verkettete Liste unterstützt O(1) Zeit, anfügen und löschen-zuerst die Kosten zu drücken oder pop in einer verketteten Liste-backed-stack ist auch O(1) worst-case. Jedoch, jedes neue element, das Hinzugefügt wurde, erfordert eine neue Zuordnung und die Zuweisungen können teuer sein, im Vergleich zu anderen Operationen.

Stack unterstützt durch ein dynamisches array. Schieben auf den Stapel implementiert werden kann, indem ein neues element, um das dynamische array, das dauert amortisiert O(1) Zeit und die worst-case O(n) Zeit. Knallen aus dem Stapel implementiert werden kann, indem nur das Letzte element, das läuft im worst-case O(1) (oder amortisiert O(1) wenn Sie möchten, um zu versuchen, um ungenutzter Speicherplatz). In anderen Worten, ist die häufigste Implementierung hat best-case O(1) push-und pop -, worst-case O(n) push-and-O(1) pop, und amortisiert O(1) push-and-O(1) pop.

Warteschlange unterstützt durch eine einfach-verkettete Liste. Einreihen in die verkettete Liste implementiert werden kann, indem auf der Rückseite der einzeln verknüpften Liste, das dauert worst-case Zeit O(1). Abarbeiten der Warteschlange kann umgesetzt werden durch entfernen des ersten Elements, das dauert auch ein worst-case-Zeit O(1). Dies erfordert auch eine neue Zuteilung pro enqueue, die möglicherweise langsam.

Warteschlange unterstützt durch eine wachsende Ringpuffer. Einreihen in den Ringpuffer funktioniert durch einfügen von etwas, das an die nächste freie position im Ringpuffer. Dies funktioniert von wachsenden die array-wenn nötig, dann durch das einfügen des neuen Elements. Mit einer ähnlichen Analyse für die dynamischen Arrays, das dauert best-case-Zeit O(1), worst-case Zeit O(n), und amortisiert Zeit O(1). Entfernen der Daten aus dem Puffer funktioniert, indem Sie entfernen das erste element des zirkulären Puffer, die Zeit O(1) - im schlimmsten Fall.

Zusammen zu fassen, all die Strukturen, die Sie unterstützen, schieben und knallen die n Elemente in O(n) Zeit. Die verlinkte Liste Versionen haben eine bessere worst-case-Verhalten, kann aber ein schlechter gesamten Laufzeit, da die Anzahl der Zuordnungen durchgeführt. Die array-Versionen sind langsamer, im schlimmsten Fall, haben aber eine bessere Gesamtleistung, wenn die Zeit pro operation ist nicht allzu wichtig.

Weitere option möchten Sie vielleicht einen Blick ins für die Implementierung von stacks ist die VList, eine aktuelle Daten-Struktur, die ein hybrid aus einer verknüpften Liste und einem dynamischen array. Es macht weniger Zuweisungen als eine verknüpfte Liste und hat weniger Zeiger in es, wenn die Raum-Nutzung ist etwas höher im schlimmsten Fall. Sie möchten vielleicht auch einen Blick in chunklists, die anderen hybrid-arrays und verketteten Listen, die verwendet werden können sowohl Stapel und Warteschlangen.

Hoffe, das hilft!

InformationsquelleAutor templatetypedef