Kaktusov sklad/Implementacija (Java)

Iz MaFiRaWiki

  1. public class KaktusovSklad{
  2. //KOMPONENTE
  3. private KaktusovSklad korenKaktusa; //katusov sklad do nevključno vrha!
  4. private Object vrhKaktusa;
  5. private boolean vrhJeKaktus; //true, če je vrh kaktusovega sklada kaktusov sklad
  6. //KONSTRUKTORJI
  7. //--osnovni
  8. //ustvari prazen kaktusov sklad: z nedoločenim (neobstoječim) korenom in vrhom
  9. public KaktusovSklad(){
  10. this.korenKaktusa = null; //= new KaktusovSklad() <-- tega ne moremo napisati (ker bi dobili cikel)!
  11. this.vrhKaktusa = null;
  12. this.vrhJeKaktus = false;
  13. }
  14. //--sprejme objekt poljubnega tipa
  15. //ustvari katusov sklad z nedoločenim (neobstoječim) korenom ter vrhom element
  16. public KaktusovSklad(Object element){
  17. this.vstavi(element); //kličemo kar metodo vstavi
  18. }
  19. //METODE
  20. //--koren
  21. public KaktusovSklad koren(){
  22. return this.korenKaktusa;
  23. }
  24. //--vrh
  25. public Object vrh(){
  26. if(this.vrhJeKaktus){ //če je na vrhu kaktusov sklad:
  27. return ((KaktusovSklad)this.vrhKaktusa).vrh(); //vrnemo vrh od vrhnjega kaktusovega sklada
  28. }
  29. //če na vrhu ni kaktusovega sklada, vrnemo kar komponento
  30. return this.vrhKaktusa;
  31. }
  32. //--kajNaVrhu
  33. //true, če je na vrhu kaktusov sklad
  34. //false, na vrhu je element
  35. public boolean kajNaVrhu(){
  36. if(this.vrhJeKaktus){
  37. return true;
  38. }
  39. else return false;
  40. }
  41. //--vrhJeKaktusovSklad
  42. public boolean vrhJeKaktusovSklad(){
  43. return this.vrhJeKaktus;
  44. }
  45. //--prazen
  46. public boolean prazen(){
  47. return this.vrhKaktusa == null && this.korenKaktusa == null;
  48. }
  49. //--vstavi
  50. public KaktusovSklad vstavi(Object element){
  51. KaktusovSklad pomozni = new KaktusovSklad(); //potrebujemo novega, da bo:
  52. //nov kaktusov sklad do vrha = star katusov sklad z vrhom vred, saj "potiskamo elemente navzdol":
  53. pomozni.korenKaktusa = new KaktusovSklad();
  54. if(this.korenKaktusa == null || this.korenKaktusa.prazen()){ //če je koren kakt. sklada nedoločen ali prazen (kaktus ima le vrhnji element):
  55. pomozni.korenKaktusa.vrhKaktusa = this.vrhKaktusa;
  56. }//
  57. else{ //če koren kakt.sklada ni prazen:
  58. pomozni.korenKaktusa = this.copy();
  59. }
  60. //nov vrh kaktusovega sklada = dani objekt:
  61. if(element.getClass().getName().equals("KaktusovSklad")){ //če je tip objekta KaktusovSklad:
  62. pomozni.vrhJeKaktus = true;
  63. pomozni.vrhKaktusa = ((KaktusovSklad)element).copy();
  64. }
  65. else{ //če tip objekta ni KaktusovSklad:
  66. pomozni.vrhKaktusa = element;
  67. pomozni.vrhJeKaktus = false;
  68. }
  69. //popravimo this:
  70. this.korenKaktusa = pomozni.korenKaktusa;
  71. this.vrhKaktusa = pomozni.vrhKaktusa;
  72. this.vrhJeKaktus = pomozni.vrhJeKaktus;
  73. //vrnemo spremenjen this:
  74. return this;
  75. }
  76. //--odstrani
  77. public KaktusovSklad odstrani() throws Exception{
  78. if(this.prazen()) throw new Exception("Kaktusov sklad je že prazen!");
  79. else{ //če kaktusov sklad ni prazen:
  80. return this.odstraniElement(); //kličemo privatno metodo
  81. }
  82. }
  83. //--odstraniElement
  84. //pomožna metoda, ki jo potrebujemo za metodo odstrani()
  85. private KaktusovSklad odstraniElement(){
  86. if(this.prazen()) { //če je kaktusov sklad prazen:
  87. //vrnemo le koren od this
  88. return ((KaktusovSklad)this.korenKaktusa).copy();
  89. }
  90. else{ //če kaktusov sklad ni prazen:
  91. KaktusovSklad pomozni = new KaktusovSklad();
  92. if(this.vrhJeKaktus && !((KaktusovSklad)this.vrhKaktusa).prazen()){ //če je na vrhu neprazen kaktusov sklad:
  93. if(((KaktusovSklad)this.vrhKaktusa).korenKaktusa == null || ((KaktusovSklad)this.vrhKaktusa).korenKaktusa.prazen()){ //če je koren vrhnjega kakt. sklada nedoločen ali prazen (vrhnji kaktus ima le en element => ima le vrh):
  94. //prepišemo le koren od this v nov kaktusov sklad:
  95. pomozni = this.korenKaktusa.copy();
  96. //popravimo this:
  97. this.korenKaktusa = pomozni.korenKaktusa;
  98. this.vrhKaktusa = pomozni.vrhKaktusa;
  99. this.vrhJeKaktus = pomozni.vrhJeKaktus;
  100. }
  101. else{ //če koren vrhnjega kaktusovega sklada ni prazen:
  102. //odstranimo element iz vrhnjega kaktusovega sklada:
  103. pomozni = ((KaktusovSklad)this.vrhKaktusa).odstraniElement().copy();
  104. //popravimo le vrh od this:
  105. ((KaktusovSklad)this.vrhKaktusa).korenKaktusa = pomozni.korenKaktusa;
  106. ((KaktusovSklad)this.vrhKaktusa).vrhKaktusa = pomozni.vrhKaktusa;
  107. ((KaktusovSklad)this.vrhKaktusa).vrhJeKaktus = pomozni.vrhJeKaktus;
  108. }
  109. }
  110. else{ //če na vrhu ni kakt. sklada, ali pa je na vrhu prazen kaktusov sklad:
  111. //prepišemo le koren od this v nov kaktusov sklad:
  112. if(this.korenKaktusa != null){ //če koren kaktusa ni nedoločen/neobstoječ:
  113. pomozni = this.korenKaktusa.copy();
  114. }
  115. else{ //če je koren kaktusa neobstoječ:
  116. //pomozni že ima prave vrednosti komponent
  117. }
  118. //popravimo this:
  119. this.korenKaktusa = pomozni.korenKaktusa;
  120. this.vrhKaktusa = pomozni.vrhKaktusa;
  121. this.vrhJeKaktus = pomozni.vrhJeKaktus;
  122. }
  123. //vrnemo spremenjen this:
  124. return this;
  125. }
  126. }
  127. //--toString
  128. public String toString(){
  129. String niz = "[ ";
  130. //preden se lotimo pregleda elementov, shranimo this v pomožni kaktusov sklad:
  131. KaktusovSklad pomozni = this.copy();
  132. //gremo čez elemente:
  133. while(!this.prazen()){
  134. if(this.vrhJeKaktus){ //če je vrh kaktusovega sklada kaktusov sklad:
  135. //gremo čez elemente vrhnjega kaktusa:
  136. niz += " " + ((KaktusovSklad)this.vrhKaktusa).toString() + " "; //zabeleži celo "vejo"
  137. while(!((KaktusovSklad)this.vrhKaktusa).prazen()){ //odstranimo vse elemente vrhnjega kaktusa
  138. try {((KaktusovSklad)this.vrhKaktusa).odstrani();}//ker toString() ne sme vreči izjeme, odstrani() pa jo lahko
  139. catch(Exception e){System.out.println(e.getMessage());}
  140. }
  141. try{this.odstrani();} //odstranimo še prazen vrhnji kaktusov sklad
  142. catch(Exception e){System.out.println(e.getMessage());}
  143. }
  144. else{
  145. niz += " " + this.vrhKaktusa + " ";
  146. try{this.odstrani();} //ker toString() ne sme vreči izjeme, odstrani() pa jo lahko
  147. catch(Exception e){System.out.println(e.getMessage());}
  148. }
  149. }
  150. niz += " ]";
  151. //this povrnemo v prvotno stanje:
  152. this.korenKaktusa = pomozni.korenKaktusa;
  153. this.vrhKaktusa = pomozni.vrhKaktusa;
  154. this.vrhJeKaktus = pomozni.vrhJeKaktus;
  155. //vrnemo niz, ki predstavlja kaktusov sklad
  156. return niz;
  157. }
  158. //--copy
  159. //pomožna metoda, ki naredi kopijo kaktusovega sklada
  160. private KaktusovSklad copy(){
  161. KaktusovSklad kopija = new KaktusovSklad();
  162. kopija.korenKaktusa = this.korenKaktusa;
  163. kopija.vrhJeKaktus = this.vrhJeKaktus;
  164. if(this.vrhJeKaktus){ //če je vrh kaktusov sklad:
  165. //naredimo še kopijo vrhnjega kaktusovega sklada:
  166. kopija.vrhKaktusa = ((KaktusovSklad)this.vrhKaktusa).copy(); //rekurzivno kličemo metodo
  167. }
  168. else{
  169. kopija.vrhKaktusa = this.vrhKaktusa;
  170. }
  171. return kopija;
  172. }
  173. //--izpisi
  174. //metoda, ki izpiše kaktusov sklad
  175. public void izpisi(){ //izpiše kaktusov sklad od spodnjega (najbolj levo) do vrhnjega elementa (najbolj desno)
  176. System.out.println(this);
  177. }
  178. }

Testni program

  1. public class Test{
  2. public static void main (String[] args) throws Exception{
  3. KaktusovSklad ks1 = new KaktusovSklad();
  4. try{
  5. ks1.odstrani(); //preverimo, ali vrže napako na praznem kakt. skladu
  6. }
  7. catch(Exception e){
  8. System.out.println(e.getMessage());
  9. }
  10. ks1 = ks1.vstavi("Jelka");
  11. ks1 = ks1.vstavi("Zupanec");
  12. System.out.println("Kaktusov sklad 1: " + ks1);
  13. System.out.println ("Vrednost vrhnjega elementa v kaktusovem skladu 1: " + ks1.vrh());
  14.  
  15. KaktusovSklad ks2 = new KaktusovSklad();
  16. ks2 = ks2.vstavi("Jelka1");
  17. ks2 = ks2.vstavi("Jelka2");
  18. ks2 = ks2.vstavi("Jelka3");
  19. ks2 = ks2.vstavi("Jelka4");
  20. ks2 = ks2.vstavi("Jelka5");
  21. System.out.println("Kaktusov sklad 2: " + ks2);
  22. System.out.println("Kaj je na vrhu ks2? " + (ks2.kajNaVrhu()?"KaktusovSklad":"Element"));
  23. System.out.println ("Vrednost vrhnjega elementa v k. skladu 2: " + ks2.vrh());
  24. System.out.println ("Vrednost korena v k. skladu 2: " + ks2.koren());
  25. ks1 = ks1.vstavi(ks2);
  26. System.out.println ("Kaktusov sklad 1, ko smo mu dodali k.sklad 2: " + ks1);
  27. System.out.println("Kaj je na vrhu ks1? " + (ks1.kajNaVrhu()?"KaktusovSklad":"Element"));
  28. System.out.println ("Vrednost vrhnjega elementa v k. skladu 2: " + ks2.vrh());
  29. System.out.println ("Vrednost vrhnjega elementa v korenu v k.skladu 1: " + ks1.koren().vrh());
  30.  
  31. KaktusovSklad ks3 = new KaktusovSklad(ks1.vrh());
  32. System.out.println ("Vrednost vrhnjega elementa v k.skladu 3: " + ks3);
  33. try{
  34. ks3.odstrani();
  35. }
  36. catch(Exception e){
  37. System.out.println(e.getMessage());
  38. }
  39. System.out.println ("Ali je k. sklad 3 prazen? " + (ks3.prazen()?"DA":"NE"));
  40.  
  41. KaktusovSklad ks4 = new KaktusovSklad();
  42. ks4 = ks4.vstavi("Računalništvo");
  43. ks3 = ks3.vstavi(ks4);
  44. System.out.println ("Kaktusov sklad 3, ko smo mu dodali k. sklad 4: " + ks3);
  45. System.out.println ("Vrednost vrhnjega elementa v k. skladu 3: " + ks3.vrh());
  46. try{
  47. ks3 = ks3.odstrani();
  48. }
  49. catch(Exception e){
  50. System.out.println(e.getMessage());
  51. }
  52. System.out.println ("Vrednost vrhnjega elementa v kaktusovem skladu 3, po odstranitvi vrha: " + ks3.vrh());
  53. System.out.println ("Ali je kaktusov sklad 4 prazen? " + (ks4.prazen()?"DA":"NE"));
  54. }
  55. }

Če program Test zaženemo v Javi, nam izpiše:

  1. > java Test
  2. Kaktusov sklad je že prazen!
  3. Kaktusov sklad 1: [ Zupanec Jelka ]
  4. Vrednost vrhnjega elementa v kaktusovem skladu 1: Zupanec
  5. Kaktusov sklad 2: [ Jelka5 Jelka4 Jelka3 Jelka2 Jelka1 ]
  6. Kaj je na vrhu ks2? Element
  7. Vrednost vrhnjega elementa v k. skladu 2: Jelka5
  8. Vrednost korena v k. skladu 2: [ Jelka4 Jelka3 Jelka2 Jelka1 ]
  9. Kaktusov sklad 1, ko smo mu dodali k.sklad 2: [ [ Jelka5 Jelka4 Jelka3 Jelka2 Jelka1 ] Zupanec Jelka ]
  10. Kaj je na vrhu ks1? KaktusovSklad
  11. Vrednost vrhnjega elementa v k. skladu 2: Jelka5
  12. Vrednost vrhnjega elementa v korenu v k.skladu 1: Zupanec
  13. Vrednost vrhnjega elementa v k.skladu 3: [ Jelka5 ]
  14. Ali je k. sklad 3 prazen? DA
  15. Kaktusov sklad 3, ko smo mu dodali k. sklad 4: [ [ Računalništvo ] ]
  16. Vrednost vrhnjega elementa v k. skladu 3: Računalništvo
  17. Vrednost vrhnjega elementa v kaktusovem skladu 3, po odstranitvi vrha: null
  18. Ali je kaktusov sklad 4 prazen? NE
Osebna orodja