Interface Queue?
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 int size();
public boolean isEmpty();
public Object front() throws EmptyQueueException;
public void enqueue(Object o);
public Object dequeue() throws EmptyQueueException;
}
Tags: Queue
Quelle:
Quelle:
Interface Stack?
public interface Stack {
public int size();
public boolean isEmpty();
public Object top() throws EmptyStackException;
public void push(Object o);
public Object pop() throws EmptyStackException;
}
public int size();
public boolean isEmpty();
public Object top() throws EmptyStackException;
public void push(Object o);
public Object pop() throws EmptyStackException;
}
Anwendungen für Stack?
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
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
Exception für Queue?
EmptyQueueException bei dem Versuch front() oder dequeue() auf leere Queue.
Tags: Queue Exception
Quelle:
Quelle:
Wie sieht eine Queue nach folgenden Operation aus?
enqueue(5), enqueue(4), enqueue(4), dequeue(), dequeue(), enqueue(2)
enqueue(5), enqueue(4), enqueue(4), dequeue(), dequeue(), enqueue(2)
(2,4)
Wo werden Queues angewendet?
Direkt:
- Warteschlangen
- Drucker
- Multiprogrammierung
Indirekt:
- Hilfsdatenstruktur für Algorithmen
- Bestandteil anderer Datenstrukturen
- Warteschlangen
- Drucker
- Multiprogrammierung
Indirekt:
- Hilfsdatenstruktur für Algorithmen
- Bestandteil anderer Datenstrukturen
Beschreiben die normale und die wrapped-around Konfiguration einer Queue!
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.
- 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.
Beschreibe die Funktionen size(), isEmpty() und enqueue(), dequeue mit Exceptions bei einer Queuelänge von 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
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
