Stapel / Warteschlange

[Luk10]

Grüße,

In der Schule besprechen wir gerade Warteschlange und Stapel.
Wir verwenden eine einfach verkettete lineare Liste mit den Klassen Liste, Knoten und Datenelement.

Wir sollen nun die Liste so umschreiben dass sie einmal auf eine Warteschlange passt und einmal so, dass sie auf die Datenstruktur Stapel zugeschnitten ist.

Die Klasse Liste hat einen

Knoten: erster

, jeder Knoten hat ein Datenelement und einen anderen

Knoten: naechster

.

Jetzt meine Frage: Ist bei der Warteschlange der Erste (Also z.B erster Kunde) auch

erster

in der Liste oder ist es der letzte Knoten von allen?

Wie ist es beim Stapel.

Danke, Luk

 

[darekkay]

Warteschlange, auch Queue genannt, funktioniert nach dem FIFO Prinzip: First In - First Out. Das heißt, was zuerst in die Schlange kommt, kommt auch zuerst raus (klar - wenn man an der Kasse steht, wird auch der Kunde, der zuerst da war, als erstes bedient ).

Ein Stapel (Stack) funktioniert nach dem LIFO-Prinzip: Last in - First Out. Das Beispiel hierfür ist ein Bücherstapel: wenn du auf deinen Stapel noch ein Buch drauflegst, dann musst du zuerst dieses Buch wieder runternehmen, um an die anderen Bücher ranzukommen (unter der Annahme, dass der Bücherstapel sonst umgeschmissen wird, wenn man versucht, ein Buch aus der Mitte zu nehmen ^^).

Formale Beschreibungen wie immer auf Wikipedia:
Stapelspeicher ? Wikipedia
Warteschlange (Datenstruktur) ? Wikipedia

 

[XHelp]

Warteschlage ist FIFO - First in - first out. Was zuerst reinkommt, geht zuerst raus.
Stapel ist LIFO - Last in - first out. Was zuletzt reinkommt, geht zuerst raus.
Bei der Umsetzung hast du einen gewissen Spielraum. z.B. bei der Warteschlange: Ob du nun an den Anfang einfügst und vom Ende ausgibst, oder ob du ans Ende einfügst und vom Anfang ausgibst ist egal.

 

[Luk10]

Was aber nicht meine Frage beantwortet ...

 

[XHelp]

Doch, eigentlich schon.