Stacks und Queues - Fachbereich Mathematik und Informatik

Stacks und Queues
Behälter, Stacks, Stackpaare, DeRekursivierung, Ausdrucksauswertung,
FORTH, Postscript, Queues, Kanäle,
Producer-Consumer
Behälter sind ...
... Sammlungen gleichartiger Objekte
¨ Operationen
n
Objekte
¨
¨
¨
n
¨
Objekte zählen
ein Objekt suchen
mehrere Behälter
¨
¨
¨
Prakt. Informatik II
aufnehmen (add)
löschen (remove)
suchen
Behälter durchlaufen, um z.B.
¨
n
mit Behältern:
zu einem zusammenfügen
Behälter kopieren
Teilbehälter bilden
© H. Peter Gumm, Philipps-Universität Marburg
Mögliche Merkmale von Behälter
n
keine Reihenfolge:
¨
¨
n
mit Standardreihenfolge:
¨
¨
n
¨
Maps
Arrays
mit Einfüge/Entnahmereihenfolge:
¨
¨
Prakt. Informatik II
Bäume
Listen
mit direktem Zugriff:
¨
n
Mengen
Bags
Stacks
Queues
© H. Peter Gumm, Philipps-Universität Marburg
Behälter mit Zugriffsreihenfolge
¨
Ein Stapel (engl.: Stack) von Briefen oder Tellern
n
n
¨
Ein Schlange von Personen an der Kasse
n
n
¨
Man greift immer nur den obersten
Das ist der zuletzt abgelegte
Stack
Der vorderste kommt zuerst dran
Der am längsten in der Schlange steht
Eine Schlange am Flugschalter
n
n
Der vorderste kommt zuerst dran, aber...
Die Besatzung darf sich vordrängeln,
sie hat Priorität
Set
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Stack - Stapel
n
direkter Zugriff nur auf letztes
eingefügte Element
¨
Last in – First Out (LIFO)
n
n
n
Manche Leute sagen: „Keller“
¨
n
Stapel von Tellern
Stapel von Briefen
h
pus
po
p
Zuletzt eingelagerte Kartoffeln
werden zuerst gegessen
Stacks sind sehr wichtige
Datenstrukturen der Informatik
¨
¨
Statt insert und remove sagt man
push und pop
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Stack - Spezifikation
n
n
n
n
LIFO-Behälter von Objekten
Sort – Stack S von Objekten
Operationen:
¨ push : Stack × Object → Stack
¨ pop : Stack → Stack
¨ emptyStack : → Stack
¨ top : Stack → Object
¨ isEmpty : Stack → boolean
Gleichungen
¨
¨
¨
¨
top(push(s,e)) = e
pop(push(s,e))= s
isEmpty(emptyStack)=true
isEmpty(push(s,e)) = false
E getNext() { E o = top(); pop(); return o; }
Prakt. Informatik II
Stack
Stack
«constructor»
«constructor»
veränderbarer
++Stack()
Stack()
«mutatoren»
«mutatoren»
++void
voidpush(Object
push(Object) )
++void
voidpop(
pop() )
«selektoren»
«selektoren»
++Object
Objecttop(
top() )
++boolean
booleanisEmpty(
isEmpty() )
«optional»
«optional»
++Object
ObjectgetNext(
getNext() )
++int
intsize(
size() )
Typ
Stack
Stack
«constructor»
«constructor»
Ergebnistyp
++Stack
Stack()()
«operationen»
«operationen»
++Stack
Stackpush(Object
push(Object) )
++Stack
Stackpop(
pop() )
++Object
Objecttop(
top() )
++boolean
booleanisEmpty(
isEmpty() )
«optional»
«optional»
++Object
ObjectgetNext()
getNext()
++int
size()
int size()
© H. Peter Gumm, Philipps-Universität Marburg
Bounded Stack
n
Wir implementieren einen
Stack als bounded stack
¨
¨
n
d.h. mit einer begrenzten
Kapazität
Diese wird bei dem Aufruf
des Constructors bestimmt
Wir wählen die destruktive
Variante der Stackoperationen
¨
¨
void push(Element e)
void pop()
Zum aktuellen
Stack gehörend
DatenMüll
7 3 -4 5 7 1 12 -2
zeiger
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Stackpaare
stack2
stack1
n
Zwei Stacks kann man in einem Array unterbringen
¨
¨
¨
einer wächst von links nach rechts
der andere von rechts nach links
Überlauf erst, wenn Summe der Längen > Länge des Arrays
n
Optimale Ausnutzung des vorhandenen Platzes
n
Viele Programmiersprachen
¨
z.B. Pascal
verwalten so
¨
den heap
n
¨
den runtime-stack
n
n
heap
Prakt. Informatik II
dynamischer Speicher
für Methodenaufrufe
lokale Variablen
stack
Konstanten
© H. Peter Gumm, Philipps-Universität Marburg
Anwendung: Text Editor
H a
n
¨
¨
W ä
l
Cursor
einer Folge von Zeichen
einem Cursor
t
!
zur Bewegung des Cursors
zum Tippen oder Löschen
Zur Implementierung eignet sich ein
Stackpaar (links,rechts)
¨
¨
n
o
«constructor»
«constructor»
++Editor()
Editor()
«mutatoren»
«mutatoren»
++void
voidleft()
left()
++void
right(
void right() )
++void
voiddelete(
delete() )
++void
voidtype(char
type(charc)c)
«selektoren»
«selektoren»
++String
StringtoString()
toString()
Operationen
¨
n
l
Ein Texteditor besteht aus
¨
n
l
Editor
Editor
links : die Zeichen vor dem Cursor
rechts : die Zeichen rechts vom Cursor
Positionierung und Operationen
¨
¨
¨
¨
Prakt. Informatik II
left() = right.push(left.getNext())
right() = left.push(right.getNext());
delete() = left.pop()
type( c ) = left.push( c )
ä
W
W
o
l
l
a
H
links
l
t
!
rechts
© H. Peter Gumm, Philipps-Universität Marburg
Auswertung rekursiver Methoden
n
Beim Eintritt
¨
n
Sichere alle lokalen Variablen
und Parameter auf dem Stack
Nach Beendigung
¨
Lade sie wieder vom Stack
void binär(int n){
if (n<2) schreibe(n);
else{
binär(n/2);
schreibe(n%2);
}
}
push(n);
n=n/2
void binär(int n){
if (n<2) schreibe(n);
else{
binär(n/2);
schreibe(n%2);
}
}
n=getNext();
push(n);
n=n/2
void binär(int n){
if (n<2) schreibe(n);
else{
binär(n/2);
schreibe(n%2);
}
}
n=getNext();
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Auswertung von binär(13)
binär(n)
n:
n=getNext();
schreibe(n%2)
13
push(n);
n=n/2;
binär(n)
n:
6
push(n);
n=n/2;
binär(n)
6
n:
3
Prakt. Informatik II
13
n=getNext();
schreibe(n%2)
n:
6
1
13
13
6
n:
3
13
110
11
3
6
n:
1101
13
3
push(n);
n=n/2;
binär(n)
13
n=getNext();
schreibe(n%2)
n:
6
schreibe(n)
n:
1
1
13
© H. Peter Gumm, Philipps-Universität Marburg
Anwendung: De-Rekursivierung
n
Auf dem Stack abgelegte
Elemente entnimmt man in
umgekehrter Reihenfolge
n
WriteBinary nutzt dies aus:
¨
die Binärziffern werden in
falscher Reihenfolge
produziert und auf dem
Stack abgelegt
¨
dann werden sie vom
Stack entnommen und
ausgegeben
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Iterative Version mit Stack s
De-Rekursivierung
Eine linear-rekursive Funktion
f f(x)
(x)==
g(x),
g(x),falls
fallsp(x)
p(x)
h(
h(x,x,f(r(x))),
f(r(x))),sonst
sonst
In java.util.Stack :
pop() statt getNext()
Programmierung in Java
X und Y stehen für
Argument- bzw. Resultattyp
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Arithmetische Ausdrücke
n
Für die Angabe komplexer arithmetische
Ausdrücke benutzt man
¨
¨
¨
Präzedenzen
Klammern
Beispiele:
n
n
(x+1)*x + 1/x * e-(x+1) * sin (1/x )
Dies macht die technische Auswertung
kompliziert
¨
Wie berechnen Sie solche Ausdrücke mit dem
Taschenrechner?
n
¨
2*(x+x2), (x+1)2/(x2+1), ...
Geben Sie einen Algorithmus an, wie man
solche Ausdrücke auswertet
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Notation von Ausdrücken
n
Infixnotation
¨
Operationszeichen zwischen den Operanden
n
¨
x and y
(x+1)*15, x and (y or z), x / √(x+1),
sin (x +1)
Praefixnotation
¨
Operationszeichen vorne
n
¨
¨
¨
+ x 3,
* 2 15,
and x y
erfordert keine Klammern
(sofern Stelligkeit der Operatoren bekannt ist)
n
n
2*15,
erfordert Klammern
n
n
x + 3,
* + x 1 15,
and x or y z,
/ x √ + x 1, sin + x 1
aber Operator muss auf Berechnung der Argument warten
wird in der Sprache LISP verwendet.
Postfixnotation (auch UPN-umgekehrte polnische Notation)
¨
Operationszeichen hinten
n
¨
2 15 *,
x y and
erfordert keine Klammern
n
¨
x 3 +,
x 1 + 15 *,
x y z or and,
xx1+√/,
x 1 + sin
Operatoren haben gleich ihre fertigen Argumente
Prakt. Informatik II
HP 35 der erste erschwingliche
programmierbare Taschenrechner
Ein Beispielprogramm z.B. bei
www.hpmuseum.org/software/25simeq.htm
© H. Peter Gumm, Philipps-Universität Marburg
Expression-Auswertung mit Stack
n
Um eine Operation mit k-Argumenten
auszuwerten
¨
Lege k Argumente auf den Stack
n
¨
¨
n
push
Operation entnimmt oberste k Elemente
n
¨
getNext
Berechnet das Ergebnis
Legt das Ergebnis auf dem Stack ab.
Netto-Veränderung des Stacks:
¨
3 7 *
Wie zu Beginn, aber das Ergebnis ist
hinzugekommen und liegt obenauf
Prakt. Informatik II
3
7
*
7
21
21
3
anfänglicher
top
© H. Peter Gumm, Philipps-Universität Marburg
6 2 – 2 7 2 (±) * +
Postfix Ausdruck : 6 2 – 2 7 2 (±) * +
Stack-Maschinen Code: push(6) push(2) sub sqr push(7) push(2) neg mul add
top
top
2
6
top
push(6)
push(2)
top
sub
4
top
16
sqr
push(7)
push(2)
top
2
-2
7
7
16
16
neg
top
-14
16
mul
top
2
add
Netto: push(Ergebnis des Ausdrucks)
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Auswertung von UPN mit Stack
n
Zahlenwerte werden auf den Stack
gelegt (push)
¨
n
HP verwendete die Enter
- Taste
Operatoren (+, -, *, sin, xy, ... )
¨
holen ihre Argumente vom Stack
n
¨
¨
berechnen Ergebnis,
speichern das Ergebnis auf dem Stack
n
¨
pop
push
Display zeigt immer top des Stacks
Infix :
Präfix :
Postfix:
1 / sin (ln(17) + 5 * √ 3 )
(1/x)(sin(+(ln(17),* (5 , √ (3))))
17 ln 3 √ 5 * + sin 1/x
HP-35 :
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Stack Evaluierung: 17 ln 3√5 *+sin1/x
n
¨
n
17 auf den Stack legen
17.0
ln
¨
¨
¨
Einstellige Operation
Argument: top(), entfernen mit pop()
Resultat berechnen und auf Stack legen
n
Push(3)
n
√
¨
n
Der Stack
push(17)
2.8
2.8 3.0
2.8 1.7
Analog zu ln
Push(5)
2.8 1.7 5.0
n
×
¨
¨
¨
n
+
¨
n
sin
¨
n
1/x
¨
Prakt. Informatik II
Argumente: Oberste zwei Stackelemente
Argumente entfernen pop(), pop()
Ergebnis der Operation auf Stack legen
Analog zu ×
2.8 8.5
11.3
Analog zu ln, √
0.19
Analog zu ln, √, sin
5.1
© H. Peter Gumm, Philipps-Universität Marburg
FORTH – die Stacksprache
n
FORTH ist eine Programmiersprache
¨
FORTH besteht aus Kommandos
(„words“) und Operationen, die einen
Stack manipulieren
¨
Mit FORTH kann man auch
moderne Programme schreiben
n
n
n
n
objektorientiert
mit GUI
CGI, etc. ..
FORTH ist sehr maschinennah
¨
¨
Forth ist sehr effizient
Die Java-Virtual-Machine (JVM) ist eine
FORTH-ähnliche Sprache
D
FORTH Programme sind für nicht
eingeweihte schwer zu lesen
C
FORTH-Programmieren macht Spaß
http://wiki.forthfreak.net/jsforth80x25.html
Prakt. Informatik II
\ \Drei
Dreikleine
kleineFORTH-Programme:
FORTH-Programme:
\ \Euklids
Algorithmus
Euklids Algorithmus
: :UMOD
UMOD( (u1
u1u2
u2- -remainder)
remainder)
00SWAP
UM/MOD
SWAP UM/MODDROP
DROP; ;
: :GCD
GCD( (u1
u1u2
u2----gcd
gcd) )
BEGIN
BEGIN?DUP
?DUPWHILE
WHILETUCK
TUCK
UMOD
REPEAT
;
UMOD REPEAT ;
\ \das
dasgleiche
gleicherekursiv
rekursiv
: :GCD-RECURSIVE
GCD-RECURSIVE( (u1
u1u2
u2- -gcd
gcd) )
?DUP
?DUPIFIFTUCK
TUCK
UMOD
UMODRECURSE
RECURSETHEN
THEN; ;
\ \First
First20
20Fibonacci
Fibonaccinumbers
numbers
: :fibonacci
fibonacci( (----) )
001120
2000DO
DODUP
DUP. .
TUCK
TUCK++LOOP
LOOP2DROP
2DROP; ;
© H. Peter Gumm, Philipps-Universität Marburg
Eine Interaktion mit FORTH
Zahlen und Werte werden auf den Stack gelegt
23 17 39 5 66
Im interaktiven Modus beantwortet
FORTH korrekte Eingaben mit ‘ok‘
FORTH-words
.s
zeigt den Stack
.
pop das oberste
Element und zeige es an
swap
vertausche oberste Elemente
dup
dupliziere oberstes Element
drop
pop
rot
rotiere obersten drei Elemente
subtrahiere stack[top] – stack[top-1]
und ersetze sie durch Ergebnis
+, *, /, mod analog
\
beginnt Kommentarzeile
Mehrere Kommandos auf einer Zeile erlaubt.
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Programmieren in FORTH
n
Zwischen ‘:‘ und ‘;‘
können neue FORTHWorte (Programme)
definiert werden
¨
n
Das System antwortet
mit ‘compiled‘
Zuerst üben wir, wie die
Funktion berechnet wird:
¨
quadratszumme(5,6) =
5*5+6*6
n
Dann definieren wir ein
Wort für die
entsprechenden Aktionen
n
Definition beginnt mit ‘:‘
und endet mit ‘;‘
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Postscript
n
n
Seitenbeschreibungssprache von Adobe
Ergebnis
¨
Dokumente
n
n
n
mit Graphik
Mit Farbe
Beliebige Berechnungen
¨
¨
Ein Postscript Dokument
Ist ein Programm für den
Postscript Interpreter
Verwendet wurde der
Ghostscript Interpreter
von Aladdin
Arithmetik
Programme
n
Theoretisch kann man damit
beliebige Programme
schreiben
n
Postscript Dokumente sind
Programme für den
Postscript Interpreter
n
Schauen Sie z.B. einmal mit
einem Editor in eine
Postscript-Datei:
Prakt. Informatik II
Die Ausgabe des obigen
Postscript-Programms
© H. Peter Gumm, Philipps-Universität Marburg
Postscript
Prakt. Informatik II
n
n
Stackcode
Stackcode
n
n
Definitionen
Definitionen
n
n
Stackmanipulation
Stackmanipulation
n
n
Graphische
GraphischeOperationen
Operationen
n
n
for-Schleife
for-Schleife
n
n
Text
Text
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
Arithm.
Arithm.Operatoren
Operatorenu.a.
u.a.
add,
mul,
sub,
div,
mod
add, mul, sub, div, mod
beginnen
beginnenmit
mit/ /
enden
mit
def
enden mit def
Code
Codezwischen
zwischen{ {und
und} }
dup,
dup,exch,
exch,
moveto
moveto(Bezugspunkt)
(Bezugspunkt)
lineto
lineto
stroke
stroke (mache
(machesichtbar)
sichtbar)
from
kktoto{ {
from
Block
Block } } for
for
Fontauswahl
Fontauswahl
scaleto
scaletoSkalierung
Skalierung
Strings
ininrunden
Strings
runden
Klammern
Klammern
¨ show
¨ show
¨ rotate: Textrichtung
¨ rotate: Textrichtung
¨
¨
¨
¨
¨
¨
© H. Peter Gumm, Philipps-Universität Marburg
Queues
n
Behälter Datentyp
¨
¨
n
front
Warteschlange
¨
¨
n
Zugriff immer auf Objekt, das am
längsten im Behälter ist
First In First Out – FIFO
Schlange in der Bäckerei
An der Bushaltestelle
Operationen
¨
¨
¨
¨
enQueue – einfügen
deQueue – entnehmen
isEmpty – ist noch ein Element
vorhanden ?
front – nächstes Element
Prakt. Informatik II
deQueue
enQueue
© H. Peter Gumm, Philipps-Universität Marburg
Queues - Warteschlangen
n
n
FIFO Behälter
Sort – Queue Q von Objekten
n
Operationen:
¨ enQ : Queue × Object → Queue
¨ deQ : Queue → Queue
¨ emptyQueue : → Queue
¨ front : Queue → Object
¨ isEmpty : Queue → boolean
n
(Bedingte) Gleichungen
¨
isEmpty(q) ⇒ deQ(enQ(q,x)) = emptyQueue
¨
¬ isEmpty(q) ⇒ deQ(enQ(q,x)) = enQ(deQ(q),x)
¨
isEmpty(q) ⇒ front(enQ(q,x)) = x
¨
¬ isEmpty(q) ⇒ front(enQ(q,x)) = front(q)
¨
isEmpty(emptyQueue)=true
¨
isEmpty(enQ(q,x)) = false
Prakt. Informatik II
Queue
Queue
«Konstructor»
«Konstructor»
++Queue()
Ergebnistyp
Queue()
«Operationen»
«Operationen»
++Queue
QueueenQ(Object
enQ(Object) )
++Queue
QueuedeQ(
deQ() )
++Object
ObjectgetNext(
getNext() )
«Selektor»
«Selektor»
++Object
Objectfront(
front() )
++boolean
booleanisEmpty(
isEmpty() )
Queue
Queue
«Konstructor»
«Konstructor»
Veränderbarer
++Queue()
Queue()
«Mutatoren»
«Mutatoren»
++void
voidenQ(Object
enQ(Object) )
++void
voiddeQ(
deQ() )
++Object
ObjectgetNext()
getNext()
«Selektoren»
«Selektoren»
++Object
Objectfront()
front()
++boolean
booleanisEmpty(
isEmpty() )
Typ
© H. Peter Gumm, Philipps-Universität Marburg
Beispiele von Queues
n
Kanal
¨
Daten müssen in der richtigen Reihenfolge ankommen
n
n
n
Puffer (engl.: buffer)
¨
Lesen aus einer Datei
n
n
n
¨
analog
Warteschlange
¨
Printerqueue
n
n
n
Festplatte schreibt in den Puffer
Programm liest aus dem Puffer
Vorteil: Zeitliche Entkopplung
Schreiben einer Datei
n
n
Sender schreibt in den Kanal,
Empfänger liest aus dem Kanal
Programm schreibt Druckauftrag in die Printerqueue
Drucker arbeitet alle Druckaufträge in der Reihenfolge des
Ankommens ab
Pipe (üblich unter Unix/Linux)
¨
Verbindung zweier Programme
n
n
Prakt. Informatik II
Programm 1 leitet Ausgabe in pipe
Programm 2 entnimmt Eingabe aus der Pipe
© H. Peter Gumm, Philipps-Universität Marburg
Producer - Consumer
n
Produzent
¨
n
Konsument
¨
n
produziert Daten
Nimmt Daten entgegen
Entkopplung durch Queue = Puffer
¨
¨
¨
Produzent: enQ
Konsument: deQ
Vorteil: Produzent und Konsument können asynchron arbeiten
n
n
Keiner verlangsamt den anderen
Konkret
¨
Beim Lesen von der Festplatte:
n
n
¨
Bei einer Pipe
n
n
¨
Programm1 ist producer
Programm2 ist consumer
Beim Senden von Daten
n
n
Prakt. Informatik II
Producer: Festplatte
Consumer: Programm
Producer: Sender
Consumer: Empfänger
© H. Peter Gumm, Philipps-Universität Marburg
Producer-Consumer-Protokoll
n
Producer
¨
¨
produziert
wartet ggf. bis Queue nicht voll
n
¨
n
¨
¨
¨
fügt Element in Queue
x
wartet ggf. bis q nicht leer
n
busy waiting
void
voidproducer(){
producer(){
while(!feierabend()){
while(!feierabend()){
produce(x);
produce(x);
while(q.isFull())
while(q.isFull()){{ }}
q.enQ(x);
q.enQ(x);
}}
}}
Consumer
q
busy waiting
entnimmt Element
konsumiert es
void
voidconsumer(){
consumer(){
while(!feierabend())
while(!feierabend()){{
while(q.isEmpty()){
while(q.isEmpty()){}}
xx==q.getNext();
q.getNext();
consume(x);
consume(x);
}}
}}
Eine
Einevolle
volleQueue
Queuebeim
beimProducer,
Producer,bzw.
bzw.eine
eineleere
leereQueue
Queuebeim
beimConsumer
Consumer
führt
führtnicht
nichtzu
zueiner
einerException,
Exception,sondern
sondernveranlasst
veranlasstden
denBenutzer
Benutzerzum
zumWarten.
Warten.
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Queue Implementierung mit Array
n
Behälter: Ein Array theQueue
¨
Zeiger: front, back
n
n
¨
enQ(Object e)
n
¨
if (! isEmpty()) front++;
isEmpty()
n
n
theQueue[back] = e; back++;
deQ()
n
¨
front zeigt auf erstes Objekt
back auf den nächsten freien Platz
front == back
Problem
Nur wenige
Elemente in der
Queue, aber
schon gefährlich
nahe am
Abgrund
Bereich zwischen front und back wandert
durch den Array
¨ Array kann verlassen werden, auch wenn
nur wenige Elemente gespeichert sind
¨
X @ # 4 QK R Z B E I S P I E L J Q
0
length-1
front
Prakt. Informatik II
back
© H. Peter Gumm, Philipps-Universität Marburg
Zirkuläre Arrays
n
Gedanklich: Verklebe Ende des
Arrays mit seinem Anfang
n
Mathematisch Berechne ArrayIndizes modulo seiner Länge
statt
n
¨
n
¨
¨
I
L
S
front == back
kann bedeuten
length-2
voll
leer
P
length-1
E
I
3
2
1
0
Zusätzliche Boolesche Variable
n
¨
J
E
front = (front+1)%length
n
@
back
front
front++
n
U
M
B
Aber wann ist der Array leer
¨
E
Z
rechne
¨
n
L
L
empty
Wird von enQ/deQ ggf. gesetzt
I E L J @M U E L L Z B E I S P
0
Prakt. Informatik II
empty:
false
length-1
back
front
© H. Peter Gumm, Philipps-Universität Marburg
Implementierung der Queue
n
Array mit Zeigern …
¨
¨
n
… und
¨
n
front : erstes Element
back: Position für das
nächste zu
speichernde Element
boolesche Variable :
full
Klasseninvariante …
front==back
⇔ leer ⊕ voll
¨ length ≥ 0
¨
n
… diese muss von
¨
¨
jedem Konstruktor
jeder Operation
erhalten werden.
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
enQ, deQ, getNext
n
next()
¨
¨
n
enQ()
¨
¨
n
prüft full
setzt es evtl.
deQ()
¨
n
„biegt“ den Array zu
einem Ring
natürlich nur, falls wir
exklusiv damit im
Array navigieren
setzt: full=false
length()
¨
benötigt die
mathematisch korrekte
Version von „modulo“
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
Anwendung von Queues
n
Eine einfache Simulation
¨
Ein Laden hat k Kassen
¨
Zu zufälligen Zeiten kommen
Kunden
n
n
¨
Sie laden ihre Einkaufswagen
n
n
n
¨
mit 1 – 45 Artikeln
zufällig verteilt
gehen dann zur Kasse mit der
kürzesten Schlange
Kassiererin braucht
n
n
¨
im Schnitt n proStunde
aber mal mehr – mal weniger
1 sec pro Artikel
9 sec zum Kassieren
Wieviele Kassen müssen
besetzt sein, damit
n
Prakt. Informatik II
90 % der Kunden nicht länger
als 5 min warten müssen ?
© H. Peter Gumm, Philipps-Universität Marburg
Codefragment – und Ausgabe
Prakt. Informatik II
© H. Peter Gumm, Philipps-Universität Marburg
DeQue
n
Double ended Queue
¨
kombiniert Stack und Queue
n
n
n
n
¨
Zusätzlich
n
n
¨
insertAtFront
removeAtFront
Prakt. Informatik II
insertAtFront = push
removeAtFront = pop = deQ
first = top = front
insertAtRear = enQ
removeAtRear
last
Implementierung
insertAtRear
removeAtRear
© H. Peter Gumm, Philipps-Universität Marburg

Download Report