Izpitno vprašanje RAČ2PRA 4500

Iz MaFiRaWiki

Vprašanje

Opiši, kako bi sklad predstavil v Javi.

Odgovor

Sklad je podatkovna struktura, ki deluje po načelu LIFO (Last In First Out - zadnji noter, prvi ven). To pomeni, da podatek, ki je pride zadnji v sklad, sklad prvi zapusti, oziroma povedano drugače - iz sklada vedno dobimo tisti podatek, ki je med vsemi elemnti v skladu najmanj časa. 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.

Osnovne operacije na skladu so:

  • pripravi sklad
  • vstavi element v sklad (push)
  • element na vrhu sklada (peek)
  • odstrani (pop)
  • prazen (empty


Sklad lahko uporabimo pri rezličnih nalogah kot so:

  • Obiskane strani v brskalniku
  • Zaporedje UNDO ukazov
  • računalniški sklad (rekurzija, dodeljevanje pomnilnika ob klicu funkcij, …),
  • Sklad klicev metod v JVM
  • Pomožni pomnilnik pri različnih algoritmih
  • Del drugih podatkovnih struktur


Formalna predstavitev sklada:

structure SKLAD
begin
   declare // naštejemo operacije z vhodnimi in izhodnimi podatki
		pripravi: 0 \rightarrow sklad;
		vstavi: (sklad, podatek) \rightarrow sklad;
		vrh: sklad \rightarrow podatek;
		odstrani: sklad \rightarrow sklad;
		prazen: sklad \rightarrow {true, false};
   where // opis delovanja operacij
		// kako se obnaša operacija prazen
		// dve možnosti – dobi prazen sklad ali pa dobi neprazen sklad
		prazen(pripravi) ::= true; // kako deluje metoda na poljubnem praznem skladu
		prazen(vstavi(s,p)) ::= false; // kako deluje metoda na poljubnem nepraznem skladu
		// kako se obnaša operacija odstrani
		// spet dve možnosti – dobi prazen sklad ali pa dobi neprazen sklad
		odstrani(pripravi) ::= NAPAKA; // kako deluje metoda na poljubnem praznem skladu
		odstrani(vstavi(s,p)) ::= s;  // vstavi(s,p) je LE EDEN OD NAČINOV, kako dobimo neprazen sklad
		// kako se obnaša operacija vrh
		vrh(pripravi) ::= NAPAKA; // lahko bi tudi bilo vrh(odstrani(vstavi(pripravi,p))) ::= 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!

Sklad lahko predstavimo z:

  • tabelo
  • linearnim seznamom (verižnim seznamom)

Predstavitev s tabelo:

  • Elemente hranimo v tabeli
  • Potrebujemo še indeks vrhnjega elementa
    • indeks zadnjega vstavljenega elementa
    • indeks prvega prostega mesta
  • prednost: ni težav z zapisom
  • problem: omejena velikost

Predstavitev z verižnim seznamom

  • Sklad predstavimo z verižnim seznamom tako, da so elementi v skladu kar elementi (vozli) seznama.
  • potrebujemo le kazalec na prvi (zgornji v skladu) vozel v verižnem seznamu.
  • Elementi sklada od vrha navzdol ustrezajo elementom seznama od vrha proti dnu.
  • Vstavljanju elementa v sklad torej ustreza vstavljanje novega prvega elementa v seznam, vrh sklada bomo pogledali kot vrednost prvega elementa seznama, brisanje vrha sklada pa ustreza brisanju prvega elementa iz seznama.
  • prednosti: nimamo težav z velikostjo sklada
  • slabost: /

Glej tudi

Osebna orodja