Stack: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 4: Zeile 4:
[[Kategorie:Datenstrukturen(IF)]]
[[Kategorie:Datenstrukturen(IF)]]
<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>
<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>
=Erklärvideos=
[https://youtu.be/Z80NV64CGHI Methoden für die Klasse Stack programmieren]
=Fachbegriffe=
oben drauflegen (push), von oben wegnehmen (pop), ist leer, den obersten anschauen (top)


= Funktionsweise =
= Funktionsweise =
''"Ein Stapel (Stack) kann eine beliebige Menge von gleich langen Informationsstrukturen (Objekte) aufnehmen und gibt diese, in entgegengesetzter Reihenfolge zur Aufnahme, wieder zurück." (Wikipedia) ''
''"Ein Stapel (Stack) kann eine beliebige Menge von gleich langen Informationsstrukturen (Objekte) aufnehmen und gibt diese, in entgegengesetzter Reihenfolge zur Aufnahme, wieder zurück." (Wikipedia) ''


Zeile 56: Zeile 64:
== Beispiel: Methode Anzahl ==
== Beispiel: Methode Anzahl ==


<code>
<code>
  public int anzahl(Stack<Buch> pStack){
  public int anzahl(Stack<Buch> pStack){
     Stack<Buch> hilfsStack = new Stack<Buch>();                     
     Stack<Buch> hilfsStack = new Stack<Buch>();                     
Zeile 72: Zeile 80:
     }
     }
   }
   }
</code>
</code>


== Methode Enthaelt==
== Methode Enthaelt==
<code>
<code>
  public boolean enthaelt(Stack<Buch> pStack, Buch pBuch){
  public boolean enthaelt(Stack<Buch> pStack, Buch pBuch){
     boolean ergebnis = false;
     boolean ergebnis = false;
Zeile 94: Zeile 102:
     }
     }
     return ergebnis;
     return ergebnis;
  }
  }</code>
 
</code>


== Methode Löschen ==
== Methode Löschen ==


<code>
<code>
  public void loeschen(Stack<Buch> pStack, Buch pBuch) {
  public void loeschen(Stack<Buch> pStack, Buch pBuch) {
     Stack<Buch> hilfsStack = new Stack<Buch>();
     Stack<Buch> hilfsStack = new Stack<Buch>();
Zeile 116: Zeile 122:
     }
     }
  }
  }
</code>
</code>


== Methode Unterstes Element==
== Methode Unterstes Element==
Die folgende Methode löscht das unterste Buch aus einem Stack und gibt es zurück.
Die folgende Methode löscht das unterste Buch aus einem Stack und gibt es zurück.
<code>
<code>
  public Buch unterstesBuch(Stack<Buch> pStack){
  public Buch unterstesBuch(Stack<Buch> pStack){
     Stack<Buch> hilfsStack = new Stack<Buch>();
     Stack<Buch> hilfsStack = new Stack<Buch>();
Zeile 134: Zeile 140:
     return dasUnterste;
     return dasUnterste;
  }
  }
</code>
</code>


== Methode Buch unten einfügen==
== Methode Buch unten einfügen==
<code>
<code>
  public void buchUntenEinfuegen(Stack<Buch> pStack, Buch pBuch){
  public void buchUntenEinfuegen(Stack<Buch> pStack, Buch pBuch){
     Stack<Buch> hilfsStack = new Stack<Buch>();
     Stack<Buch> hilfsStack = new Stack<Buch>();
Zeile 150: Zeile 156:
     }
     }
  }
  }
</code>
</code>


== Methode mischen==
== Methode mischen==
<code>
<code>
  public Stack<Buch> mischen(Stack<Buch> s1, Stack<Buch> s2){
  public Stack<Buch> mischen(Stack<Buch> s1, Stack<Buch> s2){
     Stack<Buch> ergebnis= new Stack<Buch>();
     Stack<Buch> ergebnis= new Stack<Buch>();
Zeile 186: Zeile 192:
[[File:Klassendiagramm-Node.png|thumb|Klassendiagramm Node|322px]]
[[File:Klassendiagramm-Node.png|thumb|Klassendiagramm Node|322px]]


<code>
<code>
   public class Stack<ContentType> {
   public class Stack<ContentType> {
         // der oberste Node eines Stacks
         // der oberste Node eines Stacks
Zeile 221: Zeile 227:
         }
         }
   }
   }
</code>
</code>

Aktuelle Version vom 6. September 2022, 21:41 Uhr

Diese Seite entspricht dem Abi 17 (und folgenden)

Erklärvideos

Methoden für die Klasse Stack programmieren

Fachbegriffe

oben drauflegen (push), von oben wegnehmen (pop), ist leer, den obersten anschauen (top)

Funktionsweise

"Ein Stapel (Stack) kann eine beliebige Menge von gleich langen Informationsstrukturen (Objekte) aufnehmen und gibt diese, in entgegengesetzter Reihenfolge zur Aufnahme, wieder zurück." (Wikipedia)

Schnittstellenbeschreibung (Zentralabitur)

Download als PDF: Stack Schnittstellenbeschreibung (PDF)


Konstruktor Stack()

Ein leerer Stapel wird erzeugt. Objekte, die in diesem Stapel verwaltet werden, müssen vom Typ ContentType sein.


Anfrage boolean isEmpty()

Die Anfrage liefert den Wert true, wenn der Stapel keine Objekte enthält, sonst liefert sie den Wert false.


Auftrag push (ContentType pContent)

Das Objekt pContent wird oben auf den Stapel gelegt. Falls pContent gleich null ist, bleibt der Stapel unverändert.


Auftrag pop()

Vorher: Der Stapel ist nicht leer.

Nachher: Das zuletzt eingefügte Element ist aus dem Stapel entfernt.


Anfrage ContentType top()

Die Anfrage liefert das oberste Stapelobjekt. Der Stapel bleibt unverändert. Falls der Stapel leer ist, wird null zurückgegeben.

Veranschaulichung: Stapel von Spielkarten

Einen Stack kann man sich als einen Stapel von Spielkarten vorstellen. Für den Kartenstapel sind folgende Handlungen möglich:

  • Die oberste Karte anschauen: Methode top()
  • Die oberste Karte wegnehmen: Methode pop()
  • Auf den Stapel eine Karte drauflegen: Methode push(neueKarte)
  • Man kann abfragen, ob der Stapel überhaupt eine Karte enthält: Methode isEmpty()

Verwendung von Stacks

Um mit den Elementen eines Stacks sinnvoll arbeiten zu können, muss man sie nach und nach vom Stack "runternehmen".

Damit man den Stack dabei nicht zerstört, muss man die runtergenommenen Elemente auf einen Hilfs-Stack ablegen und nach der Bearbeitung wieder zurückschichten.

Klassendiagramm der Klasse Buch

Die Verwendung von Stacks wird hier aufgezeigt für Stacks, die Objekte vom Typ Buch enthalten (vgl. Klassendiagramm rechts)

Beispiel: Methode Anzahl


public int anzahl(Stack<Buch> pStack){
   Stack<Buch> hilfsStack = new Stack<Buch>();                     
   int ergebnis = 0;                                   
   while(pStack.isEmpty() == false){
      Buch oberstesBuch = pStack.top();
      hilfsStack.push(oberstesBuch);
      ergebnis++;                       
      pStack.pop();
   }
   while(hilfsStack.isEmpty() == false){
      Buch oberstesBuch = hilfsStack.top();
      pStack.push(oberstesBuch);
      hilfsStack.pop();
   }
 }

Methode Enthaelt


public boolean enthaelt(Stack<Buch> pStack, Buch pBuch){
   boolean ergebnis = false;
   Stack<Buch> hilfsStack = new Stack<Buch>();
   while (pStack.isEmpty() == false) {
      Buch oberstesBuch = pStack.top();
      if (oberstesBuch.getTitel().equals(pBuch.getTitel())) {
         ergebnis = true;
      }
      hilfsStack.push(oberstesBuch);
      pStack.pop();
   }
   // Buecher auf pStack zurueck legen
   while (!hilfsStack.isEmpty()) {
      Buch oberstesBuch = hilfsStack.top();
      pStack.push(oberstesBuch);
      hilfsStack.pop();
   }
   return ergebnis;
}

Methode Löschen


public void loeschen(Stack<Buch> pStack, Buch pBuch) {
   Stack<Buch> hilfsStack = new Stack<Buch>();
   while (!pStack.isEmpty()) {
      Buch oberstesBuch = pStack.top();
      if (oberstesBuch.getTitel().equals(pBuch.getTitel())) {
         pStack.pop();
      }
      hilfsStack.push(oberstesBuch);
   }
   while (!hilfsStack.isEmpty()){
      Buch oberstesBuch = hilfsStack.top();
      pStack.push(oberstesBuch);
      hilfsStack.pop();
   }
}

Methode Unterstes Element

Die folgende Methode löscht das unterste Buch aus einem Stack und gibt es zurück.


public Buch unterstesBuch(Stack<Buch> pStack){
   Stack<Buch> hilfsStack = new Stack<Buch>();
   while (!pStack.isEmpty()) {
      hilfsStack.push(pStack.top());
      pStack.pop();
   }
   Buch dasUnterste = hilfsStack.top();
   while (!hilfsStack.isEmpty()) {
      pStack.push(hilfsStack.top());
      hilfsStack.pop();
   }
   return dasUnterste;
}

Methode Buch unten einfügen


public void buchUntenEinfuegen(Stack<Buch> pStack, Buch pBuch){
   Stack<Buch> hilfsStack = new Stack<Buch>();
   while (!pStack.isEmpty()) {
      hilfsStack.push(pStack.top());
      pStack.pop();
   }
   pStack.push(pBuch);
   while (!hilfsStack.isEmpty()) {
      pStack.push(hilfsStack.top());
      hilfsStack.pop();
   }
}

Methode mischen


public Stack<Buch> mischen(Stack<Buch> s1, Stack<Buch> s2){
   Stack<Buch> ergebnis= new Stack<Buch>();
   while (!s1.isEmpty() && !s2.isEmpty()){
      ergebnis.push(s1.top());
      s1.pop();
      ergebnis.push(s2.top());
      s2.pop();
   }
   // jetzt den Rest von s1 (wenn es einen gibt)
   while (!s1.isEmpty()){
      ergebnis.push(s1.top());
      s1.pop();
   }
   // jetzt den Rest von s2 (wenn es einen gibt)
   while (!s2.isEmpty()){
      ergebnis.push(s2.top());
      s2.pop();
   }
   return ergebnis;
}

Objektdiagramm eines Stacks

Stack ab Abi2017.png

Der Stack selber hat nur das eine Attribut head, er kann demnach nur auf obersten Knoten direkt zugreifen. Dies reicht aus, da Stack-Operationen (Anschauen, Hinzufügen, Löschen) immer nur oben möglich sind und die Nodes untereinander ja verbunden sind (jeder Node hat ein Attribut next, in dem eine Referenz auf das nächste Node-Objekt gespeichert ist).

Implementierung

Für die Implementierung der Klasse Stack wird die Klasse Node benutzt, für die das Klassendiagramm rechts gilt.

Klassendiagramm Node

 public class Stack<ContentType> {
       // der oberste Node eines Stacks
       private Node<ContentType> head;
        
       public Stack() {
          head = null;
       }

       public boolean isEmpty() {
          return (head == null);
       }

       public void push(ContentType pContent) {
          if (pContent != null) {
             Node<ContentType> node = new Node<ContentType>(pContent);
             node.setNext(head);
             head = node;
          }
       }

       public void pop() {
          if (!isEmpty()) {
             head = head.getNext();
          }
       }

       public ContentType top() {
          if (!this.isEmpty()) {
             return head.getContent();
          } else {
          return null;
          }
       }
 }