Aufbau und Funktionsweise
Auch der Stapel besteht innen aus Knoten, die aneinanderhängen. Anders als die Schlange merkt er sich aber nur einen Knoten: den obersten (head). Von dort aus zeigt jeder Knoten auf den, der unter ihm liegt.
Auf dieser Seite schaust du hinein. Als Beispiel dient ein Messenger, der neue Nachrichten oben auf einen Stapel legt.
| Teil | Was er sich merkt |
|---|---|
Stack |
head – den obersten Knoten |
StackNode |
content – das gespeicherte Objekt, nextNode – den Knoten darunter |
Der unterste Knoten hat keinen Nachfolger: Sein nextNode ist null. Einen leeren Stapel erkennt man daran, dass head auf null zeigt.
Das Klassendiagramm zeigt alle drei beteiligten Klassen, die Pfeile tragen die Namen der Verweise aus den Objektdiagrammen.
classDiagram
direction LR
class Stack {
+isEmpty() boolean
+push(pContent: Message)
+pop()
+top() Message
}
class StackNode {
+StackNode(pContent: Message)
+getNext() StackNode
+setNext(pNext: StackNode)
+getContent() Message
}
class Message {
+getUsername() String
+getText() String
+getDate() String
}
Stack --> StackNode : head
StackNode --> StackNode : nextNode
StackNode --> Message : content
Nachrichten auflegen
Die Methode push soll eine neue Nachricht auf den Stapel legen.
- Setze die Schritte im Objektdiagramm um.
- Entwirf zur Methode push der Klasse Stack einen Algorithmus in Pseudocode.
- Bereite dich darauf vor, deinen Algorithmus anhand des Objektdiagramms zu präsentieren.
Formulierungshilfe: Pseudocode
- Erzeuge ...
- Setze das Attribut / die Variable ... auf die Referenz ...
Weiterdenken: In push kommt es auf die Reihenfolge der Zuweisungen an. Was geht verloren, wenn man head zuerst auf den neuen Knoten setzt?
Nachrichten lesen und entfernen
Die Methode top soll die oberste Nachricht zurückgeben. Die Methode pop soll die oberste Nachricht vom Stapel entfernen.
- Setze die Schritte im Objektdiagramm um.
- Entwirf zu den Methoden pop und top einen Algorithmus in Pseudocode.
- Bereite dich darauf vor, deinen Algorithmus anhand des Objektdiagramms zu präsentieren.
Grenzfälle: der leere Stapel
Bei der Schlange brauchte das Einreihen in eine leere Schlange einen eigenen Fall. Wie ist das beim Stapel?
- Setze beide Schritte im Objektdiagramm um.
- Prüfe deine Algorithmen von oben an diesen beiden Fällen. Brauchen sie eine zusätzliche Fallunterscheidung?
- Was müssen top und pop tun, wenn der Stapel schon leer ist? Schlag in der Dokumentation nach und ergänze deine Algorithmen.