06 – Warteschlange und Stapel

 

Stapel (stack)

Ein Stapel speichert Daten nach dem Prinzip “last in-first out”, das heißt das Element, das zuletzt auf den Stapel gelegt wurde, wird als erstes wieder heruntergenommen.
Für diesen Zweck sind im Datentyp Stapel zwei Operationen definiert: push(Data) und pop()

Beispiel:

Realisierung mit dem Datentyp “Liste”:
push(Data)-Neues Element mit dem Inhalt “Data” wird hinter dem Listenkopf (sentinel) angefügt.
pop()-Das erste Element hinter dem Listenkopf wird aus der Liste herausgenommen.

Stapel werden zum Beispiel von Windows beim Aufruf von Unterprogrammen benutzt. Auch bei der Kontrolle von verschachteltem Code (zum Beispiel Bulletin-Board Code) sind sie nützlich.

Warteschlange (queue)

Eine Warteschlange speichert Daten nach dem Prinzip “first in-first out”, das heißt derjenige, der sich zuerst angestellt hat, kommt auch zuerst dran.
Für diesen Zweck sind im Datentyp Warteschlange zwei Operationen definiert: push(Data) oder append(Data) und pop() oder get()

Beispiel:

Realisierung mit dem Datentyp “doppelt verkettete Liste”, alle Operationen können mit dem Aufwand O(1) realisiert werden.

Warteschlangen werden häufig genutzt wie im realen Leben, zum Beispiel gibt es eine Warteschlange für Druckaufträge oder eine Warteschlange für mehrere nacheinander auszuführende Prozesse im Betriebssystem.

Implementierung in Java

Stapel:

public class Stack
{
	private class StackElement
	{ // Klasse zur Verwaltung der Listeneinträge
        private int value;
        private StackElement next;

        public StackElement(int value)
		{ // Konstruktor
            this.value = value;
            this.next = null;
        }

        public void setNext(StackElement next)
		{ // setzt Adresse des nächsten Elements auf übergebenen Wert
            this.next = next;
        }

        public int getValue()
		{ // gibt "Data" des Elements zurück
            return value;
        }

        public StackElement getNext()
		{ // gibt die Adresse des nächsten Elements zurück
            return this.next;
        }
    }

    private StackElement top; // Kopf

    public Stack()
	{ // Konstruktor der Hauptklasse
        this.top = null;
    }

    public boolean isEmpty()
	{ // gibt true zurück, wenn leer
        return (top == null);
    }

    public void push(int value)
	{ // fügt neues Element am Anfang ein
        StackElement tmp = new StackElement(value);
        tmp.setNext(top);
        this.top = tmp;
    }

    public void pop()
	{ // entfernt Element
        if (this.top == null)
            return;
        this.top = top.getNext();
    }

    public int top()
	{ // gibt Wert des Kopfes zurück
        return top.getValue();
    }
}

Warteschlange:

public class Queue
{
	private LinkedList list;

	public Queue()
	{ // Queue Konstruktor
		list = new LinkedList();
	}

	public boolean isEmpty()
	{ // gibt 1 zurück, wenn leer
		return (list.size() == 0);
	}

	public void enqueue(Object item)
	{ // fügt Element in Warteschlange ein
		list.add(item);
	}

	public Object dequeue()
	{ // nimmt Element aus Warteschlange heraus
		Object item = list.get(1);
		list.remove(1);
		return item;
	}

	public Object peek()
	{ // liest Element, ohne es aus der Liste zu entfernen
		return list.get(1);
	}
}

Ähnliche Artikel

Kommentar verfassen