Stek (apstraktni tip podataka)
U računarstvu, stek je privremeni apstraktni tip podataka i struktura podataka, baziran na principu LIFO (LIFO - Last In First Out - poslednji koji ulazi, prvi izlazi). Stekovi se u velikoj meri koriste na svim nivoima modernog računarskog sistema.
Stek-mašina je računarski sistem koji privremene podatke skladišti prvenstveno u stekovima, umesto u hardverskim registrima.
Apstraktni tip podataka[uredi | uredi izvor]
Kao apstraktni tip podataka, stek se sastoji od čvorova, i ima dve osnovne operacije: push i pop. Push stavlja dati čvor na vrh steka, ostavljajući prethodne čvorove ispod. Pop uklanja i vraća čvor koji je trenutno na vrhu. Stek se može shvatiti kao nekoliko tanjira postavljenih jedan na drugi. Ako želimo da dodamo novi tanjir, stavljamo ga na vrh, a ukoliko nam je potreban tanjir, uzimamo onaj sa vrha. Da bismo skinuli tanjir sa dna, prethodno moramo da skinemo sve tanjire koji se nalaze na njemu. Samo nam je tanjir sa vrha dostupan, dok su ostali prekriveni. Kad se na vrh doda novi tanjir, on postaje vrh steka. Ova metafora ilustruje dva važna principa: jedan je princip LIFO (engl. Last in, first out - poslednji koji ulazi, prvi izlazi), a drugi je da je samo tanjir sa vrha vidljiv, pa da bi se video treći tanjir, prvi i drugi moraju prvo da se sklone.
Operacije[uredi | uredi izvor]
Kod modernih računarskih jezika, stek se obično implementira sa dodatnim operacijama, a ne samo sa "push" i "pop". Često je moguće da se dužina steka vrati kao parametar. Još jedna pomoćna operacija je top[1] (takođe poznata kao peek i peak) može da vrati trenutni element sa vrha, bez uklanjanja sa steka.
Sledi pseudokod za dodavanje i uklanjanje čvorova sa steka, kao i za funkcije koje određuju dužinu, i top funkciju. U ovim funkcijama se koristi null, da referiše na dno steka.
struktura Cvor {
podaci; // Подаци који се чувају у чвору''
sledeci; // показивач на следећи чвор; null за последњи чвор
};
struktura Stek {
Cvor pokazivacNaVrh; // показује на врх стека; null за празан стек
};
funkcija push(Stek stek, Element element)
{
// гура елемент на стек
noviCvor = novi Cvor; // алоцира меморију за нови чвор
noviCvor.podaci = element;
noviCvor.sledeci = stek.pokazivacNaVrh;
stek.pokazivacNaVrh = noviCvor;
}
funkcija pop(Stek stek)
{
// повећава показивач на стек, и враћа чвор са врха''
// Овде такође може да се провери да ли је stack.stackPointer null''
// Ако је тако, може се вратити грешка''
cvor = stek.pokazivacNaVrh;
stek.pokazivacNaVrh = stek.sledeci;
element = cvor.podaci;
vrati element;
}
funkcija vrh(Stek stek)
{
// враћа чвор са врха
vrati stek.pokazivacNaVrh.podaci;
}
funkcija duzina(Stek stek)
{
// враћа број чворова из стека
duzina = 0;
cvor = stek.pokazivacNaVrh;
dok cvor nije null {
duzina = duzina+1;
cvor = cvor.next;
}
vrati duzina;
}
Kao što se može videti, ove funkcije prosleđuju stek i čvorove kao parametre i povratne vrednosti. Čvorovi u ovoj implementaciji koriste pokazivače. Stek može biti implementiran i kao linearna sekcija memorije (na primer u nizu), u kom slučaju se zaglavlja funkcija ne menjaju, već samo njihova unutrašnjost.
Implementacija[uredi | uredi izvor]
Tipična memorijska zahtevnost steka od n elemenata je O(n). Tipična vermenska zahtevnost operacija je O(1). Stek se lako koristi pomoću dinamičkog niza, ili povezane liste.
Standardna šablonska biblioteka C++ programskog jezika sadrži šablonsku klasu stack, koja je ograničena samo na push/pop operacije. Javina biblioteka sadrži Stack[2] klasu koja je specijalizacija klase Vector[3] što neki smatraju velikom greškom u dizajnu, jer nasledna get() metoda iz klase Vector ignoriše LIFO ograničenja klase Stack.
Sledi jednostavan primer steka sa opisanim operacijama u programskom jeziku Piton. Stek nema nikakav tip provere grešaka.
class Stack:
def __init__(self):
self.stack_pointer = None
def push(self, element):
self.stack_pointer = Node(element, self.stack_pointer)
def pop(self):
(e, self.stack_pointer) = (self.stack_pointer.element, self.stack_pointer.next)
return e
def peek(self):
return self.stack_pointer.element
def __len__(self):
i = 0
sp = self.stack_pointer
while sp:
i += 1
sp = sp.next
return i
class Node:
def __init__(self, element=None, next=None):
self.element = element
self.next = next
if __name__ == '__main__':
# small use example
s = Stack()
[s.push(i) for i in xrange(10)]
print [s.pop() for i in xrange(len(s))]
Ovo inače nije potrebno, jer Piton podržava pop i append funkcije za liste. Međutim, jednostavna sintaksa ovog jezika ga čini pogodnim za primer.
Povezane strukture podataka[uredi | uredi izvor]
Apstraktni tip podataka i struktura podataka tipa FIFO (FIFO - First In First Out - prvi koji ulazi, prvi izlazi) je red. Na primer, promena steka u red u algoritmu za pretragu može da promeni algoritam iz pretrage u dubinu u pretragu u širinu.
Hardverski stekovi[uredi | uredi izvor]
Najčešća upotreba stekova na nivou arhitekture je kao sredstvo za alociranje i pristupanje memoriji.
Osnovna arhitektura steka[uredi | uredi izvor]
Tipičan stek skladišti lokalne podatke i informacije o pozivu za ugnežđene procedure. Ovaj stek raste nadole od početka. Pokazivač na stek pokazuje na trenutni vrh steka. Operacija Push umanjuje pokazivač, i kopira podatke na stek; operacija pop vraća podatke sa steka, a zatim pokazivač pokazuje na novi vrh steka. Svaka procedura pozvana unutar programa skladišti svoje povratne informacije (žuto) i lokalne podatke (u drugim bojama) gurajući ih na stek. Ovakva implementacija steka je izrazito česta, ali je ranjiva na napade prekoračenja bafera. Tipičan stek je deo u memoriji računara sa fiksiranim početkom, i promenljivom veličinom. Na početku, veličina steka je nula. Pokazivač na stek, obično u vidu hardverskog registra, pokazuje na poslednju iskorišćenu adresu na steku; kada je stek veličine nula, pokazivač pokazuje na početak steka.
Dve operacije primenljive na sve stekove su:
- push operacija, u kojoj se predmet postavlja na lokaciju na koju pokazuje pokazivač na stek, a adresa u pokazivaču se prilagođava za veličinu tog predmeta;
- pop ili pull operacija: predmet na trenutnoj lokaciji na koju pokazuje pokazivač se uklanja, a adresa u pokazivaču se prilagođava za veličinu tog predmeta
Postoji mnogo varijacija osnovnog principa stek operacija. Svaki stek ima fiksiranu lokaciju u memoriji, na kojoj počinje. Kako se podaci dodaju na stek, stek pokazivač se pomera, kako bi oslikavao trenutno stanje steka, koje se širi od njegovog početka (može da se širi ka gore ili ka dole, zavisno od implementacije).
Na primer, stek može da počne na memorijskoj lokaciji 1000, i da se širi ka nižim adresama, i u tom slučaju se novi podaci smeštaju na adresama ispod 1000, i pokazivač na stek se umanjuje svaki put kad se novi podatak doda. Kad se podatak ukloni sa steka, pokazivač na stek se uvećava.
Pokazivač na stek može da pokazuje na početak steka, ili na ograničeni opseg iznad ili ispod početka (u zavisnosti od toga u kom smeru ste kraste); međutim, on ne može da pređe početak steka. Drugim rečima, ako je početak steka na adresi 1000, i stek raste nadole (prema adresama 999, 998, i tako dalje), pokazivač na stek ne sme nikad da bude uvećan iznad 1000 (na 1001, 1002, i tako dalje). Ako pop operacija dovede do toga da pokazivač na stek pređe preko početka steka, dolazi do potkoračenja steka (stack underflow). Ako push operacija dovede do toga da se pokazivač na stek uveća ili umanji preko maksimalne veličine steka, dolazi do prekoračenja steka (stack overflow).
Neka okruženja se u velikoj meri oslanjaju na stekove mogu da pružaju i dodate operacije, na primer:
- -{Dup(licate)]-: vrh steka se duplira, tako što se novi primerak tog podatka postavi na stek, tako da original ostane ispod njega.
- Peek: vrh steka se vraća, ali se pokazivač na stek ne menja, kao ni veličina steka (što znači da podatak ostaje na steku). Ova operacije se takođe često naziva top.
- Swap ili exchange: dva elementa najbliža vrhu steka menjaju mesto.
- Rotate: n elemenata steka najbližih vrhu se premeštaju na steku, tako što se rotiraju. Na primer, ako je n=3, podaci 1, 2, i 3 na steku se premeštaju na pozicije 2, 3, i 1 redom. Moguće su mnoge varijacije ove operacije, a najčešće su rotiranje ulevo (left rotate) i rotiranje udesno (right rotate).
Stekovi se obično zamišljaju tako što rastu od dna ka vrhu (kao u realnim primerima (na primer diskovi na štapu)), ili sa vrhom steka na fiksiranoj poziciji (vidi sliku), nalik na okvir kod pištolja ([1] Arhivirano na sajtu Wayback Machine (27. septembar 2007)), ili tako što rastu sleva nadesno, pa najviši postaje najdesniji. Ove vizuelizacije mogu biti nezavisne od stvarne implementacija steka u memoriji. Ovo znači da će right rotate pomeriti prvi element na treću poziciju, drugi element na prvu, a treći na drugu poziciju. Slede dve ekvivalentne vizuelizacije ovog procesa:
јабука краставац банана ==right rotate==> јабука краставац банана
јабука банана краставац ==right rotate==> краставац јабука банана
Stek je u računarima obično predstavljen blokom memorijskih ćelija, sa dnom na fiksiranoj lokaciji, a pokazivač na stek čuva adresu trenutnog vrha steka. Izrazi vrh i dno se koriste nevezano za stvarnu implementaciju steka (kod koje stek može da raste i nadole, i nagore).
Guranje elementa na stek menja vrednost pokazivača na stek za veličinu elementa (bilo umanjujući, ili povećavajući ga, u zavisnosti od smera u kome stek raste u memoriji), tako da pokazuje na sledeću ćeliju, i kopira novi element na stek. Opet, u zavisnosti od specifične implementacije, na kraju push operacije, pokazivač može da pokazuje na prvu slobodnu lokaciju na steku, ili na sam vrh steka. Ako pokazivač pokazuje na trenutni vrh, on će biti pomeren pre nego što se novi element doda na stek; ako pokazuje na prvu slobodnu lokaciju, biće pomeren nakon što se novi element gurne na stek.
Hardverska podrška[uredi | uredi izvor]
Mnogi procesori imaju registre koji mogu da se koriste kao pokazivači na stek. Neki, poput Intelovog x86, imaju posebne instrukcije koje implicitno koriste registar posvećen tome da bude pokazivač na stek. Drugi, kao što je DEC PDP-11 i Motorolina familija 68000 imaju adresne modove koji omogućavaju korišćenje bilo kog skupa registara kao pokazivače na stek. Intel 80x87 serija numeričkih koprocesora ima skup registara kojima se može pristupiti bilo kao pokazivačima na stek, bilo kao numerisanim registrima. NEki mikrokontroleri, na primer PIC, imaju stek fiksirane dubine, kome se ne može direktno pristupiti.
Neki mikroprocesori takođe implementiraju stek direktno u hardveru:
- Computer Cowboys MuP21
- Harris RTX line
- Novix NC4016
Mnogi mikroprocesori bazirani na steku su korišćeni da implementiraju programski jezik Forth na nivou mikrokoda. Stekovi su takođe korišćeni kao osnova nekih mejnfremova i miniračunara. Takve mašine su nazivane stek mašinama, a najpoznatiji je Burroughs B5000.
Softverska podrška[uredi | uredi izvor]
U aplikacionim programima pisanim u višim programskim jezicima, stek se može efikasno primeniti bilo pomoću nizova bilo pomoću povezanih listas. U jeziku Lisp nema potrebe da se implementira stek, jer su funkcije push i pop dostupne za svaku listu. Adobe PostScript je takođe dizajniran oko steka koga programer direktno može da vidi, i da njime manipuliše.
Primene[uredi | uredi izvor]
Stekovi se stalno koriste u svetu računarstva.
Izračunavanje izraza i parsiranje sintakse[uredi | uredi izvor]
Kalkulatori koji koriste obrnutu poljsku notaciju koriste stek strukture da čuvaju vrednosti. Izrazi mogu biti zapisivani u prefiksnoj, postfiksnoj ili infiksnoj notaciji. Za konverziju iz jedne u drugu formu izraza je potreban stek. Mnogi kompajleri koriste stek za parsiranje sintakse izraza, programske blokove, i slično pre prevođenja u kod niskog nivoa. Većina programskih jezika su kontekst-slobodni jezici što im omogućava da budu parsirani mašinama baziranim na steku. Prirodni jezici su kontekst osetljivi jezici, i sami stekovi nisu dovoljni da interpretiraju njihovo značenje.
Na primer, izraz: ((1 + 2) * 4) + 3 može biti zapisan na sledeći način u postfiksnoj notaciji uz prednost da nisu potrebna pravila prednosti i zagrade:
- 1 2 + 4 * 3 +
Izraz se izračunava sleva nadesno korišćenjem steka:
- push kad se dođe do operanda
- pop dva operanda i njihovo računanje, kad se dođe do operacije praćeno push rezultat.
Sledi ilustracija opisanog algoritma za dati primer:
| Ulaz | Operacija | Stek |
|---|---|---|
| 1 | Push operand | 1 |
| 2 | Push operand | 1, 2 |
| + | Sabiranje i Pop poslednja dva operanda i Push rezultat | 3 |
| 4 | Push operand | 3, 4 |
| * | Množenje i Pop poslednja dva operanda i Push rezultat | 12 |
| 3 | Push operand | 12, 3 |
| + | Sabiranje i Pop poslednja dva operanda i Push rezultat | 15 |
Konačni rezultat, 15, stoji na vrhu steka nakon računanja.
Izvori[uredi | uredi izvor]
- ^ Horowitz, Ellis: "Fundamentals of Data Structures in Pascal", page 67. Computer Science Press, 1984
- ^ Sun.com „Stek“ (jezik: engleski)
- ^ „Stek“ (jezik: engleski)
Spoljašnje veze[uredi | uredi izvor]
| Normativna kontrola: Državne |
|---|
