SHPORA.net :: PDA

[ Back ]

Magasin (stack)



LIFO - last in first out

Magasini omadused:

1. dünaamiline struktuur (elementide arv on muutuv)

2. elemendid on sama tüüpi

3. elementide järjestus on oluline

4. juurdepääs on ainult viimasena lisatud elemendile (magasini tipp); "lisamine" lisab lõppu ja "võtmine" eemaldab lõpust

5. tavaliselt realiseeritavad operatsioonid: tühja magasini loomine, lisamine (push), võtmine (pop), alatäitumise (underflow) kontroll (et vältida tühjast magasinist võtmist), mõne realisatsiooni korral ka ületäitumise (overflow) kontroll (kas on "ruumi" lisamiseks), tipu lugemine ilma eemaldamiseta (optim. kaalutlustel)



Keeles Java võib magasini realisatsiooni leida klassides java.util.Stack (baseerub vektoril) või java.util.LinkedList spetsialiseerides (baseerub topeltseotud ahelal).



Magasini kasutamise näited: avaldise väärtustamine, 'return stack', puu läbimine, ...

Avaldise postfikskuju ja selle interpreteerimine



"Tavaline" infikskuju: (5-1) * 7 + 6 / 3



Prefikskuju sulgudega: +( *( -( 5, 1), 7), /(6, 3))



Postfikskuju sulgudega: (((5, 1)-, 7)*, (6, 3)/ )+



Sulgudeta postfikskuju - nn. "pööratud poola kuju": 5 1 - 7 * 6 3 / + .



3



1 7 6 6 2



5 5 4 4 28 28 28 28 30



--------------------------



5 1 - 7 * 6 3 / +