Izpitno vprašanje RAČ2PRA 4200

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka MojcaVaupotic.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Formalno opiši podatkovno strukturo sklad.

Odgovor

  1. structure SKLAD
  2. begin
  3. declare //naštejemo operacije z vhodnimi in izhodnimi podatki
  4. pripravi: 0 --> sklad;
  5. vstavi: (sklad, podatek) --> sklad;
  6. vrh: sklad --> podatek;
  7. odstrani: sklad --> sklad;
  8. prazen: sklad --> {true, false};
  9. where //opis delovanja operacij
  10. // kako se obnaša operacija prazen
  11. // dve možnosti – dobi prazen sklad ali pa dobi neprazen sklad
  12. prazen(pripravi) ::= true; // kako deluje metoda na poljubnem praznem skladu
  13. prazen(vstavi(s,p)) ::= false; // kako deluje metoda na poljubnem nepraznem skladu
  14. // kako se obnaša operacija odstrani
  15. // spet dve možnosti – dobi prazen sklad ali pa dobi neprazen sklad
  16. odstrani(pripravi) ::= NAPAKA; // kako deluje metoda na poljubnem praznem skladu
  17. odstrani(vstavi(s,p)) ::= s; // vstavi(s,p) je LE EDEN OD NAČINOV, kako dobimo neprazen sklad
  18. // kako se obnaša operacija vrh
  19. vrh(pripravi) ::= NAPAKA; // lahko bi tudi bilo vrh(odstrani(vstavi(pripravi,p))) ::= NAPAKA
  20. vrh(vstavi(s,p)) ::= p;
  21. end;
  22. // obnašanja operacij pripravi in vstavi ni bilo potrebno opisati – sta že določeni z obnašanjem ostalih!
  23.  

Podatkovna struktura sklad deluje po principu prvi noter, zadnji ven ali zadnji noter, prvi ven – LIFO (Last In First Out), kar pomeni, da bo element, ki smo ga zadnjega dodali v sklad, hkrati prvi, ki ga bomo odstranili. Torej vstavljamo in jemljemo na enem koncu.

  • Operacije:
    - pripravi sklad
    - vstavi element v skald (push): doda nov element na sklad, če ga ne more dodati, to sporoči (ko je sklad poln)
    - element na vrhu sklada (peek)
    - odstrani (pop): pobere element iz sklada, če ga ne more pobrati, to sporoči (ko je sklad prazen)
    - prazen (empty): pove, če je sklad prazen
    - top: vrne element, ki je na vrhu sklada, če ga ne more, to sporoči ( če elementa ni oziroma, če je sklad prazen sporoči napako)
Osebna orodja