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
  1. Lubatud väärtuste hulk (väärtusvaru)
  2. Lubatud operatsioonide hulk
  3. (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:

  1. lihttüübid, mille väärtustel ei ole sisemist struktuuri: arv, tõeväärtus, ...
  2. struktuursed tüübid, mille väärtus koosneb komponentidest: massiiv, objekt (kirje), ...
Operatsioonid on OOP-s "kinnistatud" objekti juurde (kapseldus).
  1. Kinnised operatsioonid: tulemus kuulub sama tüübi väärtusvarusse
  2. mittekinnised operatsioonid: tulemus on mingit teist tüüpi
  3. 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:
  1. staatilised: komponentide arv ja tüübid fikseeritud: näiteks kompleksarv
  2. 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:

  1. dünaamiline struktuur (elementide arv on muutuv)
  2. elemendid on sama tüüpi
  3. elementide järjestus on oluline
  4. juurdepääs on ainult viimasena lisatud elemendile (magasini tipp); "lisamine" lisab lõppu ja "võtmine" eemaldab lõpust
  5. 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:

  1. dünaamiline struktuur (elementide arv on muutuv)
  2. elemendid on sama tüüpi
  3. elementide järjestus on oluline
  4. juurdepääs on ainult esimesena lisatud elemendile (front); "lisamine" lisab lõppu ja "võtmine" eemaldab algusest (järjekorra metafoor)
  5. 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.
  1. Lihtahel - iga element sisaldab viita järgmisele (Java seisukohalt - sisaldab järgmist elementi isendimuutujana), ahela lõpetab nullviit
  2. Topeltseotud ahel - iga element sisaldab kaht viita: järgmisele elemendile ja eelmisele elemendile
  3. Ringahel - puudub ahelat lõpetav nullviit (Javas objekti puudumist tähistav null), elemendid moodustavad "ringi"
  4. 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).
Joonis

Lihtahela operatsioone: lisamine algusesse,  suuruse poolest sobivale kohale, lõppu;  eemaldamine; otsimine; ...
Magasini on lihtne realiseerida lihtahela abil.
 

Jaanus Pöial