Abstract Data Types, Stack and Queue

Queue

Abstraktsed andmetüübid, pinu ja järjekord

Abstraktsed andmetüübid

1. Lubatud väärtuste hulk (väärtusvaru)
2. Lubatud operatsioonide hulk
3. (Notatsioon - tähistused väärtuste ja operatsioonide jaoks)

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), ...

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

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"

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, ...

Magasin (stack) e. pinu

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)

Avaldise postfikskuju ja selle interpreteerimine

                   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

Järjekord (queue)

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

Eelistusjärjekord

Muutuvate eelistustega järjekord

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]));
         b.append(" ");
      return b.toString();
   }

} // Jarjekord lopp

Abstraktsed jadad

• Kood abstraktsete jadade jaoks

//====================================================================
// Fail Sequences.java
//====================================================================

import java.util.LinkedList;

/**
 * Abstraktsed jadad Goodrich/Tamassia raamatust.
 * @author Jaanus Poial
 */
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

Ahelad

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

• Kood lihtahela jaoks