Lineare Strukturen #2 - Stack

  • Quadratisch, Praktisch, Gut - nicht nur bei Ritter Sport - Stapeln ist die Lösung

    Im Folgenden soll der abstrakte Datentyp Stack genauer beleuchtet werden.


    Was ist ein Stack?

    Man kann Stack sehr schön mit "Stapel" übersetzen. In einem Stack werden Objekte nach dem Last-In-First-Out-Prinzip verwaltet. Das heißt, dass das Objekt, welches als letztes hinzugefügt wurde auch wieder als ersten entnommen werden wird. Ähnlich wie bei der Queue werden wir mit einem Interface IStack arbeiten, um unabhängig von einer Implementierung zu sein. Das Beispiel ist auch hier schulgerecht und darf von euch frei verwendet werden. Der Stack ist generisch gehalten.


    Veranschaulichung



    Der Stack lässt sich in Java wie folgt modellieren:



    Implementierung eines Stacks


    Modellierung

    Wenn wir die Implementierung modellieren könnte sie am Ende so aussehen:


    Implementierung

    In der Implementierung ist es vorgesehen, dass ein Stack immer sein oberstes Element kennt. Jedes Element wird durch einen Knoten (engl. Node) repräsentiert. Jeder Knoten kennt dabei seinen Nachfolger. Wann immer ein neues Element hinzugefügt wird, wird das aktuell oberste Element zum Nachfolger des neuen Elements und das neue Element wird das oberste. Letzteres gilt auch, wenn der Stack leer ist. Wenn ein Element entfernt wird, wird der Nachfolger des obersten Elements zum obersten Element und das vorherige oberste Element verschwindet aus der Struktur.


    Die Verwendung sähe dann so aus:


    Ich hoffe dass ich euch auch den Stack näher bringen konnte ;)


    Mit freundlichen Grüßen

    Nathalie

Teilen

Kommentare 13

  • Bei Stacks denke ich an eine nicht schwierige, aber nette Übungsaufgabe: Man beschreibe, wie sich eine Queue mithilfe von zwei Stacks realisieren lässt. Das ist in diesem Zusammenhang vielleicht interessant, weil der vorherige Eintrag Queues behandelt.

    • Ich plante Übungsaufgaben am Ende der dritten linearen Struktur (Listen). Danach darf man dann unter anderem Methoden wie #concat selbst implementieren ;)

  • Du könntest auch noch Bezug zum Stack, den es auch im Prozessor gibt, herstellen.

    • Ich möchte versuchen in dieser Reihe sehr schulnah und simpel an Grundprinzipien zu entwickeln. Spezielle Anwendunsgfälle oder komplexere Zusammenhänge würde ich wenn überhaupt woanders klären.

    • Verständlich. Mich macht das immer traurig, wenn jemand "schulnah" im Zusammenhang mit Informatik sagt - ich habe kein Informatik ;(

    • Du hast ja mich :P

    • Naja, ich fände es nicht wegen dem Stoff gut, sondern, weil ich dann etwas, was mich interessiert, im Unterricht durchnehme und wegen den fast hinterhergeworfenen Einsen :P

    • Das geht mir genauso. Ich habe Informatik zum Glück sogar als Leistungskurs :) Bisher haben wir zwar eigentlich nur die Dinge durchgenommen, die ich schon alle kenne, aber das ist mir egal. Hauptsache das Interesse besteht.


      Aber mal ne andere Frage: Kann es sein, dass du dich an den vorgegebenen Implementationen von Klassen für das Zentralabitur (NRW) orientierst? Die Klassen kommen mir ziemlich bekannt vor :D

  • "Implementierung einer Queue"
    gewollt?