Пређи на садржај

Red (tip podataka)

С Википедије, слободне енциклопедије
(преусмерено са Ред (структура података))
Prikaz reda kao FIFO strukture

U računarstvu, red (енгл. queue) je posebna vrsta apstraktnog tipa podataka kod kojeg su glavne (ili jedine) operacije dodavanje elemenata na kraj reda, kao i uklanjanje elemenata sa početka reda. Red predstavlja FIFO strukturu(engl. First-In-First-Out], što podrazumeva da prvi element koji se dodaje u red će biti i prvi element koji će biti uklonjen iz reda. Ovo je ekvivalentno sa zahtevom da kada se doda novi element u red, da bi se on uklonio moraju biti uklonjeni svi elementi koji su dodati pre njega.

Red je primer linearne strukture podataka i dosta se koristi u računarstvu, transportu i operacionim istraživanjima gde se različiti entiteti kao što su podaci, predmeti, lica ili događaji čuvaju, kako bi kasnije bili obrađeni. U ovom kontekstu, red obavlja funkciju bafera.

Redovi su uobičajeni u programiranju, gde su implementirani kao strukture podataka zajedno sa pristupnim rutinama, kao jedna klasa u objektno-orijentisanom programiranju. Zajedničke implementacije su cirkularni baferi i povezane liste.

Implementacija reda

[уреди | уреди извор]

Teoretski, jedna karakteristika reda je da nema specifičan kapacitet. Bez obzira na to koliko elemenata red već sadrži, uvek se može dodati novi element. Red takođe može biti prazan i u tom slučaju uklanjanje elementa je nemoguće sve dok se opet ne doda novi element. Nizovi fiksirane dužine imaju ograničen kapacitet, ali nije istina da članovi niza moraju biti kopirani na početak reda. Jednostavan trik pretvaranja niza u zatvoren krug i pustiti glavu i rep reda da se beskonačno vrte u tom krugu čini nepotrebnim pomeranje članova niza. Ako je n dužina niza, onda indeksi po modulu n će okrenuti niz u krug. Ovo je još uvek konceptualno najjednostavniji način da se izgradi red na jeziku visokog nivoa, ali je i dalje spor jer indeksi niza moraju biti poređani od nule do n, gde je n veličina niza, i to zahteva vreme za proveru da li je neki element izvan granice niza. Veličina niza mora biti deklarisana pre vremena, ali neke implementacije udvostruče deklarisanu veličinu niza kada dođe do prekoračenja. Većina modernih jezika sa objektima ili pokazivačima sadrže biblioteke sa dinamičkim listama. Takve strukture podataka mogu da nemaju ograničen kapacitet pored memorijskih ograničenja. Prekoračenje reda se dešava kada pokušamo da dodamo element na popunjen red, a potkoračenje reda kada pokušamo da uklonimo element iz praznog reda.

Postoji nekoliko efikasnih implementacija FIFO redova. Efikasna implementacija podrazumeva da je vreme potrebno za dodavanje elementa ili uklanjanje elementa O(1).

  • Povezana lista
    • Dvostruko povezana lista ima vremensku složenost umetanja i brisanja elementa na oba kraja O(1), tako da je prirodan izbor za red.
    • Jednostruko povezana lista ima efikasno ubacivanje i brisanje elementa na jednom kraju. Međutim, mala modifikacija uvođenjem pokazivača će omogućiti efikasnu implementaciju reda.
  • Red sa dva kraja se implementira uz pomoć modifikovanog dinamičkog niza.

Redovi i programski jezici

[уреди | уреди извор]

Redovi mogu biti implementirani kao poseban tip podataka, ili se mogu posmatrati kao redovi sa dva kraja, ako nisu implementirani odvojeno. Standardna biblioteka jezika C++ definiše "red" kao klasu koja je ograničena samo na operacije dodavanja ili uklanjanja. Od J2SE5.0, Java sadrži Red interfejs, koji precizira operacije reda. PHP ima SplQueue klasu i nezavisne biblioteke.

Spoljašnje veze

[уреди | уреди извор]