Stack: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(11 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
[[Kategorie:Informatik-Q1]]
[[Kategorie:Informatik-Q1]]
[[Kategorie:Datenstrukturen(IF)]]
[[Kategorie:Datenstrukturen(IF)]]
<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) ''


= Schnittstellenbeschreibung (Zentralabitur) =
= Schnittstellenbeschreibung (Zentralabitur) =
Download als PDF: [[Medium:Stack-Schnittstelle-Zentralabitur-2012.pdf|Stack Schnittstellenbeschreibung (PDF)]]
Download als PDF: [[Medium:Dokumentation Stack Abi2017.pdf|Stack Schnittstellenbeschreibung (PDF)]]




Zeile 15: Zeile 25:




Anfrage '''isEmpty(): boolean'''
Anfrage '''boolean isEmpty()'''


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




Anfrage '''top(): ContentType'''
Anfrage '''ContentType top()'''


Die Anfrage liefert das oberste Stapelobjekt. Der Stapel bleibt unverändert. Falls der Stapel leer ist, wird null zurückgegeben.
Die Anfrage liefert das oberste Stapelobjekt. Der Stapel bleibt unverändert. Falls der Stapel leer ist, wird null zurückgegeben.
Zeile 42: Zeile 52:
* Auf den Stapel eine Karte drauflegen: Methode '''push(neueKarte)'''
* Auf den Stapel eine Karte drauflegen: Methode '''push(neueKarte)'''
* Man kann abfragen, ob der Stapel überhaupt eine Karte enthält: Methode '''isEmpty()'''
* Man kann abfragen, ob der Stapel überhaupt eine Karte enthält: Methode '''isEmpty()'''
= Objektdiagramm eines Stacks =
[[Datei:Stack ab Abi2017.png]]
Der Stack selber hat nur das eine Attribut <code>'''head'''</code>, 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 <code>StackNodes</code> untereinander ja verbunden sind (jeder <code>StackNode</code> hat ein Attribut <code>nextNode</code>, in dem eine Referenz auf das darunter liegende <code>StackNode</code>-Objekt gespeichert ist).
=Implementierung=
Für die Implementierung der Klasse Stack wird die interne Klasse [[StackNode]] benutzt.
<code>
  public class Stack<ContentType> {
        // der oberste Node eines Stacks
        private StackNode head;
       
        public Stack() {
          head = null;
        }
        public boolean isEmpty() {
          return (head == null);
        }
        public void push(ContentType pContent) {
          if (pContent != null) {
              StackNode node = new StackNode(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;
          }
        }
  }
</code>


= Verwendung von Stacks =
= Verwendung von Stacks =
Zeile 100: 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<>();                     
     Stack<Buch> hilfsStack = new Stack<Buch>();                     
     int ergebnis = 0;                                   
     int ergebnis = 0;                                   
     while(pStack.isEmpty() == false){
     while(pStack.isEmpty() == false){
Zeile 116: 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;
     Stack<Buch> hilfsStack = new Stack<>();
     Stack<Buch> hilfsStack = new Stack<Buch>();
     while (pStack.isEmpty() == false) {
     while (pStack.isEmpty() == false) {
       Buch oberstesBuch = pStack.top();
       Buch oberstesBuch = pStack.top();
Zeile 138: 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<>();
     Stack<Buch> hilfsStack = new Stack<Buch>();
     while (!pStack.isEmpty()) {
     while (!pStack.isEmpty()) {
       Buch oberstesBuch = pStack.top();
       Buch oberstesBuch = pStack.top();
Zeile 160: 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<>();
     Stack<Buch> hilfsStack = new Stack<Buch>();
     while (!pStack.isEmpty()) {
     while (!pStack.isEmpty()) {
       hilfsStack.push(pStack.top());
       hilfsStack.push(pStack.top());
Zeile 178: 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<>();
     Stack<Buch> hilfsStack = new Stack<Buch>();
     while (!pStack.isEmpty()) {
     while (!pStack.isEmpty()) {
       hilfsStack.push(pStack.top());
       hilfsStack.push(pStack.top());
Zeile 194: 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<>();
     Stack<Buch> ergebnis= new Stack<Buch>();
     while (!s1.isEmpty() && !s2.isEmpty()){
     while (!s1.isEmpty() && !s2.isEmpty()){
       ergebnis.push(s1.top());
       ergebnis.push(s1.top());
Zeile 218: Zeile 180:
     return ergebnis;
     return ergebnis;
  }
  }
</code>
= Objektdiagramm eines Stacks =
[[Datei:Stack ab Abi2017.png]]
Der Stack selber hat nur das eine Attribut <code>'''head'''</code>, 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 <code>Nodes</code> untereinander ja verbunden sind (jeder <code>Node</code> hat ein Attribut <code>next</code>, in dem eine Referenz auf das nächste <code>Node</code>-Objekt gespeichert ist).
=Implementierung=
Für die Implementierung der Klasse Stack wird die Klasse '''[[Node]]''' benutzt, für die das Klassendiagramm rechts gilt.
[[File:Klassendiagramm-Node.png|thumb|Klassendiagramm Node|322px]]
<code>
  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;
          }
        }
  }
  </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;
          }
       }
 }