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

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)
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:

  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.)
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.
//====================================================================
// 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.
  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
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