Stack vs Queue - Gemeinsamkeiten / Unterschiede

[Edward]

Hallo,

wie der Titel schon sagt möchte ich die Gemeinsamkeiten und Unterschiede zw. den beiden Datenstrukturen näher diskutieren.

Der wichtigste Unterschied ist wohl, dass bei dem Stack das FIFO und beim Qeue das FIFO Verfahren angewendet wird.

Außerdem lässt sich ein Stack mittels Array einfach realisieren - Was ja bei der Qeue nicht so ist. Warum eigentlich - und was gibt es noch für Unterschiede?

 

[Flown]

Der einzige Unterschied ist - wie du schon erwähnt hast - wie eingefügt und rausgenommen wird.

 

[mrBrown]

Außerdem lässt sich ein Stack mittels Array einfach realisieren - Was ja bei der Qeue nicht so ist. Warum eigentlich - und was gibt es noch für Unterschiede?

Der Stack verändert sich nur an einer Seite - es kommen oben Elemente drauf. Der Anfang des Stacks kann dann zB an Position 0 sein, und jedes neue Element kommt an den Index eins größer.
Die Queue verändert sich an zwei Seiten - es kommen oben Elemente dazu, und unten werden welche weggenommen. Die wirkliche Queue verschiebt sich dann quasi immer über das Array, und das müsste potenziell unendlich groß sein, auch wenn nur weniger Elemente gleichzeitig drin liegen (außer man schiebt sie immer wieder an den Anfang).

 

[Dompteur]

Außerdem lässt sich ein Stack mittels Array einfach realisieren - Was ja bei der Qeue nicht so ist.

Das stimmt so nicht. Natürlich kann man auch eine Queue durch ein Array realisieren. Eine ganz einfache Implementierung verwendet neben dem Array noch 2 Variablen, die auf das erste und das letzte Element zeigen. Der Einfachheit halber merkt man sich noch die Anzahl der Elemente in der Queue.
Das Array wird dann als Ring gesehen. Nach dem letzten Element folgt wieder das Element 0.
Mit ein wenig Suchen findest du im Netz jede Menge Beispiele.

 

[mrBrown]

Das stimmt so nicht. Natürlich kann man auch eine Queue durch ein Array realisieren. Eine ganz einfache Implementierung verwendet neben dem Array noch 2 Variablen, die auf das erste und das letzte Element zeigen. Der Einfachheit halber merkt man sich noch die Anzahl der Elemente in der Queue.
Das Array wird dann als Ring gesehen. Nach dem letzten Element folgt wieder das Element 0.
Mit ein wenig Suchen findest du im Netz jede Menge Beispiele.

Er sagt ja auch „nicht einfach“ und nicht „unmöglich“ 😉

 

[rubeb]

Ja MrBrown hat Recht

Array	Queue	Stack
	FIFO-Verfahren	FIFO-Verfahren

 

[rubeb]

Case closed

 

[KonradN]

Erst einmal der Hinweis: Der Thread ist von 2017.

Und bei einem Stack gilt First In Last Out und nicht First In First Out wie bei der Queue.

Bildlich ist der Stack ja der Stapel von z.B. Spielkarten. Und da legt man Karten oben auf und wenn man eine Karte wegnimmt, dann nimmt man diese von oben weg. Die erste Karte liegt also ganz unten und wird daher erst als letztes gezogen.