Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

public interface Queue {
public int size();
public boolean isEmpty();
public Object front() throws EmptyQueueException;
public void enqueue(Object o);
public Object dequeue() throws EmptyQueueException;
}

public interface Stack {
public int size();
public boolean isEmpty();
public Object top() throws EmptyStackException;
public void push(Object o);
public Object pop() throws EmptyStackException;
}

Direkte Anwendungen:
Page-visited history im Web browser
Undo-Sequenz im Text-editor
Kette von Methodenaufrufen in der Java Virtual Machine

Indirekte Anwendungen
Hilfsdatenstruktur für Algorithmen
Bestandteil anderer Datenstrukturen

EmptyQueueException bei dem Versuch front() oder dequeue() auf leere Queue.

(2,4)

Direkt:
- Warteschlangen
- Drucker
- Multiprogrammierung

Indirekt:
- Hilfsdatenstruktur für Algorithmen
- Bestandteil anderer Datenstrukturen

Allgemein:
- Größe n
- f ist Index auf erstes Element
- r ist Zeiger auf letztes Element + 1 (immer leer!)

Je nach Startkonfiguration hat man eine normale Konfiguration (f,r). Die wrapped-around Konfiguration sind die Zeiger vertauscht (r,f), da die Elemente in den Feldern n+1 in 1 abgelegt werden. Die aktuell freie Position ist dann n-f+r %n.

Algorithm size()
return (N-f+r) mod N

Algorithm isEmpty()
return (f==r)

Algorithm enqueue(o)
if size() = N − 1 then throw FullQueueException
else Q[r] ← o r ← (r + 1) mod N

Algorithm dequeue()
if isEmpty() then throw EmptyQueueException
else
o ← Q[f]
f ← (f + 1) mod N
return o