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
Abstract sequences
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
Kaugõppe
loengu video
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)
Keeles Java võib magasini
realisatsiooni leida klassides java.util.Stack (baseerub
vektoril) või java.util.LinkedList spetsialiseerides
(baseerub topeltseotud ahelal).
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 / +
Näide. Magasini realisatsioon
tavalise massiivi abil
public class Magasin {
/** Peameetod
(silumiseks). */
public static
void main (String[] argum) {
Magasin
m = new Magasin();
System.out.println
(m);
m.push
(1);
System.out.println
(m);
m.push
(3);
System.out.println
(m);
m.push
(6);
System.out.println
(m);
m.push
(2);
System.out.println
(m);
m.op
("/");
System.out.println
(m);
m.op
("*");
System.out.println
(m);
m.op
("-");
System.out.println
(m);
int
tulemus = m.pop();
System.out.println
(m);
System.out.println
(tulemus);
Magasin
koopia = m;
System.out.println
(koopia.equals (m));
System.out.println
(m); System.out.println (koopia);
koopia
= (Magasin)m.clone();
System.out.println
(koopia.equals (m));
System.out.println
(m); System.out.println (koopia);
m.push
(6);
koopia.push
(3);
System.out.println
(koopia.equals (m));
System.out.println
(m); System.out.println (koopia);
m.pop();
System.out.println
(koopia.equals (m));
System.out.println
(m); System.out.println (koopia);
} // main
/** magasin
ise massiivina. */
private int
[] mag;
/** tipu
indeks. */
private int
SP;
/**
vaikekonstruktor teeb 10-elemendilise magasini. */
Magasin () {
this
(10);
} //
konstruktor
/** etteantud
elementide arvuga magasini konstruktor. */
Magasin (int
suurus) {
mag
= new int [suurus];
SP = -1; // tunnus, et magasin on tyhi
} //
konstruktor
/** koopia
loomine. */
@Override
public Object
clone() {
Magasin
tmp = new Magasin (mag.length);
tmp.SP
= SP;
if (SP >= 0)
for
(int
i=0;
i<=SP;
i++)
tmp.mag
[i]
=
mag
[i];
return
tmp;
} // clone
/**
alata"itumise kontroll. */
public
boolean magTyhi() {
return
(SP == -1);
} // magTyhi
/**
yleta"itumise kontroll. */
public
boolean magLohki() {
return
((SP + 1) >= mag.length);
} // magLohki
/** lisamine
magasini. */
public void
push (int a) {
if (magLohki())
throw
new
IndexOutOfBoundsException
("magasini
yletaitumine");
SP += 1; // increment
mag
[SP] = a;
} // push
/**
eemaldamine magasinist. */
public int
pop() {
if (magTyhi())
throw
new
IndexOutOfBoundsException
("magasini
alataitumine");
int
tmp = mag [SP];
SP -= 1; // decrement
return
tmp;
} // pop
/**
aritmeetiline tehe tipus olevate elementide vahel (na"ide). */
public void
op (String s) {
int
op2 = pop();
int
op1 = pop();
if (s.equals ("+")) push (op1 + op2);
if (s.equals ("-")) push (op1 - op2);
if (s.equals ("*")) push (op1 * op2);
if (s.equals ("/")) push (op1 / op2);
} // op
/** tipu
lugemine eemaldamiseta. */
public int
tos() {
if (magTyhi())
throw
new
IndexOutOfBoundsException
("magasini
alataitumine");
return
mag [SP];
} // tos
/**
magasinide v6rdsus. */
public
boolean equals (Object o) {
if (((Magasin)o).SP != SP) return false;
if (magTyhi()) return true; // teine ka tyhi!
for
(int i=0; i<=SP; i++)
if
(((Magasin)o).mag[i]
!=
mag
[i]) return false;
return
true;
} // equals
/** teisendus
s6neks (tipp paremal). */
public String
toString() {
if (magTyhi()) return "Tyhi";
StringBuffer
b = new StringBuffer();
for
(int i=0; i<=SP; i++)
b.append
(String.valueOf
(mag
[i])
+ " ");
return
b.toString();
} // toString
}
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.)
Keeles Java võib järjekorra
realisatsiooni luua klassi java.util.LinkedList
spetsialiseerides (baseerub topeltseotud ahelal).
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).
Näide.
//---------------------------------------
// Fail Jarjekord.java
//---------------------------------------
/** Ta"isarvude ja"rjekorra realisatsioon massiivi abil. */
public class Jarjekord {
/** Peameetod (silumiseks). */
public static void main (String[] argum) {
Jarjekord q = new Jarjekord();
System.out.println (q); // Tyhi
q.lisa (1);
System.out.println (q); // 1
q.lisa (3);
System.out.println (q); // 1 3
int tulemus = q.eemalda();
System.out.println (q); // 3
System.out.println (tulemus); // 1
Jarjekord koopia = q;
System.out.println (koopia.equals (q)); //true
try {
koopia = (Jarjekord)q.clone();
}
catch (CloneNotSupportedException e) {
}
System.out.println (koopia.equals (q)); // true
tulemus = koopia.eemalda();
koopia.lisa (7);
System.out.println (koopia.equals (q)); // false
System.out.println (q); // 3
System.out.println (koopia); // 7
}
/** ja"rjekord ise massiivina. */
private int [] jrk;
/** tipu indeks. */
private int lKoht, eKoht, elArv;
/** vaikekonstruktor teeb 10-elemendilise ja"rjekorra. */
Jarjekord () {
this (10);
}
/** etteantud elementide arvuga ja"rjekorra konstruktor. */
Jarjekord (int suurus) {
jrk = new int [suurus];
lKoht = 0; // lisamise indeks
eKoht = 0; // eemaldamise indeks
elArv = 0; // tegelik elementide arv
}
/** koopia loomine. */
public Object clone() throws CloneNotSupportedException {
Jarjekord tmp = new Jarjekord (jrk.length);
tmp.lKoht = lKoht;
tmp.eKoht = eKoht;
tmp.elArv = elArv;
if (elArv > 0)
for (int i=0; i<elArv; i++)
tmp.jrk [(i+eKoht)%jrk.length] = jrk [(i+eKoht)%jrk.length];
return tmp;
}
/** alata"itumise kontroll. */
public boolean jrkTyhi() {
return (elArv <= 0);
}
/** yleta"itumise kontroll. */
public boolean jrkLohki() {
return (elArv >= jrk.length);
}
/** lisamine ja"rjekorda. */
public void lisa (int a) {
if (jrkLohki())
throw new IndexOutOfBoundsException ("jarjekorra yletaitumine");
elArv += 1;
jrk [lKoht] = a;
lKoht = (lKoht + 1)%jrk.length;
}
/** eemaldamine ja"rjekorrast. */
public int eemalda() {
if (jrkTyhi())
throw new IndexOutOfBoundsException ("jarjekorra alataitumine");
elArv -= 1;
int tmp = jrk [eKoht];
eKoht = (eKoht + 1)%jrk.length;
return tmp;
}
/** ja"rjekordade võrdsus. */
public boolean equals (Object o) {
if (((Jarjekord)o).elArv != elArv) return false;
if (jrkTyhi()) return true; // teine ka tyhi!
for (int i=0; i<elArv; i++)
if (((Jarjekord)o).jrk
[(i+((Jarjekord)o).eKoht)%((Jarjekord)o).jrk.length] !=
jrk [(i+eKoht)%jrk.length]) return false;
return true;
}
/** teisendus so'neks (viimane paremal). */
public String toString() {
if (jrkTyhi()) return "Tyhi";
StringBuffer b = new StringBuffer();
for (int i=0; i<elArv; i++)
b.append (String.valueOf (jrk [(i+eKoht)%jrk.length]) + " ");
return b.toString();
}
} // Jarjekord lopp
Abstraktsed jadad
Vt. Goodrich/Tamassia "Data
Structures and Algorithms in Java" peatükid 3 ja 4.
- Kood
abstraktsete jadade jaoks
//====================================================================
// Fail Sequences.java
//====================================================================
import java.util.LinkedList;
/**
* Abstraktsed jadad Goodrich/Tamassia raamatust.
* @author Jaanus Poial
* @version 0.1 sygis 2000
* @since JDK 1.2
*/
public class Sequences {
/** peameetod. */
static public void main (String[] argum) {
SequenceADT jada = new Sequence();
jada.insertFirst ("esim");
System.out.println (jada);
} // main lopp
} // Sequences lopp
/** Liides indeksitega jada jaoks. */
interface RankedSequenceADT {
/** jada element, millele eelneb r elementi. */
public Object elemAtRank (int r)
throws IndexOutOfBoundsException;
/** asendada element indeksiga r objektiga e.
* @returns endine element.
*/
public Object replaceElemAtRank (int r, Object e)
throws IndexOutOfBoundsException;
/** lisada uus element e nii, et e indeksiks saab r. */
public void insertElemAtRank (int r, Object e)
throws IndexOutOfBoundsException;
/** eemaldada element indeksiga r.
* @returns eemaldatud element.
*/
public Object removeElemAtRank (int r)
throws IndexOutOfBoundsException;
/** elementide arv. */
public int size();
/** kas jada on tyhi. */
public boolean isEmpty();
} // RankedSequenceADT lopp
/** Indeksitega jada realisatsioon topeltseotud ahela abil. */
class RankedSequence
extends java.util.LinkedList
implements RankedSequenceADT {
public Object elemAtRank (int r)
throws IndexOutOfBoundsException {
return get (r);
}
public Object replaceElemAtRank (int r, Object e)
throws IndexOutOfBoundsException {
return set (r, e);
}
public void insertElemAtRank (int r, Object e)
throws IndexOutOfBoundsException {
add (r, e);
}
public Object removeElemAtRank (int r)
throws IndexOutOfBoundsException {
return remove (r);
}
public boolean isEmpty() {
return (size() == 0);
}
} // RankedSequence lopp
/** Liides "koht jadas". */
interface Position {
/** tagastab sellel kohal oleva elemendi. */
public Object element();
/** tagastab jada, mille koht see on. */
public PositionalSequenceADT container();
/** paneb antud objekti e sellele kohale. */
public void setElement (Object e);
} // Position lopp
/** Klass, mis realiseerib liidest "koht jadas". */
class PosElement implements Position {
private Object elem;
private PositionalSequenceADT cont;
/** konstruktor. */
PosElement (Object e, PositionalSequenceADT c) {
setElement (e);
setContainer (c);
}
public Object element() {
return elem;
}
public PositionalSequenceADT container() {
return cont;
}
public void setElement (Object e) {
elem = e;
}
void setContainer (PositionalSequenceADT c) {
cont = c;
}
} // PosElement lopp
/** Liides kohtadega jada jaoks. */
interface PositionalSequenceADT {
public Position first();
public Position last();
public Position before (Position p);
public Position after (Position p);
public int size();
public boolean isEmpty();
public Object replace (Position p, Object e);
public void swap (Position p, Position q);
public Position insertFirst (Object e);
public Position insertLast (Object e);
public Position insertBefore (Position p, Object e);
public Position insertAfter (Position p, Object e);
public Object remove (Position p);
} // PositionalSequenceADT lopp
/** Klass, mis realiseerib liidese kohtadega jada jaoks. */
class PositionalSequence extends LinkedList
implements PositionalSequenceADT {
public Position first() {
return (Position) getFirst();
}
public Position last() {
return (Position) getLast();
}
public Position before (Position p) {
int i = indexOf (p); // siia kontrollid vaja panna
return (Position)get (i-1);
}
public Position after (Position p) {
int i = indexOf (p); // siia kontroll!!
return (Position)get (i+1);
}
public boolean isEmpty() {
return (size()==0);
}
public Object replace (Position p, Object e) {
Object old = p.element();
p.setElement (e);
return old;
}
public void swap (Position p, Position q) {
Object tmp = p.element();
p.setElement (q.element());
q.setElement (tmp);
}
public Position insertFirst (Object e) {
Position p = new PosElement (e, this);
addFirst (p);
return p;
}
public Position insertLast (Object e) {
Position p = new PosElement (e, this);
addLast (p);
return p;
}
public Position insertBefore (Position p, Object e) {
Position q = new PosElement (e, this);
add (indexOf (p), q);
return q;
}
public Position insertAfter (Position p, Object e) {
Position q = new PosElement (e, this);
add (indexOf (p)+1, q); // siia veel yks kontroll vaja
return q;
}
public Object remove (Position p) {
Object e = p.element();
if (! super.remove (p))
throw new java.util.NoSuchElementException (" positsioon");
return e;
}
} // PositionalSequence lopp
/** Liides abstraktse jada jaoks. */
interface SequenceADT extends RankedSequenceADT, PositionalSequenceADT {
/** elemendi indeksiga r positsioon, */
public Position atRank (int r);
/** positsiooni p indeks. */
public int rankOf (Position p);
/** teisendus so'neks, et saaks siluda. */
public String toString();
} // SequenceADT lopp
/** Klass, mis realiseerib abstraktse jada. */
class Sequence extends PositionalSequence
implements SequenceADT {
public Position atRank (int r) {
return (Position) get (r);
}
public int rankOf (Position p) {
return indexOf (p);
}
public Object elemAtRank (int r)
throws IndexOutOfBoundsException {
return ((Position)get (r)).element();
}
public Object replaceElemAtRank (int r, Object e)
throws IndexOutOfBoundsException {
Object tmp = atRank (r).element();
atRank (r).setElement (e);
return tmp;
}
public void insertElemAtRank (int r, Object e)
throws IndexOutOfBoundsException {
add (r, new PosElement (e, this));
}
public Object removeElemAtRank (int r)
throws IndexOutOfBoundsException {
return ((Position)remove (r)).element();
}
public String toString() {
if (isEmpty()) return "Tyhi";
StringBuffer b = new StringBuffer();
for (int i=0; i < size(); i++)
b.append (elemAtRank (i).toString() + " ");
return b.toString();
}
} // Sequence lopp
Sisuliselt on see teema Java APIs
küllalt hästi esindatud: java.util.LinkedList,
java.util.Vector, java.util.Stack, ...
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).
Järgnevalt analüüsitakse lihtahela
operatsioone: lisamine algusesse, suuruse poolest sobivale
kohale, lõppu; eemaldamine; otsimine; ...
Magasini on lihtne realiseerida
lihtahela abil.
Jaanus Pöial