Red (struktura podataka)
 | Ovaj članak je siroče zato što nema ili vrlo malo ima drugih članaka koji linkuju ovamo. |
 | Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
Red (engleski: Queue) apstraktni je tip podataka koji služi za pohranu niza istovrsnih elemenata. Kod reda se podaci čitaju i brišu sa čela reda , dok se novi podaci zapisuju na začelje reda. Ovo čini red podatkovnom strukturom sa pristupom "prvi koji ulazi - prvi izlazi" (engl. FIFO - first in, first out). Kada se doda novi elemenat u red da bi se on uklonio moraju biti uklonjeni svi elementi koji su dodani prije njega. Dakle, podaci se kod reda, suprotno od steka, čitaju istim redoslijedom kojim su upisani.
Primjena reda[uredi | uredi izvor]
Red je primjer linearne strukture podataka i dosta se koristi u računarstvu, transportu i operacionim istraživanjima gdje 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.
Operacije za rad s redom[uredi | uredi izvor]
Osnovne operacije[uredi | uredi izvor]
- IsEmpty - Pokazuje da li je red prazan.
- Front - Vraća vrijednost sa čela reda.
- EnQueue - Stavlja vrijednost na začelje reda.
- DeQueue - Briše element s čela reda.
Napredne operacije[uredi | uredi izvor]
Napredne operacije vezane su uz modifikacija reda. Tako npr. red s dva kraja bez ograničenog ulaza (opisan kasnije) razlikuje EnQueue_front (dodavanje na početak) i EnQueue_back. Implementirajući takve mogućnosti apstraktni tip podataka gubi svojstva jednostavnog reda.
Implementacije reda[uredi | uredi izvor]
Pomoću povezane liste[uredi | uredi izvor]
Najfleksibilnija implementacija reda je ona sa povezanom listom. Uz samu listu, za realizaciju je potrebna struktura koja će sadržavati pokazivače na početak i kraj reda, i tako omogućiti jednostavnu izvedbu operacija za rad s redom. EnQueue se izvodi tako da se pokazivač zadnjeg elementa usmjeri na novostvoreni elemenat, te se nakon toga pokazivač na kraj liste usmjerava na taj isti elemenat. DeQueue se izvodi tako da se pokazivač na početak liste preusmjeri na sljedeći elemenat, a stari se elemenat obriše. Lista je prazna ukoliko oba pokazivača pokazuju na isti elemenat.
Pomoću niza[uredi | uredi izvor]
Kada govorimo o implementaciji pomoću niza, najčešće se izvodi implementacija kružnog reda, koja je spomenuta kasnije u tekstu.
Modifikacije reda[uredi | uredi izvor]
Red sa dva kraja[uredi | uredi izvor]
Red sa dva kraja (engl. double-ended queue tj. deque) posebna je vrsta reda kojem se elementi mogu dodavati/čitati i sa čela i sa začelja. Postoje tri vrste ovakvog reda:
- Deque sa čitanjem i pisanjem na oba kraja - obje operacije su podržane i na čelu i na začelju
- Deque s ograničenim ulazom - na jednoj strani moguće su obje operacije, a na drugoj samo uklanjanje.
- Deque s ograničenim izlazom - na jednoj strani moguće obje operacije, a na drugoj samo umetanje.
Kružni red[uredi | uredi izvor]
Kružni red (kružni međuspremnik) koristi listu elemenata fiksne veličine, čiji su krajevi povezani. Koristi se kao međuspremnik. Može se implementirati pomoću niza, a potrebna su još i tri pokazivača; jedan koji pokazuje na samu memorijsku lokaciju međuspremnika, jedan koji pokazuje na početak elemenata koji sadrže podatke, i treći koji pokazuje kraj elemenata.
Kružni red je pun ako pokazivač početka podataka, kao i pokazivač kraja pokazuju na isti element. Pošto je situacija identična kada je red prazan, potrebno je uvesti još jedan indikator.
Red s prioritetima[uredi | uredi izvor]
Red s prioritetima je takav red koji podržava slijedeće tri funkcije: InsertWithPriority koji dodaje element s određenim prioritetom, GetNext koji vraća element s najvećim prioritetom i miče ga iz reda i (opcijski) PeekAtNext koji vraća element s najvećim prioritetom i ostavlja ga u redu.
Reference[uredi | uredi izvor]
- Donald Knuth (1997). „Stacks, Queues, and Deques”. The Art of Computer Programming. Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley. pp. 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 ed.). MIT Press and McGraw-Hill. pp. 200–204. ISBN 978-0-262-03293-3.
- William Topp (2002). „Queues and Priority Queues”. Data Structures with C++ and STL. Second Edition. Prentice Hall. pp. 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. pp. 137–169. ISBN 978-0-534-49182-6.
Vanjski linkovi[uredi | uredi izvor]
 |
Commons ima datoteke na temu: Red (struktura podataka) |