Izpitno vprašanje DIRI2005 4200

Iz MaFiRaWiki

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

Vsebina

Vprašanje

Formalno opiši podatkovno strukturo sklad.

Odgovor

Sklad je podatkovna struktura, ki ima značilnost, da se implementira po protokolu zadnji not, prvi ven (ang. last-in-first-out ==> LIFO). To pomeni, da lahko dostopamo le do objekta, ki je v skladi najvišje oziroma je to objekt, ki smo ga v sklad vstavili nazadnje. Glede na to, da lahko dostopamo le do zadnjega elementa mora imeti vsak elemet le še kazalec na element, ki smo ga vstavili pred njim. Torej ima vsak element informacijo, kdo je pred njim. Če strukturo predstavimo v tabeli (Array) pa je to njegov desni sosed.

Sklad
Slika1: Sklad.

Če bi radi v skladu dostopali do elementa, ki smo ga v sklad dali kot prvega, moramo vse elemente, ki smo jih v sklad dali za njim preložiti nekam drugam, običajno v drug sklad ali izbrisati.

Osnovne operacije nad skladom:

  • ustvarjanje praznega sklada,
  • vstavljanje (dodajanje) elementa v sklad,
  • dostopanje do elementa na vrhu sklada (ga le pogledamo),
  • brisanje elementa na vrhu sklada,
  • preverjanje ali je sklad prazen.

Zakonitosti:

  • ustvarjanje sklad.pripravi() --> ustvari prazen sklad
  • vstavi (ang. push); sklad.vstavi(p) ---> sklad (z novim elementom p)
  • sklad.prazen()
    • sklad.prazen(pripravi()) --> true
    • sklad.prazen(vstavi(p)) --> false
  • vrh (ang. peek); sklad.vrh() ---> element oz. podatek na vrhu, sklad ostane nespremenjen
    • sklad.vrh(vstavi(p)) --> p
    • sklad.odstrani(vstavi(p)) --> sklad
  • odstrani (ang. pop); sklad.odstrani() ---> element oz. podatek na vrhu
    • če operaciji vrh ali vzami vršimo nad praznim skladom:
    • sklad.vrh(pripravi()) ---> NAPAKA!
    • sklad.vzami(pripravi()) ---> NAPAKA!

Primer sklada

  1. import java.util.Stack;
  2. import javax.swing.*;
  3.  
  4. public class Sklad {
  5. public static void main(String[] args) {
  6.  
  7. Stack <String> sklad = new Stack <String>(); // sklad, ki ga sami ustvarite
  8.  
  9. int koliko = Integer.parseInt(JOptionPane.showInputDialog("Koliko elementov boste vnesli? "));
  10. while ( koliko > 0 ) {
  11. sklad.push(JOptionPane.showInputDialog("Vnesi vrednost elementa v sklad")); // branje v sklad
  12. koliko--;
  13. }
  14. System.out.println("Elementi v skladu, ki ste ga ustvarili: " + sklad); // primer operacij na skladu
  15.  
  16. Stack <String> sklad1 = new Stack <String>(); // ustvarjanje novega sklada
  17. sklad1.push("danes"); // vstavljanje v sklad
  18. sklad1.push("je");
  19. sklad1.push("lep");
  20. sklad1.push("dan");
  21. System.out.println("");
  22. System.out.println("Elementi v skladu1:");
  23. System.out.println(sklad1); // izpis elementov v skladu
  24. System.out.println("sklad1.peek(): " + sklad1.peek()); // pogleda element na vrhu sklada
  25. System.out.println(sklad1);
  26. System.out.println("sklad1.pop(): " + sklad1.pop()); // vzame element na vrhu sklada, ga zbriše
  27. System.out.println(sklad1);
  28. System.out.println("sklad1.pop(): " + sklad1.pop());
  29. System.out.println(sklad1);
  30. System.out.println("sklad1.push(\"kaj\"): ");
  31. sklad1.push("kaj");
  32. System.out.println(sklad1);
  33. System.out.println("");
  34. System.out.println("Izpraznimo sklad.");
  35. while ( !sklad1.empty()) { // zanka, ki izprazni sklad
  36. sklad1.pop();
  37. System.out.println(sklad1);
  38. }
  39.  
  40. }
  41. }

Izhod

  • Elementi v skladu, ki ste ga ustvarili: [...]
  • Elementi v skladu1:
  • [danes, je, lep, dan]
  • sklad1.peek() --> dan
  • dan
  • [danes, je, lep, dan]
  • sklad1.pop() --> dan
  • [danes, je, lep]
  • sklad1.pop() --> lep
  • [danes, je]
  • sklad1.push("kaj") --> [danes, je, kaj]
  • Izpraznimo sklad.
  • [danes, je]
  • []

Osebna orodja