Red (tip podataka)

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.

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 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.

• Stek
• Red sa dva kraja
• Liste
• Red sa prioritetom

• Donald Knuth (1997). „Stacks, Queues, and Deques”. The Art of Computer Programming. Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley. стр. 238-243. ISBN 978-0-201-89683-1. 
• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). „Stacks and queues”. Introduction to Algorithms (2nd изд.). MIT Press and McGraw-Hill. стр. 200-204. ISBN 978-0-262-03293-3. 
• William Ford; William Topp (2002). „Queues and Priority Queues”. Data Structures with C++ and STL. Second Edition. Prentice Hall. стр. 386-390. ISBN 978-0-13-085850-4. 
• Adam Drozdek (2005). „Stacks and Queues”. Data Structures and Algorithms in C++. Third Edition. Thomson Course Technology. стр. 137—169. ISBN 978-0-534-49182-6. 

• SGI STL Documentation: deque<T, Alloc>
• Code Project: An In-Depth Study of the STL Deque Container
• Diagram of a typical STL deque implementation
• Deque implementation in C Архивирано на сајту Wayback Machine (6. март 2014)
• VBScript implementation of stack, queue, deque, and Red-Black Tree
• Multiple implementations of non-catenable deques in Haskell