Warum würden Sie einen Stapel oder eine Warteschlange mithilfe einer Verknüpfungsliste anstelle einer Array- oder Vektorimplementierung implementieren?

Damit ich weiß, einen Stapel oder eine Warteschlange mit Vektor oder ein Array diese Eigenschaften aufweisen Umsetzung: fürWarum würden Sie einen Stapel oder eine Warteschlange mithilfe einer Verknüpfungsliste anstelle einer Array- oder Vektorimplementierung implementieren?

O (n)
Mindestens mit Array-Implementierung der Suche (Alle auf dem Stapel statt Heap)
O (1) peek oben/vorne oder nach hinten/unten

und wenn Raumbegrenzung des Arrays ist ein Thema würden Sie den Stapel oder Warteschlange unter Verwendung eines Vektors implementieren, also warum jemand eine dieser Datenstrukturen implementieren würde mit eine Linkliste? Jedes Beispiel aus dem wirklichen Leben wäre großartig, und eine große O-Notation einiger Grundfunktionen würde sich von der Array-/Vektorimplementierung unterscheiden.

Quelle

2016-07-27 Omid CompSCI

A 'LinkedList' ist eine Warteschlange in Java, und Sie können es über ein Array verwenden möchten, wenn Sie die Möglichkeit haben möchten, dynamisch zu wachsen. –

Wenn Sie dynamisch wachsen wollten, konnten Sie die Warteschlange oder den Stapel nicht einfach mit einem Vektor implementieren? Sorry, ich war mehr auf C++ ausgerichtet (Making your eigenen Stack oder Warteschlange von Grund auf neu) –

Für die Warteschlange würde eine verkettete Liste schnellere Ergebnisse liefern, wenn Daten in der Mitte der Warteschlange bearbeitet werden (hinzufügen/löschen): O (1). Wenn es mit einem Array oder einem Vektor implementiert wird, wäre es O (n), weil Sie andere Elemente verschieben müssen, um den Platz für das neue Element zu erstellen, oder den Raum des gelöschten Elements füllen.

Was den Stapel, verweise ich Sie auf diese Antwort: Linked list vs. dynamic array for implementing a stack

Quelle

2016-07-27 05:11:59 alexscasa

Vielen Dank, ich las den Artikel für Stack. Allerdings sehe ich nicht die Notwendigkeit, in der Mitte der Warteschlange einfügen, daher eine Warteschlange soll First-In-First-Out-Algorithmus sein, und wenn alles, was Sie in der Rückseite oder Front "Deque" einfügen können. Das wäre eine Link-Liste im Allgemeinen, wenn Sie andere Funktionen wie insertbeforeLast, insertBeforeIndex usw. hinzufügen. –

Entschuldigung, ich habe das Beispiel der Implementierung nicht in meine Antwort aufgenommen. Sie müssten die Mitte einer Warteschlange bearbeiten, wenn es sich um eine Prioritätswarteschlange handelt. Ein Element mit einer hohen Priorität muss vor anderen Elementen mit weniger Priorität hinzugefügt werden, aber nach Elementen mit höherer Priorität (in der Mitte). In der realen Welt können Personen Warteschlangen verlassen, so dass eine Löschung in der Mitte der Warteschlange erforderlich sein kann. – alexscasa

Ah, eine Prioritätswarteschlange! Ein großartiges Beispiel, das völlig sinnvoll und viel einfacher ist, dies über eine Link - Liste zu implementieren, anstatt sich mit der Verschiebung von Indizes zu beschäftigen. Vielen Dank! –

Warum würden Sie einen Stapel oder eine Warteschlange mithilfe einer Verknüpfungsliste anstelle einer Array- oder Vektorimplementierung implementieren?

Antwort

Verwandte Themen