Sklad

Iz MaFiRaWiki

Sklad je podatkovna struktura, ki deluje po načelu LIFO (Last In First Out - zadnji noter, prvi ven) . To pomeni, da podatek, ki je zadnji prišel v sklad, ga bo tudi prvi zapustil.

Vsebina

Predstavitev sklada

Za podatkovno strukturo sklad je povsem dovolj, da poznamo njen vrh, kajti tja vstavljamo in od tam brišemo podatke, ter da poznamo razvrstitev elementov. Vrh označuje indeks zadnjega prispelega elementa in je nič, če je sklad prazen.


Osnovne operacije na skladu so: pripravi prazen sklad, je sklad prazen, vrh sklada, briši element s sklada, dodaj element v sklad.

Formalni opis podatkovne strukture sklad

Structure SKLAD

begin

declare - naštejemo operacije z vhodnimi in izhodnimi podatki
- opis funkcij
// Pripravi prazen sklad.
pripravi: 0 → sklad;
// Vstavi podatek v sklad in vrne novi sklad.
vstavi: (sklad, podatek) → sklad;
// Vrne podatek, ki je na vrhu sklada.
vrh: sklad → podatek;
// Izbriše vrhnji element sklada in vrne novi sklad.
odstrani: sklad → sklad;
// Ali je sklad prazen?
prazen: sklad → {true, false};


where - opis pravil obnašanja funkcij
// kako se obnaša operacija prazen
// dve možnosti - dobi prazen sklad ali pa dobi neprazen
prazen(pripravi) ::= true;
prazen(vstavi(s, p)) ::= false;
// kako se obnaša operacija odstrani
// spet dve možnosti – dobi prazen sklad ali pa dobi neprazen sklad
odstrani(pripravi) ::= NAPAKA;
odstrani(vstavi(s, p)) ::= s;
// kako se obnaša operacija vrh
vrh(pripravi) ::= NAPAKA;
vrh(vstavi(s, p)) ::= p;

end // obnašanja operacij, pripravi in vstavi, ni bilo potrebno opisati – sta že določeni z obnašanjem ostalih!

Pri tem sta operaciji pripravi in dodaj konstruktorja, medtem ko je npr. operacija vrh selektor.

Predstavitev sklada s tabelo

Glej: Izpitno vprašanje RAČ2PRA 4300

Zgled

Implementacija

  • Sklad najlažje implementiramo s tabelo. Kazalec vrh kaže na mesto, kjer je vrh sklada in pove, do kod je zapolnjena tabela.

Zgled uporabe

Sestavi metodo public static void odstraniSamoglasnike(Sklad<Character> s), ki iz sklada odstrani vse samoglasnike.

Ideja

Naredimo pomožni sklad v katerega bomo prelagali elemente iz prvotnega sklada. In sicer, če element na vrhu sklada ni samoglasnik, ga vstavimo v pomožni sklad, sicer če je samoglasnik, ga odstranimo iz prvotnega sklada. Ponavljamo toliko časa, dokler sklad ni prazen. Na koncu preložimo vse elemente iz pomožnega sklada nazaj v prvotni sklad.

Primer:

Če imamo npr. podan sklad, Sklad s = {'a','k','l','e'}. Vidimo, da je vrh sklada s znak a, je samoglasnik, zato ga odstranimo iz sklada s. Naslednji znak je k, ni samoglasnik, zato ga vstavimo na vrh pomožnega sklada, iz sklada s ga odstranimo. Znak l ni samoglasnik, vstavimo ga na vrh pomožnega sklada, iz sklada s ga odstranimo. Naslednji je e, je samoglasnik zato ga odstranimo iz sklada s. Sedaj je sklad s prazen v pomožnem skladu pa imamo {'l','k'}. Na koncu preložimo elemente iz pomožnega sklada nazaj v sklad s.

Naš prvoten sklad (Sklad s):

Če znak ni samoglasnik ga vstavimo v pomožni sklad:

Končen sklad ( pomožen sklad smo prestavili nazaj v prvoten sklad ):


Rešitev:

  1.  
  2. public class OdstraniSamoglasnike{
  3. public static void odstraniSamoglasnike(Sklad<Character> s) throws Exception{
  4. Sklad<Character> pom = new Sklad<Character>();
  5. String samogl = "AEIOUaeiou";
  6. // ponavljamo dokler sklad ni prazen
  7. while(!s.prazen()){
  8. char ss = s.vrh();
  9. // če element ni samoglasnik ga vstavimo v pomožen sklad
  10. if (samogl.indexOf(ss) == -1){
  11. pom.vstavi(ss);
  12. }
  13. // sicer ga odstranimo
  14. s.odstrani();
  15. }
  16. // iz pomožnega sklada prenesmo elemente nazaj v sklad s
  17. while(!pom.prazen()){
  18. s.vstavi(pom.vrh());
  19. pom.odstrani();
  20. }
  21. }
  22. // primer za preizkus delovanja programa
  23. public static void main(String[] args) throws Exception{
  24. Sklad<Character> pom = new Sklad<Character>();
  25. pom.vstavi('a');
  26. pom.vstavi('6');
  27. pom.vstavi('f');
  28. pom.vstavi('z');
  29. pom.vstavi('A');
  30. pom.vstavi('O');
  31. pom.vstavi('i');
  32. System.out.println(pom);
  33. odstraniSamoglasnike(pom);
  34. System.out.println(pom);
  35. }
  36. }


Programki jezik java že pozna razred, ki predstavlja sklad to je razred Stack. Vsebuje naslednje metode:

  • empty vrne true, če je sklad prazen;
  • peek vrne prvi objekt na skladu in ga ne zbriše;
  • pop vrne prvi objekt s sklada in ga zbriše;
  • push doda objekt na vrh sklada;
  • search najde objekt na skladu in vrne razdaljo od vrha do objekta;


Isti primer predstavljen z uporabo sklada definiranega v javi pa bi izgledal takole:

  1.  
  2. import java.util.*;
  3.  
  4. public class OdstraniSamoglasnike{
  5. public static void odstraniSamoglasnike(Stack<Character> s) throws Exception{
  6. Stack<Character> pom = new Stack<Character>();
  7. String samogl = "AEIOUaeiou";
  8. // ponavljamo dokler sklad ni prazen
  9. while(!s.empty()){
  10. char ss = s.peek();
  11. // če element ni samoglasnik ga vstavimo v pomožen sklad
  12. if (samogl.indexOf(ss) == -1){
  13. pom.push(ss);
  14. }
  15. // sicer ga odstranimo
  16. s.pop();
  17. }
  18. // iz pomožnega sklada prenesmo elemente nazaj v sklad s
  19. while(!pom.empty()){
  20. s.push(pom.peek());
  21. pom.pop();
  22. }
  23. }
  24. // primer za preizkus delovanja programa
  25. public static void main(String[] args) throws Exception{
  26. Stack<Character> pom = new Stack<Character>();
  27. pom.push('a');
  28. pom.push('6');
  29. pom.push('f');
  30. pom.push('z');
  31. pom.push('A');
  32. pom.push('O');
  33. pom.push('i');
  34. System.out.println(pom);
  35. odstraniSamoglasnike(pom);
  36. System.out.println(pom);
  37. }
  38. }

Še nekaj zgledov uporabe

Glej tudi

Zunanji viri

Osebna orodja