14.81 Aufgaben mit Stacks

Auf dieser Seite betrachten wir zunächst einmal allgemeine Aufgaben zum Thema "Stacks". Diese Aufgaben stammen teilweise aus Informatik-Büchern, teilweise aus Vorlesungsmitschriften. Abituraufgaben zum Thema werden auf der nächsten Seite vorgestellt.

Kopieren eines Stacks

Betrachten Sie den folgenden Quelltext:

public class Test
{
    Stack s1;
    
    public Test()
    {
       s1 = new Stack();
       s1.push(new Bruch(3,4));
       s1.push(new Bruch(5,8));
       s1.push(new Bruch(1,7));
      
       show(s1);
       show(s1);
    }
    
    public void show(Stack s)
    {
       while (!s.empty())
       {
          Bruch b = (Bruch) s.top();
          b.show();
          s.pop();
       }
    }
}

Das Stack-Objekt s1 speichert hier drei Objekte der Klasse Bruch, und die show-Methode gibt die Bruch-Objekte in der Konsole aus. Dazu ruft sie die show-Methode der Klasse Bruch auf.

Im Konstruktor von Test wird die show-Methode der Klasse Test zweimal aufgerufen, nachdem der Stack aufgebaut wurde. Damit wollte ich eine wichtige Sache zeigen. Hier die Ausgabe des Konsolenfensters:

1/7
5/8
3/4

Der Stack wird nur einmal angezeigt, obwohl show zweimal aufgerufen wurde. Woran liegt das?

Schauen Sie sich die Arbeitsweise der show-Methode näher an. Das oberste Element wird angezeigt, dann wird es mit pop vom Stack gelöscht. Wenn das letzte Stack-Element angezeigt wurde, ist der Stack leer. Ein zweiter Aufruf von show zeigt dann nur den leeren Stack.

Wenn wir den Stack zweimal hintereinander ausgeben wollen, müssen wir also vorher eine Kopie des Stacks anfertigen. Dazu benötigen wir einen zweiten Stack. Also erweitern wir unseren Quelltext entsprechend:

public class Test
{
    Stack s1, s2;

    public Test()
    {
       s1 = new Stack();
       s1.push(new Bruch(3,4));
       s1.push(new Bruch(5,8));
       s1.push(new Bruch(1,7));
       
       s2 = new Stack();
       kopiere(s1,s2);
      
       show(s1);
       show(s2);
    }
    
    public void kopiere(Stack quelle, Stack ziel)
    {
    
    }
    
    public void show(Stack s)
    {
       while (!s.empty())
       {
          Bruch b = (Bruch) s.top();
          b.show();
          s.pop();
       }
    }
}

Und damit wären wir auch schon bei der ersten "richtigen" Aufgabe mit Stacks:

Vervollständigen Sie die Methode kopiere!

Lösungshinweise

Verbinden von zwei Stacks

Wir wollen für die Klasse Test jetzt eine Methode verbinde schreiben, die zwei Stacks, die verbinde als Parameter übergeben werden, zu einem neuen Stack zusammenbaut, der dann als Stack zurück gegeben wird.

Betrachten Sie dazu folgenden Quelltext:

import java.util.ArrayList;

public class Test
{
    Stack s1, s2;

    public Test()
    {
       s1 = new Stack();
       s1.push(new Bruch(1,4));
       s1.push(new Bruch(1,8));
       s1.push(new Bruch(1,7));
       
       s2 = new Stack();
       s2.push(new Bruch(2,4));
       s2.push(new Bruch(2,8));
       s2.push(new Bruch(2,7));
       
       Stack s12 = verbinde(s1,s2);
       System.out.println("Stapel 1+2:");
       show(s12);
    }
    
    public Stack verbinde(Stack teil1, Stack teil2)
    {
    }
   
    public void show(Stack s)
    {
    }
}

Der Stack s2 soll mit dem Stack s1 verbunden werden, so dass sich in dem resultierenden Stack der alte s1 unten befindet und der zweite Stack s2 oben. Die Reihenfolge innerhalb der beiden Stacks soll aber erhalten bleiben.

Aus dem Stack s1

1/7
1/8
1/4

und dem Stack s2

2/7
2/8
2/4

ergibt sich nach Aufrufen von verbinde folgender Gesamtstack s1:

2/7
2/8
2/4
1/7
1/8
1/4

Und damit wären hätten wir die zweite Aufgabe mit Stacks formuliert:

Vervollständigen Sie die Methode verbinde!

Lösungshinweise

Zwei weitere Aufgaben

public boolean gleich (Stack s1, Stack s2)

 public boolean enthalten(Stack a, Bruch x)