Was ist der grundlegende Unterschied zwischen Stapel und Warteschlange?

130

Was ist der grundlegende Unterschied zwischen Stapel und Warteschlange?

Bitte helfen Sie mir, ich kann den Unterschied nicht finden.

Wie unterscheidet man einen Stapel und eine Warteschlange?

Ich habe in verschiedenen Links nach der Antwort gesucht und diese Antwort gefunden.

In der High-Level-Programmierung

Ein Stapel ist definiert als eine Liste oder Folge von Elementen, die verlängert wird, indem neue Elemente "über" vorhandenen Elementen platziert und durch Entfernen von Elementen von oben auf vorhandenen Elementen verkürzt werden. Es ist ein ADT [Abstract Data Type] mit mathematischen Operationen von "push" und "pop".

Eine Warteschlange ist eine Folge von Elementen, die hinzugefügt wird, indem das neue Element an der Rückseite des vorhandenen Elements platziert und durch Entfernen von Elementen vor der Warteschlange verkürzt wird. Es ist ein ADT [Abstract Data Type]. Diese Begriffe werden in der Programmierung von Java, C ++, Python usw. besser verstanden.

Kann ich eine detailliertere Antwort haben? Bitte hilf mir.

Harish Rachakonda
quelle
12
Sie scheinen Ihre eigene Frage beantwortet zu haben: Ein Stapel ist ein LIFO-Container (Last-In First-Out) und eine Warteschlange ist ein FIFO-Container (First-In First-Out).
Iridium

Antworten:

151

Der Stapel ist eine LIFO-Datenstruktur (last in first out). Der zugehörige Link zu Wikipedia enthält eine detaillierte Beschreibung und Beispiele.

Die Warteschlange ist eine FIFO-Datenstruktur (First In First Out). Der zugehörige Link zu Wikipedia enthält eine detaillierte Beschreibung und Beispiele.

jhonkola
quelle
131

Stellen Sie sich einen Stapel Papier vor . Das letzte Stück, das in den Stapel gelegt wird, befindet sich oben, es ist also das erste, das herauskommt. Das ist LIFO . Das Hinzufügen eines Blattes Papier wird als "Drücken" bezeichnet, und das Entfernen eines Blattes Papier wird als "Knallen" bezeichnet.

Stellen Sie sich eine Warteschlange im Laden vor . Die erste Person in der Schlange ist die erste Person, die aus der Reihe kommt. Das ist FIFO . Eine Person, die in die Reihe kommt, wird "in die Warteschlange gestellt", und eine Person, die aus der Reihe kommt, wird "in die Warteschlange gestellt".

123
quelle
3
Eine der besten Analogien, die ich mir vorstellen kann.
Yeikel
83

Ein visuelles Modell

Pfannkuchen - Stapel (LIFO)

Die einzige Möglichkeit, eine hinzuzufügen und / oder zu entfernen, ist von oben.

Pfannkuchenstapel

Line Queue (FIFO)

Wenn man ankommt, kommt man am Ende der Warteschlange an und wenn man geht, geht man von der Vorderseite der Warteschlange weg.

dmv line

Lustige Tatsache: Die Briten bezeichnen Linien von Menschen als Warteschlange

Jacksonkr
quelle
6
Jee, das muss die Antwort sein. Danke @Jacksonkr
Kulasangar
Haha, sicher, dass dies eine perfekte Beschreibung von Queue and Stack ist, aber nur um der Argumentation willen, was ist, wenn ich möchte, dass der erste Pfannkuchen auf den Teller kommt? Ich weiß, dass dies mit einem stack.size () vs. if (! Stack.isEmpty ()) abgeschlossen werden kann, aber dennoch könnte dieser erste Pfannkuchen der beste sein :) ... So oder so, nette Antwort und ich stimme dem zu Das klarste ... scheint interessant zu sein, dass die Briten Zeilen als Warteschlangen bezeichnen (wenn das korrekt ist). In einer Nicht-Programmiersprache würde ich immer noch davon ausgehen, dass eine Zeile, in der der erste Eintrag zuerst verlassen wird (nach dem Verlassen der Zeile / Warteschlange) )
ViaTech
Warten Sie, sie werden anderswo nicht als Warteschlangen bezeichnet?
Ausflug
37

Sie können sich beides als eine geordnete Liste von Dingen vorstellen (geordnet nach dem Zeitpunkt, zu dem sie der Liste hinzugefügt wurden). Der Hauptunterschied zwischen den beiden besteht darin, wie neue Elemente in die Liste aufgenommen werden und alte Elemente die Liste verlassen.

Wenn ich für einen Stapel eine Liste habe a, b, cund diese hinzufüge d, wird sie am Ende angeheftet, sodass ich am Ende mit a,b,c,d. Wenn ich ein Element der Liste einfügen möchte, entferne ich das zuletzt hinzugefügte Element d. Nach einem Pop ist meine Liste jetzt a,b,cwieder

Für eine Warteschlange füge ich auf die gleiche Weise neue Elemente hinzu. a,b,cwird a,b,c,dnach dem Hinzufügen d. Aber jetzt, wenn ich auftauche, muss ich ein Element von der Vorderseite der Liste nehmen, damit es wird b,c,d.

Es ist sehr einfach!

Cdesrosiers
quelle
14

Warteschlange

Warteschlange ist eine geordnete Sammlung von Artikeln.

Elemente werden an einem Ende gelöscht, das als "vorderes" Ende der Warteschlange bezeichnet wird.

Elemente werden am anderen Ende eingefügt, das als "Rückseite" der Warteschlange bezeichnet wird.

Das erste eingefügte Element ist das erste, das entfernt wird (FIFO).

Stapel

Stapel ist eine Sammlung von Gegenständen.

Es ermöglicht den Zugriff auf nur ein Datenelement: das zuletzt eingefügte Element.

Elemente werden an einem Ende eingefügt und gelöscht, das als "Top of the Stack" bezeichnet wird.

Es ist ein dynamisches und sich ständig änderndes Objekt.

Alle Datenelemente werden oben auf den Stapel gelegt und oben abgenommen

Diese Struktur des Zugriffs wird als Last-in-First-out-Struktur (LIFO) bezeichnet.

Dissanayake
quelle
Im Grunde genommen ist eine "Warteschlange" ein "FIFO" - First-in-First-Out-Warteschlange. Während ein 'Stack' ein "LIFO" ist - last in first out queue. Hab ich recht?
Sebastian Nielsen
@SebastianNielsen Ja richtig wie in der Antwort erwähnt.
Dissanayake
Aber was ist dann der Unterschied zwischen einer verknüpften Liste und einem Stapel? Ist es nicht dasselbe?
Sebastian Nielsen
@SebastianNielsen Der Stack ist ein ADT. Dies bedeutet, dass eine Schnittstelle verfügbar gemacht wird, bei der es sich um die Push- und Pop-Operation handelt. Der zugrunde liegende Mechanismus (Implementierung) ist jedoch für den Endbenutzer verborgen. Ein Stapel kann mit einem Array oder mit einer verknüpften Liste implementiert werden.
Gdyrrahitis
13

STAPEL:

  1. Stapel ist definiert als eine Liste von Elementen, in die wir Elemente nur am oberen Rand des Stapels einfügen oder löschen können.
  2. Das Verhalten eines Stapels ähnelt einem LIFO-System (Last-In First-Out).
  3. Der Stapel wird verwendet, um Parameter zwischen Funktionen zu übergeben. Bei einem Aufruf einer Funktion werden die Parameter und lokalen Variablen auf einem Stapel gespeichert.
  4. Hochwertige Programmiersprachen wie Pascal, c usw., die die Rekursion unterstützen, verwenden den Stapel für die Buchhaltung. Denken Sie daran, dass bei jedem rekursiven Aufruf der aktuelle Wert von Parametern, lokalen Variablen und die Rücksprungadresse (die Adresse, an die das Steuerelement nach dem Aufruf zurückkehren muss) gespeichert werden müssen.

WARTESCHLANGE:

  1. Die Warteschlange ist eine Sammlung desselben Elementtyps. Es handelt sich um eine lineare Liste, in der Einfügungen an einem Ende der Liste erfolgen können, die als Rückseite der Liste bezeichnet wird, und Löschungen nur am anderen Ende erfolgen können, das als Vorderseite der Liste bezeichnet wird
  2. Das Verhalten einer Warteschlange ähnelt einem FIFO-System (First-In-First-Out).
ASHUTOSH KUMAR
quelle
Ich bin mir ziemlich sicher, dass Sie auch am Ende oder am Anfang eines Stapels einfügen können. Ich denke, das Wichtigste, was Sie hier beachten sollten, ist das FIFO vs. LIFO
Mike
6

Ein Stapel ist eine Sammlung von Elementen, die einzeln gespeichert und abgerufen werden können. Elemente werden in umgekehrter Reihenfolge ihrer Speicherzeit abgerufen, dh das zuletzt gespeicherte Element ist das nächste abzurufende Element. Ein Stapel wird manchmal als LIFO-Struktur (Last-In-First-Out) oder FILO-Struktur (First-In-Last-Out) bezeichnet. Zuvor gespeicherte Elemente können erst abgerufen werden, wenn das neueste Element (normalerweise als "oberstes" Element bezeichnet) abgerufen wurde.

Eine Warteschlange ist eine Sammlung von Elementen, die einzeln gespeichert und abgerufen werden können. Elemente werden in der Reihenfolge ihrer Speicherzeit abgerufen, dh das erste gespeicherte Element ist das nächste abzurufende Element. Eine Warteschlange wird manchmal als FIFO-Struktur (First-In-First-Out) oder LILO-Struktur (Last-In-Last-Out) bezeichnet. Nachfolgend gespeicherte Elemente können erst abgerufen werden, wenn das erste Element (normalerweise als "Front" -Element bezeichnet) abgerufen wurde.

Saurabh RS
quelle
2

STACK: Stack ist eine Liste von Elementen, in die Elemente nur am oberen Rand des Stapels eingefügt oder gelöscht werden können

Der Stapel wird verwendet, um Parameter zwischen Funktionen zu übergeben. Bei einem Aufruf einer Funktion werden die Parameter und lokalen Variablen auf einem Stapel gespeichert.

Ein Stapel ist eine Sammlung von Elementen, die einzeln gespeichert und abgerufen werden können. Elemente werden in umgekehrter Reihenfolge ihrer Speicherzeit abgerufen, dh das zuletzt gespeicherte Element ist das nächste abzurufende Element. Ein Stapel wird manchmal als LIFO-Struktur (Last-In-First-Out) oder FILO-Struktur (First-In-Last-Out) bezeichnet. Zuvor gespeicherte Elemente können erst abgerufen werden, wenn das neueste Element (normalerweise als "oberstes" Element bezeichnet) abgerufen wurde.

WARTESCHLANGE:

Die Warteschlange ist eine Sammlung desselben Elementtyps. Es handelt sich um eine lineare Liste, in der Einfügungen an einem Ende der Liste erfolgen können, die als Rückseite der Liste bezeichnet wird, und Löschungen nur am anderen Ende erfolgen können, das als Vorderseite der Liste bezeichnet wird

Eine Warteschlange ist eine Sammlung von Elementen, die einzeln gespeichert und abgerufen werden können. Elemente werden in der Reihenfolge ihrer Speicherzeit abgerufen, dh das erste gespeicherte Element ist das nächste abzurufende Element. Eine Warteschlange wird manchmal als FIFO-Struktur (First-In-First-Out) oder LILO-Struktur (Last-In-Last-Out) bezeichnet. Nachfolgend gespeicherte Elemente können erst abgerufen werden, wenn das erste Element (normalerweise als "Front" -Element bezeichnet) abgerufen wurde.

Shashimani
quelle
2

Um die Beschreibung eines Stapels und einer Warteschlange zu vereinfachen, handelt es sich um dynamische Ketten von Informationselementen, auf die von einem Ende der Kette aus zugegriffen werden kann. Der einzige wirkliche Unterschied zwischen ihnen besteht in der Tatsache, dass:

bei der Arbeit mit einem Stapel

  • Sie fügen Elemente an einem Ende der Kette ein und
  • Sie rufen Elemente am selben Ende der Kette ab und / oder entfernen sie

während mit einer Warteschlange

  • Sie fügen Elemente an einem Ende der Kette ein und
  • Sie rufen sie am anderen Ende ab / entfernen sie

HINWEIS : Ich verwende in diesem Zusammenhang den abstrakten Wortlaut "Abrufen / Entfernen", da es Fälle gibt, in denen Sie das Element nur aus der Kette abrufen oder in gewisser Weise nur lesen oder auf seinen Wert zugreifen, aber auch Fälle, in denen Sie das Element aus entfernen die Kette und schließlich gibt es Fälle, in denen Sie beide Aktionen mit demselben Aufruf ausführen.

Das Wortelement wird auch absichtlich verwendet, um die imaginäre Kette so weit wie möglich zu abstrahieren und von bestimmten Begriffen der Programmiersprache zu entkoppeln. Diese abstrakte Informationsentität, die als Element bezeichnet wird, kann je nach Sprache ein Zeiger, ein Wert, eine Zeichenfolge oder Zeichen, ein Objekt usw. sein.

In den meisten Fällen handelt es sich jedoch entweder um einen Wert oder um einen Speicherort (dh einen Zeiger). Und der Rest versteckt diese Tatsache nur hinter dem Sprachjargon <

Eine Warteschlange kann hilfreich sein, wenn die Reihenfolge der Elemente wichtig ist und genau der Reihenfolge entsprechen muss, in der die Elemente zum ersten Mal in Ihr Programm aufgenommen wurden. Zum Beispiel, wenn Sie einen Audiostream verarbeiten oder wenn Sie Netzwerkdaten puffern. Oder wenn Sie irgendeine Art von Speicherung und Weiterleitung durchführen. In all diesen Fällen muss die Reihenfolge der Elemente in derselben Reihenfolge ausgegeben werden, in der sie in Ihr Programm eingegeben wurden. Andernfalls sind die Informationen möglicherweise nicht mehr sinnvoll. Sie können Ihr Programm also in einem Teil unterbrechen, der Daten von einer Eingabe liest, verarbeitet und in eine Warteschlange schreibt, und ein Teil, der Daten aus der Warteschlange abruft, verarbeitet und in einer anderen Warteschlange speichert, um die Daten weiter zu verarbeiten oder zu übertragen .

Ein Stapel kann hilfreich sein, wenn Sie ein Element vorübergehend speichern müssen, das in den unmittelbaren Schritten Ihres Programms verwendet werden soll. Beispielsweise verwenden Programmiersprachen normalerweise eine Stapelstruktur, um Variablen an Funktionen zu übergeben. Was sie tatsächlich tun, ist, die Funktionsargumente im Stapel zu speichern (oder zu pushen) und dann zu der Funktion zu springen, in der sie die gleiche Anzahl von Elementen aus dem Stapel entfernen und abrufen (oder einfügen). Auf diese Weise hängt die Größe des Stapels von der Anzahl der verschachtelten Funktionsaufrufe ab. Nachdem eine Funktion aufgerufen und beendet wurde, verlässt sie den Stapel in genau demselben Zustand wie vor dem Aufruf! Auf diese Weise kann jede Funktion mit dem Stapel arbeiten und ignoriert, wie andere Funktionen damit arbeiten.

Schließlich sollten Sie wissen, dass es andere Begriffe gibt, die für dieselben ähnlichen Konzepte verwendet werden. Zum Beispiel könnte ein Stapel als Heap bezeichnet werden. Es gibt auch Hybridversionen dieser Konzepte, z. B. kann sich eine Warteschlange mit zwei Enden gleichzeitig wie ein Stapel und eine Warteschlange verhalten, da von beiden Seiten gleichzeitig auf sie zugegriffen werden kann. Darüber hinaus bedeutet die Tatsache, dass Ihnen eine Datenstruktur als Stapel oder als Warteschlange zur Verfügung gestellt wird, nicht unbedingt, dass sie als solche implementiert ist. Es gibt Fälle, in denen eine Datenstruktur als alles implementiert und als spezifisch bereitgestellt werden kann Datenstruktur einfach, weil sie sich so verhalten kann. Mit anderen Worten, wenn Sie einer Datenstruktur eine Push- und Pop-Methode bereitstellen, werden sie auf magische Weise zu Stapeln!

Angelos Asonitis
quelle
Verwenden Sie keine Code-Formatierung für Text, der kein Code ist.
Marquis von Lorne
1

STACK ist eine LIFO-Liste (last in, first out). bedeutet, dass 3 Elemente in den Stapel eingefügt werden, dh 10,20,30. 10 wird zuerst eingefügt und 30 wird zuletzt eingefügt, so dass 30 zuerst vom Stapel gelöscht wird und 10 zuletzt vom Stapel gelöscht wird. Dies ist eine LIFO-Liste (Last In First Out).

QUEUE ist eine FIFO-Liste (First In First Out). Dies bedeutet, dass zuerst ein Element eingefügt wird, das zuerst gelöscht werden soll.

Apurva Sanjay Borse
quelle
1

Stapelt eine als vertikale Sammlung betrachtete Sammlung. Verstehen Sie zunächst, dass eine Sammlung ein OBJEKT ist, das andere kleinere OBJEKTE sammelt und organisiert. Diese kleineren OBJEKTE werden üblicherweise als Elemente bezeichnet. Diese Elemente werden in einer ABC-Reihenfolge auf dem Stapel "geschoben", wobei A an erster Stelle und C an letzter Stelle steht. vertikal würde es so aussehen: 3. Element hinzugefügt) C 2. Element hinzugefügt) B 1. Element hinzugefügt) A.

Beachten Sie, dass sich das "A", das zuerst zum Stapel hinzugefügt wurde, unten befindet. Wenn Sie das "A" vom Stapel entfernen möchten, müssen Sie zuerst "C", dann "B" und schließlich Ihr Zielelement "A" entfernen. Der Stapel erfordert einen LIFO-Ansatz, um die Komplexität eines Stapels zu bewältigen. (Last In First Out) Wenn Sie ein Element von einem Stapel entfernen, lautet die korrekte Syntax pop. Wir entfernen kein Element von einem Stapel, sondern "platzen" es ab.

Denken Sie daran, dass "A" das erste Element war, das auf den Stapel geschoben wurde, und "C" das letzte Element war, das auf den Stapel geschoben wurde. Wenn Sie sich entscheiden, dass Sie sehen möchten, was sich unten auf dem Stapel befindet, da die 3 Elemente auf dem Stapel angeordnet sind, wobei A das erste B das zweite und C das dritte Element ist, muss das obere Element dann entfernt werden zweites Element hinzugefügt, um den unteren Rand des Stapels anzuzeigen.

Zimmermen7
quelle
Bitte formatieren Sie Ihre Frage, damit sie besser und lesbarer aussieht.
Neeku