MINT lernen

Das Prinzip Stapel

Zwei Abituraufgaben zum Stapel — vom Ablagestapel bis zur Rückgängig-Funktion.

Dein Fortschritt:
0 / 0 Aufgaben
1

Ablagestapel beim Kartenspiel

AFB I–II

Bei einem Kartenspiel wird der Ablagestapel als Stack<String> ablage modelliert. Er ist zu Beginn leer. Nacheinander werden ausgeführt:

ablage.push("Herz 7");
ablage.push("Pik Bube");
String a = ablage.pop();
ablage.push("Karo 9");
String b = ablage.top();
  1. Stellen Sie den Stapel nach jeder Anweisung grafisch dar und geben Sie die Werte von a und b an.
  2. Nennen Sie zwei weitere Anwendungen des Stapelprinzips in der Informatik.

Hinweise

Hinweis zu Aufgabe a)
Zeichnen Sie den Stapel senkrecht mit dem obersten Element oben. top() verändert den Stapel nicht.
Hinweis zu Aufgabe b)
Denken Sie an Programme, bei denen man „zurück“ geht.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

[Herz 7] → [Herz 7, Pik Bube] → [Herz 7], a = „Pik Bube“ → [Herz 7, Karo 9] → unverändert [Herz 7, Karo 9], b = „Karo 9“ (jeweils unten links, oben rechts).

Erwartungshorizont zu Aufgabe b)

Zum Beispiel: Rückgängig-Funktion in Editoren, Zurück-Knopf im Browser, Aufrufstapel bei Methodenaufrufen, Klammerprüfung, Rückweg bei der Suche in einem Labyrinth.

2

Rückgängig im Texteditor

AFB II–III

Ein einfacher Texteditor speichert jede Aktion als Text (z. B. „Wort löschen“) im Attribut Stack<String> aktionen. Rückgängig gemachte Aktionen sollen im Attribut Stack<String> wiederholen abgelegt werden, damit man sie später wiederholen kann.

  1. Erklären Sie, warum ein Stapel für die Rückgängig-Funktion geeignet ist.
  2. Implementieren Sie die Methode String rueckgaengig(), die die letzte Aktion zurücknimmt, sie in wiederholen ablegt und zurückgibt. Ist nichts rückgängig zu machen, wird der leere Text zurückgegeben.
  3. Erörtern Sie den Vorschlag, höchstens die letzten 100 Aktionen zu speichern und bei der 101. Aktion die älteste zu verwerfen.

Hinweise

Hinweis zu Aufgabe a)
Welche Aktion muss als Erstes zurückgenommen werden?
Hinweis zu Aufgabe b)
Vor dem Entnehmen mit isEmpty() prüfen.
Hinweis zu Aufgabe c)
Wo liegt beim Stapel die älteste Aktion, und wie kommt man an sie heran?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Rückgängig nimmt immer die zuletzt ausgeführte Aktion zuerst zurück, dann die davor usw. Das entspricht dem LIFO-Prinzip: Die neueste Aktion liegt oben und wird mit pop() zuerst entnommen.

Erwartungshorizont zu Aufgabe b)
public String rueckgaengig() {
    if (aktionen.isEmpty()) {
        return "";
    }
    String a = aktionen.pop();
    wiederholen.push(a);
    return a;
}
Erwartungshorizont zu Aufgabe c)

Pro: begrenzter Speicherbedarf, in der Praxis werden selten mehr als 100 Schritte zurückgenommen. Contra: Die älteste Aktion liegt ganz unten im Stapel und ist nur erreichbar, wenn man alle 100 Aktionen auf einen Hilfsstapel umlädt und wieder zurücklädt — bei jeder neuen Aktion. Alternativ müsste eine dynamische Reihung verwendet werden (append für neue Aktionen, delete(0) für die älteste). Ergebnis: Die Begrenzung ist sinnvoll, sollte aber nicht mit einem reinen Stapel umgesetzt werden.