Kaktusov sklad

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Kratek opis

Kaktusov sklad je posebna oblika sklada. Že samo ime nam pove, da ima obliko razvejanega kaktusa. Podatkovna struktura kaktusov sklad je podobna podatkovni strukturi sklad, vendar sklad je sestavljen iz "enostavnih" elementov, medtem ko je kaktusov sklad sestavljen iz "enostavnih" elementov in kaktusovih skladov.

Kaktusov sklad je različica sklada v kateri lahko na vrh dodamo še kakšen drug kaktusov sklad. Dodani kaktusov sklad se imenuje veja. Ko veja postane prazna je odstranjena. Kaktusov sklad je načeloma preprost navaden sklad sam je nekaj posebnega, ker se lahko razraste do onemoglosti(vsaka veja ima lahko spet veje), od tu tudi ime kaktusov sklad. Ko na primer dodamo en element, je ta element lahko kaktusov sklad z enim elementom. Ime kaktusov sklad je dobil po kaktusih, saj ima obliko kot kaktusi na sliki.

Slika:kaktus.jpg.jpg

Drugi imeni za kaktusov sklad sta še spaghetti sklad in saguaro sklad (saguaro je vrsta razvejanega kaktusa).

Operacije nad kaktusovem skladom:

  1. pripravi kaktusov sklad
  2. vstavi element v kaktusov sklad
  3. vstavi sklad v kaktusov sklad
  4. element na vrhu sklada
  5. odstrani
  6. prazen

Zgodovina

Takšno strukturo (vendar ne pod imenom kaktusov sklad) sta prva "izumila", oz. uvedla Bobrow in Wegbreit (oktobra leta 1973 pa sta objavila članek na to temo).


Opis podatkovne strukture

Kaktusov sklad je podatkovna struktura, zato potrebujemo nek prostor v katerega bomo hranili podatke. Elementi v kaktusovem skladu so bodisi posamezni podatki, bodisi kaktusovi skladi. Na spodnji sliki je prikazana oblika kaktusovega sklada:

Slika:kaktusovsklad2.jpg

Operacije nad kaktusovim skladom

Osnovne operacije

pripravi()

Pripravi prostor, v kateremu bomo lahko hranili podatke.

vrh()

Vrh je lahko različen, pogledati moramo:

- če je kaktusov sklad prazen, potem vrne napako, ker prazen kaktusov sklad nima vrhnjega elementa

- če je vrh kaktusovega sklada "enostaven" element, vrne ta element

- če je vrh kaktusov sklad, potem vrne vrhnji element tega kaktusovega sklada

odstrani()

Imamo različne možnosti:

- če je kaktusov sklad prazen, potem vrne napako, ker ne moremo odstraniti nobenega elementa, ker ga ne vsebuje

- če je vrh kaktusovega sklada "enostaven" element, odstrani ta element

- če je vrh kaktusovega sklada s kaktusov sklad s1, potem odstranimo vrhnji element v kaktusovem skladu s1

vstavi(element, kaktusov sklad)

Vstavi "enostaven" element v kaktusov sklad, ta element je potem vrh.

vstavi(kaktusov sklad s1, kaktusov sklad)

Vstavi kaktusov sklad s1 v kaktusov sklad s, v tem primeru je vrh kaktusov sklad s1.

prazen()

Preveri, če je kaktusov sklad prazen. Če je, vrne logično vrednost true, sicer false

Pomožne operacije

koren()

Koren kaktusovega sklada je kaktusov sklad do nevključno vrha.

odstraniElement()

Pomožna metoda, ki je potrebna za metodo odstrani().

copy()

Pomožna metoda, ki naredi kopijo kaktusovega sklada. Ko kopiraš objekt katerega koli tipa, moraš vsako komponento posebej prepisat. Pri objektu kaktusov sklad je dodaten problem pri prepisovanju, saj je njegova komponenta zopet kaktusov sklad in vrh je lahko tudi. Torej ko kopiraš celoto moraš kopirati po komponentah.

izpisi()

Izpisovanje kaktusovega sklada ne gre brez odstranjevanja, zato moraš sproti kopirati v pomožen kaktusov sklad. Pri izpisu se vidi, kje se začne in kje se posamezna kakšna veja.

kajNaVrhu()

Metoda, ki vrne true, če je na vrhu kaktusovega sklada kaktusov sklad in false, če je na vrhu kaktusovega sklada element.

Kratek opis odstranjevanja elementov iz kaktusovega sklada S

Postopek je opisan s pomočjo slikice zgoraj.

Če želimo odstraniti element v kaktusovem skladu S, moramo najprej pogledati vrh tega kaktusovega sklada S; v tem primeru je vrh element, ki ga tako lahko odstranimo, podobno kot v običajnem skladu. Ko pa želimo odstraniti še en element, pogledamo zopet vrh in tokrat je vrh kaktusov sklad 4, zato moramo odstraniti vrhnji element v tem kaktusovem skladu. Slednji kaktusov sklad 4 kopiramo v pomožni kaktusov sklad in iz tega pomožnega odstranimo vrh in ga nato vstavimo v kaktusov sklad S. S tem sta v kaktusovem skladu odstranjena prva dva elementa, a postopek lahko nadaljujemo peljemo tako dalje, dokler ne bo kaktusov sklad 4 odstranjen, s čimer bodo odstranjeni vsi elementi le-tega. Omenjeni postopek lahko nadaljujemo, dokler še obstaja kakšen element v kaktusovem skladu (dokler ni kaktusov sklad prazen).

Struktura kaktusovega sklada

  1. structure KAKTUSOV_SKLAD
  2. begin
  3. declare // nastejemo operacije z vhodnimi in izhodnimi podatki
  4. pripravi: 0 --> kaktusov sklad;
  5.  
  6. vstavi: (podatek, kaktusov sklad) --> kaktusov sklad;
  7. // v kaktusov sklad vstavimo "enostaven" podatek
  8.  
  9. vstavi: (kaktusov sklad S1, kaktusov sklad S)
  10. --> kaktusov sklad
  11. // v kaktusov sklad S vstavimo kaktusov sklad S1
  12.  
  13. vrh: kaktusov sklad --> podatek
  14.  
  15. odstrani: kaktusov sklad --> kaktusov sklad;
  16.  
  17. prazen: kaktusov sklad --> {true, false};
  18.  
  19. where //opis delovanja operacij
  20.  
  21. //kako se obnaša operacija prazen
  22. //dve možnosti - dobi prazen kaktusov
  23. //sklad ali pa dobi neprazen kaktusov sklad
  24.  
  25. prazen(pripravi) ::= true;
  26. // kako deluje metoda na poljubnem praznem kaktusovem skladu
  27.  
  28. prazen(vstavi(podatek, kaktusov sklad)) ::= false;
  29. // kako deluje metoda na poljubnem
  30. //nepraznem kaktusovem skladu, ki ima na
  31. //vrhu "navaden" podatek
  32. prazen(vstavi(kaktusov sklad S1, kaktusov sklad S)) ::= false;
  33. //kako deluje metoda na poljubnem nepraznem kaktusovem skladu,
  34. //ki ima na vrhu kaktusov sklad S1
  35. //kako se obnaša operacija odstrani
  36. //spet dve možnosti - dobi prazen kaktusov sklad ali pa
  37. //dobi neprazen kaktusov sklad
  38. odstrani(pripravi) ::= NAPAKA; // kako deluje metoda
  39. //na poljubnem praznem skladu
  40.  
  41. //če smo v kaktusov sklad na zadnje vstavili "enostaven" podatek
  42. odstrani(vstavi(podatek, kaktusov sklad)) ::= kaktusov sklad;
  43. //če odstranimo podatek, ki smo ga na zadnje vstavili v
  44. //kaktusov sklada, dobimo kaktusov sklad vendar
  45. //brez vrha (podatka, ki smo vstavili)
  46.  
  47. //če smo v kaktusov sklad na zadnje vstavili kaktusov sklad S1
  48. odstrani(vstavi(kaktusov sklad S1, kaktusov sklad S)) ::=
  49. //S1 ne more biti prazen, ker drugače
  50. //ne bi bil v kaktusovem skladu
  51. if (prazen(odstrani(S1))) return S;
  52. // če je S1 kaktusov sklad z le enim elementom
  53. //prazen kaktusov sklad namrec brišemo!
  54. return vstavi(odstrani(S1), S);
  55. // kaktusov sklad S1 brez vrhnjega
  56. //elementa damo nazaj v kaktusov sklad S
  57.  
  58. // kako se obnaša operacija vrh
  59. vrh(pripravi) ::= NAPAKA;
  60.  
  61. //če smo v kaktusov sklad na zadnje vstavili "enostaven" podatek
  62. vrh(vstavi(podatek, kaktusov sklad)) ::= podatek
  63. //če smo na zadnje vstavili v kaktusov sklad podatek, potem je
  64. vrh kaktusovega sklada ta podatek
  65.  
  66. //če smo na zadnje v kaktusov sklad vstavili kaktusov sklad S1
  67. vrh(vstavi(kaktusov sklad S1, kaktusov sklad S)) ::=
  68. //če je na vrhu kaktusov sklad
  69. return vrh(S1);//vrnemo vrhnji element v kaktusovem skladu S1
  70.  
  71. end; //obnašanja operacij pripravi in vstavi ni bilo potrebno opisati -
  72. //sta že določeni z obnašanjem ostalih!

Implementacija v Javi

Kratek opis

Kaktusov sklad sem implementirala takole: sestavljen je iz dveh delov korena kaktusovega sklada in vrha kaktusovega sklada. Vrh kaktusovega sklada sem obravnavala posebej, saj ko delamo z kaktusovim skladom (brišemo, vstavljamo..) vedno pogledamo vrh kaktusovega sklada. Ta vrh kaktusovega sklada pa je lahko "enostaven" element ali pa kaktusov sklad. Zato sem v razredu kaktusov sklad definirala 3 komponente:

  1. KaktusovSklad korenKaktusa
  2. Object vrhKaktusa
  3. boolean vrhJeKaktus

S pomočjo teh komponent sem napisala dva konstruktorja:

  1. KaktusovSklad()
  2. KaktusovSklad(Object element)

Prvi ustvari prazen kaktusov sklad z nedoločenim (neobstoječim) korenom in vrhom, Drugi konstruktor pa sprejme objekt poljubnega tipa, ustvari kaktusov sklad z nedoločenim (neobstoječim) korenom ter vrhom element. Nato sem napisala metode za vstavljanje elementov, brisanje elementov, kaj je vrh kaktusovega sklada... Pri vseh metodah je potrebno preveriti, če ni kaktusov sklad prazen. Kaktusov sklad pa je prazen, če je prazen vrhKaktusa in korenKaktusa. Pri pisanju metod za vstavljanje, brisanje sem si pomagala pomožnim kaktusovim skladom.

Vse metode so opisane in uporabljene v spodnji implementaciji.

Implementacija

Glej tudi

Zunanje povezave

http://www.nist.gov/dads/HTML/cactusstack.html

http://en.wikipedia.org/wiki/Spaghetti_stack

http://www.memorymanagement.org/glossary/c.html

Osebna orodja