Abstract
Data Types, Stack and Queue
"Early"
OOP. Set of values (domain), set of operations, notation.
Primitive types vs. structured types. Encapsulation. Closed
operations vs. open operations, type conversions. Imperative vs.
object oriented notation for operations. Static types and dynamic
types. Adding and removing elements, complexity issues.
Stack
LIFO - Last In First Out.
Top (Top Of Stack = TOS) and bottom.
Main operations - push, pop, top, underflow (and overflow)
conditions
Forms of arithmetic expressions: infix, prefix, postfix, Reverse
Polish Notation (RPN)
Examples - return stack, RPN calculator
Array based implementation of stack
Queue
FIFO -
First In First Out
Main operations - add, remove, iterator, ...
Priority queue
Dynamic priority queue
Examples and complexity issues
Implementation of queue using circular buffer
Dequeue - Double Ended Queue
Pointers, lists: linked
list, doubly linked list, circular list, lists with headers
Implementation of linked
lists
Implementation of stacks
based on unidirectional (singly) linked list
Abstraktsed andmetüübid, magasin ja
järjekord
Abstraktsed andmetüübid
"Varajane" OOP. Eesmärk: peita
realisatsiooni detailid, anda rakenduse programmeerijale
probleemorienteeritud liides.
ADT - Abstract Data Type
- Lubatud väärtuste hulk (väärtusvaru)
- Lubatud operatsioonide hulk
- (Notatsioon - tähistused väärtuste ja operatsioonide jaoks)
Näit. kompleksarvud, polünoomid,
graafid, geomeetrilised kujundid, ...
OOP muutis niisuguse lähenemise
kohustuslikuks.
Väärtusvaru järgi jagunemine:
- lihttüübid, mille väärtustel ei ole sisemist struktuuri: arv,
tõeväärtus, ...
- struktuursed tüübid, mille väärtus koosneb komponentidest:
massiiv, objekt (kirje), ...
Operatsioonid on OOP-s "kinnistatud"
objekti juurde (kapseldus).
- Kinnised operatsioonid: tulemus kuulub sama tüübi
väärtusvarusse
- mittekinnised operatsioonid: tulemus on mingit teist tüüpi
- tüübiteisendused: tegelikud ja deklaratiivsed
Näit. kinnine operatsioon "summa"
(mis iganes see ka poleks)
Imperatiivne
lähenemine: m = summa (a, b)
"funktsiooni summa parameetriteks on a ja b"
OOP lähenemine: m = a.summa (b) "objektile a
saadetakse teade 'summa' parameetriga b"
Andmestruktuurid võib jagada:
- staatilised: komponentide arv ja tüübid fikseeritud: näiteks
kompleksarv
- dünaamilised: väärtuse komponentide arv on muutuv,
komponendid ise tavaliselt üht tüüpi: näiteks magasin,
järjekord, graaf, ...
Andmestruktuuride korral on
oluliseks küsimuseks juurdepääsu tagamine komponentidele ning
struktuuri muutmine (vastavate operatsioonide ajaline keerukus).
"Võtmine" ja "lisamine".
Magasin (stack)
LIFO - last in first out
Magasini omadused:
- dünaamiline struktuur (elementide arv on muutuv)
- elemendid on sama tüüpi
- elementide järjestus on oluline
- juurdepääs on ainult viimasena lisatud elemendile (magasini
tipp); "lisamine" lisab lõppu ja "võtmine" eemaldab lõpust
- tavaliselt realiseeritavad operatsioonid: tühja magasini
loomine, lisamine (push), võtmine (pop),
alatäitumise (underflow) kontroll (et vältida tühjast
magasinist võtmist), mõne realisatsiooni korral ka ületäitumise
(overflow) kontroll (kas on "ruumi" lisamiseks), tipu
lugemine ilma eemaldamiseta (optim. kaalutlustel)
Magasini kasutamise näited: avaldise väärtustamine,
'return stack', puu läbimine, ...
Avaldise postfikskuju ja selle
interpreteerimine
"Tavaline" infikskuju: (5-1)
* 7 + 6 / 3
Prefikskuju sulgudega: +( *( -( 5, 1), 7), /(6, 3))
Postfikskuju sulgudega: (((5, 1)-, 7)*, (6, 3)/ )+
Sulgudeta postfikskuju - nn. "pööratud poola kuju": 5 1 - 7
* 6 3 / + .
3
1 7 6 6 2
5 5 4 4 28 28 28 28 30
--------------------------
5 1 - 7 * 6 3 / +
Realisatsiooni näide:
#!/usr/bin/env python3
import sys
class Magasin(object):
__list = []
def __init__(self, lst=None):
if lst is None:
self.__list = []
else:
self.__list = lst
def __len__(self):
return len(self.__list)
def tyhi(self):
return len(self) == 0
def push(self, value):
self.__list.append(value)
def pop(self):
if self.tyhi():
raise IndexError("pop tyhjast magasinist")
return self.__list.pop()
def tos(self):
if self.tyhi():
raise IndexError("tos tyhjast magasinist")
return self.__list[len(self.__list)-1]
def __bool__(self):
return not self.tyhi()
def __str__(self):
res = ""
for k in self.__list:
res += " " + str(k)
if res == "":
res = "tyhi"
return res
def __eq__(self, other):
if len(self) != len(other):
return False
for k in range(0, len(self)):
if self.__list[k] != other.__list[k]:
return False
return True
def copy(self):
return Magasin(list(self.__list))
def op(self, operator):
if self.tyhi():
raise IndexError("op tyhjast magasinist")
o2 = self.pop()
if self.tyhi():
raise IndexError("op pooltyhjast magasinist")
o1 = self.pop()
if operator.strip() in ['+', '-', '*', '/']:
res = eval(str(o1) + operator + str(o2))
else:
raise ValueError("vale tehe " + operator + " meetodis op")
self.push(res)
Järjekord (queue)
FIFO - First In First Out
Järjekorra omadused:
- dünaamiline struktuur (elementide arv on muutuv)
- elemendid on sama tüüpi
- elementide järjestus on oluline
- juurdepääs on ainult esimesena lisatud elemendile (front);
"lisamine"
lisab
lõppu
ja
"võtmine"
eemaldab algusest (järjekorra metafoor)
- tavaliselt realiseeritavad operatsioonid: tühja järjekorra
loomine, lisamine, võtmine, alatäitumise (underflow)
kontroll (et vältida tühjast järjekorrast võtmist), mõne
realisatsiooni korral ka ületäitumise (overflow) kontroll
(kas on "ruumi" lisamiseks), vahendid järjekorra läbivaatamiseks
(näit. iteraatorid vms.)
Näiteid järjekorra kasutamise kohta: ressursside jagamine
(printer), tegevuste planeerimine, graafi läbimine
Eelistusjärjekord
Järjekord, milles on olulised
elementide (võtmete) väärtused. Prioriteetidega järjekord.
"Lisamine" on sisuliselt hulgateoreetiline lisamine ja "võtmine"
on vähima (suurima) võtmeväärtusega elemendi eemaldamine. Kui
prioriteedid on staatilised (ei muutu elemendi järjekorras olemise
ajal), siis saab "lisamise" teha pistemeetodi abil "Õigesse
kohta".
Muutuvate eelistustega järjekord
Kui elemendi prioriteet võib
elemendi järjekorras olemise ajal dünaamiliselt muutuda (niisugust
järjekorda nim. muutuvate eelistustega järjekorraks), siis tuleb
"võtmine" realiseerida järjekorra läbivaatusena ("lisamine" on
selle eest lihtne). Teine võimalus on kajastada iga
prioriteedimuutust kohe järjekorras, aga see ei pruugi olla hea
lahendus (näiteks kui muutusi on palju, aga võtmisi vähe).
Ahelad
Ahel koosneb muutuvast arvust
elementidest, mis on omavahel seotud viitadega. Keeles Java ei ole
viidatüüpi operatsioone ilmutatud kujul olemas - iga objektitüüpi
väärtus on "tegelikult" viit.
- Lihtahel - iga element sisaldab viita järgmisele (Java
seisukohalt - sisaldab järgmist elementi isendimuutujana), ahela
lõpetab nullviit
- Topeltseotud ahel - iga element sisaldab kaht viita:
järgmisele elemendile ja eelmisele elemendile
- Ringahel - puudub ahelat lõpetav nullviit (Javas objekti
puudumist tähistav null),
elemendid
moodustavad "ringi"
- Päisega ahel - ahelale on lisatud formaalne lüli, mis ei
kuulu ahela koosseisu, aga viitab esimesele (topeltseotud ahela
korral ka viimasele) lülile. Vajalik selleks, et tühi ahel
kujutuks objektina (mitte nullviidana).
Lihtahela
operatsioone: lisamine algusesse, suuruse poolest sobivale
kohale, lõppu; eemaldamine; otsimine; ...
Magasini on lihtne realiseerida
lihtahela abil.
Jaanus Pöial
