Drei Strukturen, drei Zugriffsarten
Alle drei Strukturen speichern beliebig viele Elemente in einer Reihe. Sie unterscheiden sich darin, wo man hineinlegen und wo man herausnehmen darf.
| DynArray | Stapel | Schlange | |
|---|---|---|---|
| Zugriff | jedes Element über den Index | nur oben | nur vorn |
| Einfügen | an jeder Stelle | oben (push) | hinten (enqueue) |
| Entnehmen | an jeder Stelle | oben (pop) | vorn (dequeue) |
| Reihenfolge | frei | LIFO | FIFO |
- Weniger ist mehr:Stapel und Schlange können weniger als die Reihung — dafür sind Programme mit ihnen kürzer und Fehler seltener.
- Nachbauen:Jeden Stapel und jede Schlange könnte man mit einem DynArray nachbilden, müsste aber selbst auf die Regeln achten.
Gemeinsamkeit: DynArray, Stapel und Schlange speichern beliebig viele Elemente in einer Reihe; sie unterscheiden sich darin, wo man einfügen und entnehmen darf.
DynArray: Zugriff auf jedes Element über den Index, Einfügen und Entnehmen an jeder Stelle, Reihenfolge frei.
Stapel: Zugriff nur oben (push, pop), Reihenfolge LIFO.
Schlange: hinten einfügen (enqueue), vorn entnehmen (dequeue), Reihenfolge FIFO.
Weniger ist mehr: Stapel und Schlange können weniger als die Reihung, dafür sind Programme kürzer und Fehler seltener.
Die passende Struktur wählen
Entscheidend ist, in welcher Reihenfolge die Daten wieder gebraucht werden.
- Frage 1:Muss ich gezielt auf ein Element mitten in der Reihe zugreifen oder dort einfügen? → DynArray.
- Frage 2:Wird immer das zuletzt Hinzugefügte zuerst gebraucht? → Stapel.
- Frage 3:Wird in der Reihenfolge des Eintreffens abgearbeitet? → Schlange.
Ordne jede Situation der passenden Datenstruktur zu: Karte anklicken und dann einen Korb wählen — oder ziehen. Mit der Tastatur: Karte ansteuern und 1, 2 oder 3 drücken.
Halte fest: Man wählt die Struktur nach der Reihenfolge, in der die Daten wieder gebraucht werden — nicht nach der Art der Daten.
Wahl nach dem Zugriff: beliebig → DynArray · Neuestes zuerst → Stapel · Ältestes zuerst → Schlange.
Entscheidend: In welcher Reihenfolge werden die Daten wieder gebraucht? Gezielter Zugriff oder Einfügen in der Mitte → DynArray; zuletzt Hinzugefügtes zuerst → Stapel; in der Reihenfolge des Eintreffens → Schlange.
Merke: Man wählt die Struktur nach der Reihenfolge der Verwendung, nicht nach der Art der Daten.
Allgemeine Hinweise
Nicht nach dem Inhalt wählen
Ob Namen, Zahlen oder Aufträge gespeichert werden, ist egal. Es zählt nur, welches Element als Nächstes gebraucht wird.
Begründen gehört dazu
In Klausuren genügt „Schlange“ nicht. Erwartet wird die Begründung über das Prinzip: Aufträge werden in der Reihenfolge ihres Eintreffens bearbeitet (FIFO).
Die Probe mit drei Elementen
Drei Elemente A, B, C hineinlegen und überlegen, welches zuerst wieder gebraucht wird: C → Stapel, A → Schlange, beliebig → DynArray.