Geef telkens de waarde van x nadat de uitdrukking x <- q.front() werd uitgevoerd. Geef telkens de waarde van y nadat de uitdrukking y <- q.dequeue() werd uitgevoerd.
q <- nieuwe Queue(3)
q.enqueue(100)
q.enqueue(54)
x <- q.front()
y <- q.dequeue()
x <- q.front()
q.enqueue(60)
q.enqueue(360)
y <- q.dequeue()
y <- q.dequeue()
x <- q.front() data k s x y
----------------------------------------------------
1) | | | | -1 -1
2) |100| | | 0 0
3) |100|54| | 0 1
4) 100
5) |100|54| | 1 1 100
6) 54
7) |100|54|60| 1 2
8) |360|54|60| 1 0
9) |360|54|60| 2 0 54
10) |360|54|60| 0 0 60
11) 360^ op examen
Breid de klasse Queue uit met een methode full. Deze methode heeft als resultaat een boolean en geeft aan of een wachtrij al dan niet vol is.
full(I: /): vlag: boolean
* Preconditie: de wachtrij q bestaat.
* Postconditie: de waarde true of false werd afgelevered, afhankelijk van het feit of de wachtrij q vol is of niet.
* Gebruikt: length
BEGIN
RETOUR ((s + 1) MOD data.length) = k
EINDEBreid de klasse Queue uit met een methode size. Deze methode heeft als resultaat het aantal elementen dat tot een wachtrij q behoort
size(I: /): aantal: geheel getal
* Preconditie: de wachtrij q bestaat
* Postconditie: het aantal elementen dat tot de wachtrij q behoort werd geretourneerd
* Gebruikt: empty(), length
BEGIN
ALS empty() DAN
aantal <- 0
ANDERS
aantal <- s - k + 1
ALS (aantal ≤ 0) DAN
aantal <- aantal + data.length
EINDE ALS
EINDE ALS
RETOUR (aantal)
EINDESchrijf een nieuwe versie van de methode enqueue. Gebruik dynamische arrays zodat, indien de wachtrij reeds vol is, de elementen van de wachtrij worden gecopieerd naar een dubbel zo grote array.
enqueue(I: x: Element): /
* Preconditie: de wachtrij q bestaat en is nog niet vol
* Postconditie: het element x werd aan de staart van de wachtrij q toegevoegd
* Gebruikt: full, empty, length
BEGIN
n <- data.length
ALS full() DAN
original <- data
data = nieuwe array[n * 2]
VOOR i = 0 TOT n - 1 DOE
data[i] <- original[(k + i MOD n)]
EINDE VOOR
k <- 0
s <- n
ANDERS
ALS empty() DAN
k <- 0
EINDE ALS
s <- (s + 1) MOD n
EINDE ALS
data[s] <- x
EINDEconcatenate(q1, q2) : voegt de elementen van de wachtrij q2 toe achteraan de wachtrij q1. Na afloop zullen de beide wachtrijen gewijzigd zijn.
concatenate(I: q1, q2)
* Preconditie: De wachtrijen q1 en q2 hebben evenveel elementen
* Postconditie: De wachtrij q2 werd aan q1 toegevoegd
* Gebruikt: enqueue, dequeue, empty
BEGIN
ZOLANG ( NIET q2.empty()) DOE
q1.enqueue(q2.dequeue())
EINDE ZOLANG
RETOUR (q1)
EINDEmerge(q1, q2) : voegt de elementen van de wachtrij q1 en de elementen van de wachtrij q2 samen in een wachtrij q zodanig dat de elementen van q1 op de even posities (0, 2, . . . ) staan en de elementen van q2 op de oneven posities (1,3, . . . ). Na afloop zullen de beide wachtrijen gewijzigd zijn.
merge(I: q1, q2)
* Preconditie: De wachtrijen q1 en q2 hebben evenveel elementen
* Postconditie: De wachtrij q werd geretourneerd, in de wachtrij q staan de elementen van q1 op de even posities (0, 2, ...) en de elementen van q2 op de oneven positites (1, 3, ...)
* Gebruikt: Queue, empty, enqueue, dequeue, size
BEGIN
q1Grootte = q1.size()
q2Grootte = q2.size()
q = nieuwe Queue(q1Grootte + q2Grootte)
ZOLANG (NIET q1.empty() EN NIET q2.empty()) DOE
q.enqueue(q1.dequeue())
q.enqueue(q2.dequeue())
EINDE ZOLANG
ZOLANG (NIET q1.empty()) DOE
q.enqueue(q1.dequeue())
EINDE ZOLANG
ZOLANG (NIET q2.empty()) DOE
q.enqueue(q2.dequeue())
EINDE ZOLANG
RETOUR (q)
EINDESchrijf een methode removeTail( ) die het laatst toegevoegde element van een wachtrij verwijdert en ook retourneert. Schrijf deze methode uit in pseudo-code. Maak enkel gebruik van de abstracte datastructuur van een wachtrij, verwijs niet naar een eventuele implementatie. De methode size uit oefening 3 mag gebruikt worden.
removeTail(I: q1): x: Element
* Preconditie: De wachtrijen q1 en q2 hebben evenveel elementen
* Postconditie: De wachtrij q werd geretourneerd, in de wachtrij q staan de elementen van q1 op de even posities (0, 2, ...) en de elementen van q2 op de oneven positites (1, 3, ...)
* Gebruikt: enqueue, dequeue, size
BEGIN
VOOR i = 1 TOT q1.size() - 1 DOE
q1.enqueue(q1.dequeue())
EINDE VOOR
RETOUR q1.dequeue()
EINDE
// Of zonder size
BEGIN
n <- q.size()
qHulp <- nieuwe Queue(n)
x <- q.dequeue()
ZOLANG NIET q.empty() DOE
qHulp.enqueue(x)
x <- q.dequeue()
EINDE ZOLANG
ZOLANG NIET qHulp.empty() DOE
q1.enqueue(qHulp.dequeue())
EINDE ZOLANG
RETOUR (x)
EINDEGegeven is een wachtrij q1. Schrijf een methode invertQueue voor het verplaatsen van alle elementen van q1 naar een nieuwe wachtrij q2. De elementen van q1 moeten in omgekeerde volgorde voorkomen in q2. Na afloop is de wachtrij q1 leeg. Maak enkel gebruik van publieke methodes voor het schrijven van het algoritme. Verwijs niet naar een eventuele implementatie. De functie size uit oefening 3 mag eveneens gebruikt worden.
invertQueue(I: q1): q1: Queue
* Preconditie:
* Postconditie:
* Gebruikt: Queue, Stack
BEGIN
q2 <- nieuwe Queue(q1.size())
hulpStapel <- nieuwe Stack(q1.size())
ZOLANG NIET q1.empty() DOE
hulpStapel.push(q1.dequeue())
EINDE ZOLANG
ZOLANG NIET hulpStapel.empty() DOE
q2.enqueue(hulpStapel.pop())
EINDE ZOLANG
RETOUR (q2)
EINDE