i
i
“Lokar-sklad” — 2010/5/28 — 11:46 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 14 (1986/1987)
Številka 6
Strani 305–309, 301
Matija Lokar:
PODATKOVNA STRUKTURA SKLAD
Ključne besede: matematika, računalništvo, podatkovne strukture,
sklad.
Elektronska verzija: http://www.presek.si/14/859-Lokar.pdf
c© 1987 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
onrll,\lo, N'/C Tl '[1"" __ '1' IL 1_' 1 ~_
PODATKOVNA STRUKTURA SKLAD
S pojmom sklad se v vsakdanjem življenju dokaj pogosto srečamo. Tako se v
jeseni v kleteh pojavijo zaboj čki s krompirjem in jabolki, zloženi drug na
drugem v sklad, železničarji imenujejo sklad razporeditev tirov, ki jim omogo-
ča prestavljanje vagonov, v kuhinjski omarici so krožniki zloženi eden vrh dru-
gega, '"
VHOD
=1= SKLAD
IZHOD
Tudi v računalništvu se pogosto srečamo s pojmomsklada . Pravimo, da je
sklad ena osnovnih podatkovnih struktur. ln kaj sploh je podatkovna struktu-
ra? Najkrajše jo lahko označimo kot skupino podatkov, nad kater imi lahko iz-
vajamo določeno operacije. Definicija sicer ni povsem natančna, tudi pomanj -
kljiva je, a bo za našo rabo povsem zadostna .
Če hočemo torej predstaviti sklad, moramo ugotoviti , katere so operacije,
ki so za sklad najbolj značilne . Odpravimo se zato v skladišče, kjer je gotovo ve-
liko skladov zabojev . Postavimo se tja v kot, da ne bomo v napoto, in opazuj -
mo. Pripeljal je tovornjak, naložen s štedilniki. V il ičarji ga razk ladajo. Prvi za-
boj gre na tla , drugega položijo nanj, na tega spet tretjega, . oo Mimo pride
skladiščnik in nekaj razburjeno vpije. Nekaj je narobe. Aha! Štedilnik, ki so
ga naložili kot drugega, ne spada sem, ker je druge vrste. Kaj pa sedaj? Kar
ven se ga ne da potegniti, saj so nad njim naložen i še trije štedilniki. Zato vili-
čar odstrani zgornji štedilnik, ki je b il naložen zadnji, nato naslednjega, še ene -
ga in šele sedaj pride na vrsto napačni zaboj. En viličar ga odpelje, drugi pa na -
305
loži preostale tri zaboje v sklad . Vidimo, da zaboje jemljejo iz sklada ravno v
obratnem vrstnem redu, kot so jih nanj nalagal i. In to je tudi glavna značilnost
sklada : element, ki prej pride v sklad, ga zapusti kasneje . Zato v tuji literaturi
sklad imenujejo tudi UFO seznam. UFO je kratica za Last ln Fir st Out. Sklad
je torej seznam, kjer element, ki gre zadnji "noter", pride prvi "ven". Pa še eno
značilnost sklada smo lahko opazili v skladišču. Vse, kar se s skladom dogaja,
se dogaja na enem koncu. Na istem koncu nalagamo elemente, z ist ega konca
elemente jemljemo . Zato ta konec zasluži posebno ime. Imenujemo ga vrh
sklada .
Kate re bodo torej operacije, ki jih bomo izvajali nad skladom? Najprej si
moramo prostor za sklad pr ipraviti . Ustezno operacijo bomo imenovali kar
PR IPRAV 1. V sklad vstavljamo in iz njega jemljemo elemente. To bosta izvajali
operaciji VSTAVI in ODSTRANI. Seveda lahko iz sklada jemljemo elemente le
toliko časa, dokler ta ni prazen . S pogojem PRAZEN bomo kontrolirali, če je v
skladu še kaj elementov. Pogosto nas zanima tudi to, kateri element je na vrhu
sklada. To operacijo bomo imenovali VRH.
Operacije smo tako določili. Še vedno pa n ismo nič rekli o tem, zakaj
sklad uporabljamo v računalniku in kako ga v računalniku sploh predstavimo.
Odložimo to še za trenutek in poglejmo, kako b i formalno opisali podatkovno
strukturo sklad.
V prvem delu predstavitve strukture, označenem s declare, naštejemo ope-
racije , ki jih lahko nad to podatkovno strukturo izvajamo, v drugem delu, ozna-
čenem z where, pa bomo našteli pravila, ki jih mo rajo te operacije upoštevati.
Kakorkoli potem predstavimo sklad v računalniku in na kakršenkoli način te
operacije sestavimo kot procedure, mora ta predstavitev zadoščati naštetim
pravilom . Omenimo le operacijo "Prazen", katere rezultat je logična vrednost,
ki jo bomo označili z Boolean. Oznako za ta tip si bomo sposodili iz program-
skega jezika pascal. Izraz tipa Boolean lahko zavzame dve vrednosti, pravilno
(true) ali napačno (falsel .
Sklad je tako definiran in ga lahko uporabimo . Vrste uporabe sklada so v
računalništvu številne . Tako brez sklada ne moremo speljati rekurzije , upora-
bljamo ga pri izračunu izrazov, služi nam za označevanje vrstnega reda obde-
lovanja podatkov, kjer moramo določene korake opraviti šele kasneje , ko so
izpolnjeni d rugi pogoji. Poglejmo si primer . Denimo, da izvajamo nalogo A.
Med izvajanjem pa pridemo do točke, ko moramo najprej opraviti nalogo B,
da bi z nalogo A lahko nadaljevali. Zato se lotimo naloge B. Še prej pa si mo ra-
mo zapomniti, kje moramo nadaljevati , ko bomo končali z nalogo B. Zato v
sklad shranimo potrebne podatke iz naloge A. Pr i opravljanju naloge B pa mo -
ramo spet najprej izvesti nalogo C. Spet shranimo ustrezno informacijo v skla d
306
structure sklad
(* struktura "sklad" nad poljubno zalogo vrednosti tipa "podatek"*)
begin
declare
(*pripravi prazen sk lad *)
p ripravi: lil=> sklad ;
(*vstavi podatek v sklad in vrne nov sklad *)
vstavi : (podatek, sklad) => sklad,
(* vrne podatek, ki je na vrhu sklada *)
vrh: sklad =>podatek;
(* izb riše vrhnji element sk lada in vrne novi sklad * )
odstran i: sklad => sklad;
(* ali je sklad prazen *)
prazen: sklad => Boolean;
where
prazen (pr ipravil := true;
prazen (vstavi (p.sl) := false;
odstrani (pripravi) := napaka;
odstrani (vstavi (p,s)) := s;
vrh (pripravi) := napaka;
vrh (vstav i (p,s)) := p;
end.
in pne nemo izvajati nalogo C. Po nekaj korakih ta spet zahteva, da najprej
opravimo nalogo D. V sklad shranimo podatke o C in se lotimo naloge D. To
uspešno končamo. Kaj pa sedaj? Edina naloga , ki jo lahko izvajamo, je nalo-
ga C, saj A zahteva, da je končana naloga B, le-ta pa, da je končana naloga
C. Nalogo C vzamemo z vrha sklada in izvedemo do konca. Nadaljujemo z
izvajanjem naslednje naloge na vrhu sklada. To je naloga B. Vendar po nekaj
korakih le-ta spet zahteva, da dokončamo še nalogo E. Zato B ponovno uvrsti-
mo v sklad in izvedemo nalogo E. Ko to končamo , se ponovno lotimo vrhnje
naloge v skladu, B, in ko je opravljena, iz sklada vzamemo še zadnjo nalogo A
in jo dokončamo. Spreminjanje sklada je prikazano na sl iki 2.
Vidimo, da v vsakem trenutku med obdelavo sklad avtomatično vzdržuje
vrstni red , potreben za uspešno izvajanje naloge . Na ta način računalnik tudi
nadzoruje izvajanje programa, č e je A glavn i program, B, C, D in E pa ustrezni
podprogrami.
Ostane nam le še , da sklad predstav imo v r ač u na l n i k u . Načinov predstavi-
tve je več , odv isno tu d i od uporabe določenega programskega jez ika . Uporab ili
307
Slika 2
- I,-EEI 1-1 A -
E8-1 I-EB -IA A I - I
bomo kar BASIC in predstavitev s pomočjo tabele .
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. Če uporabimo linearno predstavitev ali predstavitev s tabelo, je
vrstni red določen kar z indeksom elementa v tabeli. Element, ki je na vrhu
sklada, ima najvišji indeks, njegov predhodnik indeks za eno manjš i, Oo. V de-
finiciji sklada nikjer nismo omejili števila elementov, ki so naenkrat lahko v
skladu. Ker pa si moramo za tabelo rezervirati prostor , bomo z VELIKOST
označili maksimalno število elementov, ki jih i stoč asno lahko vodimo v skladu.
Kot smo rekli, bomo sklad predstavili s tabelo, k i ji bomo rekli SKLAD . Potre -
bujemo še spremenljivko , ki označuje vrh sklada . To naj bo kar VRH.
Če smo v sklad zaporedoma vstav ili števila 3, 1, 6 in 8 in imamo v skladu
prostor za 9 elementov, bo sklad v tem trenutku predstavljen ta kole:
VELIKOST = 9
VRH = 4
SKLAD ( 1) = 3 SKLAD( 4) = 8 SKLAD(7) =
SKLAD (2) = 1 SKLAD( 5) SKLAD(8 ) =
SKLAD(3) = 6 SKLAD(6) = SKLAD(9) =
Sestavimo sed aj podprog ram, s pomoč j o katerih izvajamo potrebne ope-
racije .
10 REM
20 REM pri pr avi skl ad vel i kosti VELIKOST z vr hom VRH
30 REM
40 VELIKOST = . . .
50 DI MSKL AD(VELIKOST)
60 VRH = O
70 RETURN
308
Matija Lokar
•
100 REM
110 REM če je sklad prazen, dobi spremenljivka PRAZEN
120 REM vrednost 1, drugače O
130 REM
140 PRAZEN = O
150 IF VRH = O THEN PRAZEN =
160 RETURN
200 REM
210 RB~ vstavi podatek ELE}lliNT v sklad
220 REM
230 IF VRH < VELIKOST THEN GOTO 260
240 REM sklad je poln - primerno ukrepamo
250
260 REM sklad ni poln
270 VRH = VRH + 1
280 SKLAD(VRH) = ELEMENT
290 RETURN
300 REM
310 REM briše podatek iz sklada in ga shrani v ELEl"'lENT
320 REM
330 IF VRH = O THEN ... : REM napaka, primerno ukrepamo
340 ELEMENT = SKLAD(VRH)
350 VRH = VRH - 1
360 RETURN
Zadnji podprogram vsebuje v sebi dve operaciji: ODSTRANI, ki iz sklada
naredi nov sklad, in VRH, ki vrne vrhnji element v skladu. S ... smo označili
mesta, kjer vpišemo ukaze, ki ustrezajo uporabi sklada v programu. Tako
lahko prekinemo izvajanje programa in sporočimo napako, lahko pokličemo
ustrezni podprogram, oo. Odvisno pač od situacije, v kateri uporabljamo sklad.
V nekaterih primerih bo to znak, da je v programu napaka, drugič spet le
znamenje, da program potrebuje večj i sklad .
V začetku smo omenili, da je sklad le ena od osnovnih podatkovnih struk-
tur. Druge, ki jih prav tako pogosto uporabljamo v računalništvu, so še: drevo,
vrsta, kopica, graf, gozd in še mnoge druge . V naslednjih številkah PRESEKA
si bomo ogledali še nekatere. Do takrat pa nekaj nalog, ki so objavljene na
strani 333.
309