Izpitno vprašanje DIRI2005 4600

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)

Vprašanje

Predstavitev sklada s pomočjo tabele.

Odgovor


Realizacija sklada s tabelo je precej enostavna, saj potrebujemo le indeks vrhnjega elementa. Slabost je v omejeni velikosti tabele, ki jo moramo definirati na začetku.

Sklad formalno opredelimo z metodami, ki jih lahko nad skladom izvajamo. V nadaljevanju navajam opise metod, na koncu pa je predstavljen razred Sklad, ki je izveden s tabelo.

Vstavi

if (..preverimo če je sklad poln..)
 ERROR
 // kaj storimo v tem primeru, je odvisno od uporabe

else {
 sklad[vrh] = podatek;
 vrh = vrh + 1;
};


Brisi

if (prazen())
 ERROR
else
 vrh = vrh - 1;


Vrh

if (prazen())
 ERROR
else
 return sklad[vrh-1];


Prazen

/*
sklad je prazen, ce je
vrh enak 0
*/
return (vrh = 0);


Takole pa izgleda razred Sklad, ki je realiziran s tabelo

public class Sklad extends Object
{
 // predstavitev sklada s tabelo
 // v skladu hranimo cela števila
 // uporabnik mora sam poskrbeti, da ne prekorači zmogljivosti sklada

 private int[] tab;
 private int kam; // kazalec na mesto, kjer bomo vstavili nov element
 private final static int MAX_V = 20; // privzeta velikost sklada

 // kostruktorji (pripravi)

 public Sklad()
 {
  tab = new int[MAX_V];
  kam = 0;
 }

 public Sklad(int vel)
 {
  tab = new int[vel];
  kam = 0;
 }

 // metode

 public void vstavi(int pod)
 { // vstavi podatek "pod" v sklad
  tab[kam] = pod;
  kam = kam + 1;
 }

 public void odstrani()
 {  // odstrani podatek iz sklada
  // če je sklad prazen, ne naredimo nič
  if (!prazen())
	kam = kam - 1;
 }

 public boolean prazen()
 { // ali je sklad prazen
  return (kam == 0);
 }

 public int vrh()
 {  // vrne vrhnji element sklada
  // če je sklad prazen, vrne največji int
  // sklad se NE spremeni
  if (!prazen())
  {
   return tab[kam - 1]; // kam kaže na prvo PROSTO mesto
  }
   return Integer.MAX_VALUE; // v primeru praznega sklada
  }

  ///// dodatna metoda

 public boolean poln()
 { // je sklad poln?
 return (kam == tab.length);
 }
 
 public void izpis()
 {   // izpise sklad in ga ohrani
  for(int i = kam - 1; i >= 0; i--)
  System.out.print(tab[i] + " ");

  System.out.println();
 }
}
Osebna orodja