Datenstrukturen dienen dazu, mehrere Werte zu einem Ganzen zusammenzufassen. Zwei der einfachsten Datenstrukturen in der Informatik sind sogenannte Schlangen (englisch: queues) und Keller (auch Stapel oder englisch: stacks).
Beide Begriffe darf man wörtlich nehmen: Queues funktionieren wie die Warteschlangen an der Supermarktkasse – wer sich zuerst anstellt, ist auch als Erstes wieder draußen – und Stacks wie der heimische Keller – alles wird obendrauf geworfen, und wenn man das braucht, was ganz unten liegt, muss man alles andere aus dem Weg räumen.
Informatisch formuliert arbeiten Queues nach dem FIFO-Prinzip (first in, first out). Sie stellen Operationen zum Einfügen und Entfernen von Elementen bereit, wobei, wie in einer Warteschlange, ein Element erst dann entfernt werden kann, wenn alle vor ihm eingefügten Elemente entfernt wurden.
Stacks arbeiten nach dem LIFO-Prinzip (last in, first out). Elemente können auf einem Stack abgelegt und von diesem
entnommen werden, wobei immer nur das zuletzt abgelegte Element entnommen werden kann. Die Operation zum Ablegen eines Elements auf dem Stack heißt traditionell push, die zum
Entnehmen des zuletzt abgelegten Elements heißt pop.
Das folgende Beispiel veranschaulicht die Arbeitsweise eines Stacks anhand einiger Beispielaufrufe dieser Operationen:
push(3) push(4) pop() push(7) pop() pop()
leerer 4 7 3
Stack 4 ↑ 7 ↑ ↑
↓ 3 3 3 3 3
_____ _____ _____ _____ _____ _____ _____
Zu Beginn ist der Stack leer. Dann wird mit push(3) das Element 3 auf den Stack gelegt. Als Nächstes wird mit push(4) ein weiteres Element oben auf den Stack gelegt, welches dann mit pop() wieder entfernt wird. Die Operation pop() benötigt kein Argument, da immer nur das oberste Element entfernt werden kann. Im Anschluss werden noch die Operationen push(7), pop() und noch einmal pop() ausgeführt, wonach der Stack wieder leer ist.
Im Folgenden werden wir Stacks auch horizontal notieren. Das obige Beispiel sähe in dieser Schreibweise so aus:
| # push(3)
3 | # push(4)
3 4 | # pop()
3 | # push(7)
3 7 | # pop()
3 | # pop()
|
Der Stack ist zu Beginn und am Ende leer und neue Elemente werden rechts neben schon existierende eingefügt.