Stek

Stek je poznat i često korišćen mehanizam u programiranju. Najveći broj programskih jezika koristi koncept steka za: prosleđivanje parametara, smeštanje lokalnih promenljivih, realizaciju mehanizma grananja, realizaciju mehanizma prekida (interapta). Osnovne opercije sa stekom su: push (stavljanje podataka na stek) i pop (skidanje podataka sa steka). Koriste se i metodi provere kao što su top i isEmpty. Primer korišćenja steka su hanojske kule.


slika 1. Push i pop operacije

 

Stek je jednostavno još jedan skup objekata, pa bi stoga bilo moguće koristiti istu specifikaciju kao i za opšti skup. Međutim, skupovi sa LIFO semantikom steka su toliko važni u računarskoj nauci, da ograničena specifikacija steka tu nalazi svoju punu potvrdu.

slika 2. Stek i vrh steka

 

Iako je moguće realizovati stek pomoću povezane liste (dodavanje i brisanje sa glave povezane liste daje upravo LIFO semantiku steka), najčešće primene steka imaju memorijsko ograničenje, tako da je realizacija pomoću niza prirodnija i efikasnija. Kod većine operativnih sistema, alokacija i dealokacija memorije je relativno skupa neefikasna operacija, tako da postoji nedostatak u brzini na račun fleksibilnosti realizacije pomoću povezane liste.

 

N - arno stablo

Do sada smo spominjali linearne strukture podataka. Međutim, postoje jedanako važne, ako ne i važnije strukture, takozvane nelinearne strukture podataka. Taj tip ili struktura podatka se bazira na odabiru jednog člana koji će predstavljati koren stabla. Na koren stabla niko ne pokazuje, a u zavisnosti od n-arnosti stabla koren pokazuje na n sledećih članova koje zovemo čvorovima ili decom. U sledećem koraku svako dete ima svojih n dece i tako dalje. U jednom momentu se dešava da deca više nemaju na koga da pokazuju. Takvu decu zovemo listovima datog drveta. Najjednostavniji primer takvog stabla je binarno stablo, odnosno stablo kod kojeg svaki čvor, uključujući i koren, ima najviše dva naslednika. Dakle, to je struktura koja se sastoji od tri dela. Deo koji sadrži informaciju i dva dela sa pointerima.


slika 3. Primer binarnog stabla. T pokazuje na koren

 

Knjiga je lep primer za ilustraciju prikaza stabla. Svaka knjiga se sastoji od korena, što bi, recimo, mogao biti njen sadržaj. Zatim, postoje glavne grane, kao što su uvod, zatim nazivi poglavlja i literatura. Unutar svakog poglavlja, dalje, postoje podpoglavlja, pa podpodpoglavlja i tako dalje. Uočava se postojanje jedne hijerarhije, kao i jedinstvenost putanje do pojedinih čvorova, u smislu da mogu postojati čvorovi istog imena, ali moraju imati različite putanje. Recimo, mogu postojati dva podpoglavlja istog imena, ali se moraju nalaziti u različitim poglavljima.

Stabla sa sobom nose i probleme u vidu uređenosti stabla. Naime, dodavanjem novih čvorova u stablo možemo narušiti balans stabla, na taj način da jedna grana ima više čvorova od druge. Postoje tehnike koje obezbeđuju automatsko balansiranje stabla, ali su uglavnom vremenski zahtevne. Stablo može biti potpuno, odnosno takvo da su svi listovi na istom nivou. Stablo takođe može biti i kompletno, odnosno da svi unutrašnji čvorovi imaju po n dece.

Najčešća implementacija binarnih stabala, u praksi, jeste metodom dinamičke alokacije, uz upotrebu pokazivača. Pri ovome važi da je kod binarnih stabala potrebno obezbediti dva pokazivača, a kod nebinarnih n pokazivača. Na sledećoj slici vidimo predstavljanje binarnog stabla.

slika 2. Binarno stablo smešteno u listu

 

B- stabla

Zajedničko svim n-arnim stablima je da čvorovi mogu da imaju samo jedan podatak. Međutim, postoje i strukture koje mogu imati više podataka u čvoru i u zavisnosti od broja podataka u čvoru mogu imati promenljiv broj naslednika. Takav tip podataka je posebno koristan kod realizacije baza podataka. B-stabla se lakše pretražuju od n-arnih i nose slične probleme koji se tiču balansiranja, ali ih efikasnije rešavaju.

 

Slika 3. Primer b-stabla. Koren ima dva elemena i tri lista

 

Pravila koja važe za takva stabla su:

  • Svaki čvor ima manje od m dece i svaki čvor ima više od m/2 dece
  • Čvor ima najmanje dva deteta, osim ako nije list
  • Svaki list je na istom nivou i nosi podatak
  • Čvor sa k dece, a koji nije list ima k-1 pokazivač
Dodaj komentar Sviđa mi se - (1) Ne sviđa mi se - (0)    

  • Složeni tipovi podataka 2 1
  • Složeni tipovi podataka 2 2
  • Složeni tipovi podataka 2 3
  • Složeni tipovi podataka 2 4
  • Složeni tipovi podataka 2 5