Keller / Stack

Basiert auf LIFO-Verfahren.

Ein Keller (oder Stack) kann man sich wie eine Stapel vorstellen. Der Keller funktioniert nach dem Last in First out Prinzip (LIFO-Prinzip).

Ein Keller ist eine dynamische Datenstruktur die implementiert werden muss. Alle dynamischen Datenstrukturen sind über dem Abstraktionsniveau einer Programmiersprache und deshalb müssen alle dynamische Datenstrukturen erstmal mit Hilfe einer statischen Datenstruktur (Array) implementiert werden.

Mann kann einen Keller auch mit einer verketteten Liste oder halt mit einem Array implementieren.

Ein neues Element kann mit dem Befehl push() hinten reingeschoben werden.

Mit dem Befehl pop() wird das hintere Element gelöscht und ausgegeben. Der Befehl peek() ermöglicht das lesen des hinteren Elements ohne das dieses aus dem Keller entfernt wird.

In einem Stack/Keller kann immer nur auf das obere bzw. hintere Element zugegriffen werden. Deshalb sagt man, dass ein Keller nach dem Last In First Out Prinzip funktioniert.

Operationen:

-       Schreiben: push(Object o) Einfügen durch Anhängen von Elementen AM ENDE

-       Löschen: pop() – Entfernen  AM ENDE und Rückgabe

-       Lesen: peek() – Liefert Endelement zurück, ohne zu entfernen

 

/*

* Ein Keller ist eine dynamische Datenstruktur

* Sie muss deshalb mit einer statischen

* Datenstruktur implementiert werden.

* Das liegt daran, dass dynamische

* Datenstrukturen über dem Abstraktions-

* niveau der Programmiersprachen liegen.

* Grundoperationen sind:

*             – push

*             – peek

*             – pop

* Grundprinzip:

*             – Last in First out

*/

public class KellerImplementation

{

void push(Object o)

{

list.addFirst(Object o);

}

Object peek()

{

return list.getFirst();

}

Object pop()

{

Node temp = peek();            //zugreifen

list.removeFirst()            //löschen

return temp;                        //zurückgeben

}

}