Izpitno vprašanje RAČ2PRA 4600

Iz MaFiRaWiki

Vprašanje:

Predstavitev sklada s tabelo!

Odgovor:

  • Elemente hranimo v tabeli (cela števila)
  • Problem: omejena velikost
  • rešitev: Uporabnik naj sam poskrbi zato, da ne prekorači zmogljivosti sklada

Ideja je v tem, da podatke hranimo v tabeli. Poleg tega si zapomnimo še indeks do kje je tabela zapolnjena. To nam bo predstavljalo vrh sklada, dno sklada pa bo pri indeksu 0.

V predstavitvi spodaj kot indeks (kam) vodimo prvo prosto mesto. Torej ima trenutni vrhnji elt v skladu indeks kam - 1.

  1. public class SkladTabela{
  2. private int[] tabela;
  3. private int kam; // kazalec na mesto, kjer bomo vstavili nov element
  4. private final static int MAX_V = 20; // privzeta velikost sklada
  5.  
  6. // kostruktorja:
  7. public SkladTabela(){ //sklad privzete velikosti
  8. tabela = new int[MAX_V]; //naredimo prazno tabelo s prostorom za MAX_V elementov
  9. kam = 0;
  10. }
  11. public SkladTabela(int velikost){
  12. tabela = new int[velikost];
  13. kam = 0;
  14. }
  15.  
  16. // metode:
  17. public void vstavi(int podatek)throws Exception{ // vstavimo podatek v sklad
  18. if(kam > tabela.length) throw new Exception("Sklad je poln.");
  19. else{
  20. tabela[kam] = podatek;
  21. kam = kam + 1; //premanemo se naprej na naslednji element
  22. }
  23. public void odstrani()throws Exception{ // odstranimo podatek iz sklada
  24. // ce je sklad prazen, ne naredimo nič
  25. if (!prazen()) kam = kam - 1; //indeks premaknemo za eno mesto nazaj - tabela namreč ne pozna brisanja
  26. else throw new Exception("Sklad je prazen.");
  27. }
  28. public boolean prazen(){ // ali je sklad prazen
  29. return (kam == 0);
  30. }
  31. public int vrh()throws Exception{ // vrnemo vrhnji element sklada
  32. if (!prazen()) return tabela[kam - 1]; // kam kaže na prvo PROSTO mesto
  33. else throw new Exception("Sklad je prazen.");
  34. }
  35. public boolean poln(){ // je sklad poln?
  36. return (kam == tabela.length);
  37. }
  38. public String toString(){
  39. String izpis = "";
  40. for(int i = kam - 1; i >= 0; i--){
  41. izpis = izpis + " " + tabela[i];
  42. }
  43. return izpis;
  44. }}}
Osebna orodja