Stapel, Schlange und dynamische Reihung: Zusammenfassung – Informatik Grundkurs

Die dynamische Reihung

Eine Reihung, die mit jeder Operation wächst oder schrumpft — Zugriff auf jedes Element über den Index.

Index

Die Elemente stehen lückenlos an den Positionen 0 bis getLength() − 1.

erstes: getItem(0) · letztes: getItem(getLength() − 1)

Einfügen und Anhängen

append hängt hinten an; insertAt schiebt ein, der Rest rückt nach hinten.

append(x) · insertAt(i, x)

Ersetzen und Löschen

setItem ersetzt ohne Verschieben; delete entfernt, der Rest rückt nach vorn.

setItem(i, x) · delete(i)

Durchlaufen

Zählschleife über alle gültigen Indizes; Löschen in der Schleife rückwärts.

for (int i = l.getLength() − 1; i ≥ 0; i−−)

Operationen

append · insertAt · setItem · delete · getItem · getLength · isEmpty

Gültige Indizes: 0 ≤ i ≤ getLength() − 1.

Warum Löschen vorwärts schiefgeht

Nach delete(i) rückt das nächste Element auf Index i. Das anschließende i++ springt darüber — rückwärts laufen oder i nur ohne Löschen erhöhen.

Der Stapel

Nur das oberste Element ist erreichbar: Was zuletzt hineinkam, kommt zuerst heraus.

LIFO

Last In – First Out: Rückgängig, Browser-Zurück, Klammerprüfung, Aufrufstapel.

zuletzt hinein → zuerst heraus

push, pop, top

push legt oben auf, pop nimmt oben weg und liefert, top schaut nur nach.

push(x) · pop() · top() · isEmpty()

Hilfsstapel

Durchsehen = umladen; danach zurückladen, damit der Stapel unverändert bleibt.

umladen · bearbeiten · zurückladen

Klammerprüfung

Öffnende pushen, bei schließenden poppen und vergleichen, am Ende leer.

korrekt ⇔ alles passt und isEmpty()

Stapel

LIFO — push oben auflegen, pop oben wegnehmen

Vor pop() und top() mit isEmpty() prüfen.

Umladen dreht um

Beim Umladen auf einen Hilfsstapel dreht sich die Reihenfolge um; das Zurückladen dreht sie wieder richtig herum.

Die Schlange und die Wahl der Struktur

Hinten anstellen, vorn entnehmen: Die Reihenfolge des Eintreffens bleibt erhalten.

FIFO

First In – First Out: Druckaufträge, Warteschleifen, Rundlauf-Verfahren.

zuerst hinein → zuerst heraus

enqueue, dequeue, head

enqueue stellt hinten an, dequeue entnimmt vorn, head schaut nur nach.

enqueue(x) · dequeue() · head() · isEmpty()

Rotation

n-mal dequeue und enqueue — danach ist die Schlange wie vorher; Filtern durch gezieltes Nicht-Anstellen.

q.enqueue(q.dequeue())

Struktur wählen

Entscheidend ist die Reihenfolge, in der Daten wieder gebraucht werden.

beliebig → DynArray · neuestes → Stapel · ältestes → Schlange

Schlange

FIFO — enqueue hinten anstellen, dequeue vorn entnehmen

Anzahl der Durchläufe vor der Schleife bestimmen.

Rundlauf

Das vorderste Programm rechnet eine Zeitscheibe lang; ist es nicht fertig, wird es hinten wieder angestellt.