Red sa dva kraja

U informatici, red sa dva kraja (engl. Double-ended-queue, uglavnom se piše deque, izgovara se dek) je apstraktan tip podataka koji je uopštenje reda, u koji se elementi mogu dodavati ili uklanjati sa početka(glave) ili kraja(repa).^[1]

Deque se ponekad piše i kao dequeue, ali se taj termin uglavnom ne koristi pošto je dequeue takođe glagol koji znači "ukloniti iz reda". Uprkos tome, nekoliko biblioteka i neki autori, kao Aho, Hopkroft, i Ulman u svom udžbeniku Strukture podataka i algoritmi(Data structures and algorithms), koriste termin dequeue. Džon Mičel, autor dela Koncepti u programskim jezicima(Concepts in Programming Languages), takođe koristi ovaj termin.

Razlikuje se od reda koji radi na principu FIFO, u koji se elementi samo mogu dodati na jedan kraj a vaditi sa drugog kraja. Deque može da ima neke od sledećih podtipova:

• Deque sa ograničenjem na ulaz: brisanje elemenata se može vršiti na oba kraja dok se ubacivanje može vršiti samo na jednom kraju.
• Deque sa ograničenjem na izlaz: ubacivanje elemenata se može vršiti na oba kraja dok se brisanje može vršiti samo na jredom kraju.

Osnovni kao i najuobičajeniji tipovi lista u računarstvu, redovi i stekovi se mogu smatrati posebnim oblikom redova sa dva kraja, i mogu se implementirati korišćenjem istih.

Osnovne operacije koje se mogu vršiti su ubacivanje i vađenje sa bilo kog kraja. Uglavnom se i implementira operacija koja će da vrati vrednost sa bilo kog od krajeva deque-a bez njegovog brisanja.

Imena se razlikuju među jezicima; neki od značajnijih jezika:

Postoje najmanje dva uobičajena načina za efikasno implementiranje deque-a: korišćenjem modifikovanog dinamičkog niza ili dvostruko povezane liste.

Pristup korišćenjem dinamičkog niza koristi varijantu dinamičkog niza koji može da se proširuje sa oba kraja. Takvi nizovi imaju sva svojstva dinamičkih nizova, kao što su konstantno vreme nasumičnom pristupu podacima, dobra lokalnost referenci, neefikasno ubacivanje/izbacivanje elemenata u sredini, kao i amortizovano konstantno vreme za ubacivanje/brisanje na oba kraja, umesto samo na jednom kraju. Tri uobičajene implementacije:

• Skladištenje deque-a u kružnom baferu koji se proširuje tek kada se napuni do kraja. Ovime se postiže manja učestalost proširivanja.
• Alociranje sadržaja deque-a počevši od centra niza koji se koristi za realizaciju i proširivanje istog tek kad se dostigne bilo koji od krajeva. Ovakav pristup može zahtevati učestalija proširivanja i trošiti više prostora, posebno kada se elementi dodaju samo sa jednog kraja.
• Skladištenje sadržaja u više manjih nizova, pritom alocirajući dodatne nizove s početka ili kraja po potrebi. Indeksiranje se implementira tako što se koristi dinaminčki niz koji čuva pokazivače na svaki od manjih nizova.

Ada-ini kontejneri obezbeđuju generičke pakete: Ada.Containers.Vectors koji sadrži implementaciju dinamičkih nizova, odnosno Ada.Containers.Doubly_Linked_Lists koji sadrži implementaciju dvostruko povezanih listi.

C++-ova biblioteka standardnih šablona ovezbeđuje šablone klasa std::deque i std::list koje sadrže implementacije deque-a, odnosno lista.

Od verzije 6, Java-in Collections Framework obezbeđuje novi Deque interfejs koji obezbeđuje funkcionalnost umetanja i brisanja sa oba kraja. Klase kao sto su ArrayDeque (koja je takođe novina u Java 6) i LinkedList implementiraju ovaj intefejs i obezbeđuju implementacije dinamičkog niza, odnosno povezanih listi. Međutim, the ArrayDeque, nasuprot svom imenu, ne podržava nasumičan pristup elementima.

Python 2.4 je uveo collections modul sa podrškom za deque objekte. Od verzije 5.3, proširenje PHP-ove SPL sadrži 'SplDoublyLinkedList' klasu koja se može koristiti za implementaciju deque-a. Prethodno su se morale koristiti nizovne funkcije array_shift/unshift/pop/push da bi se napravio deque.

GHC-ov Data.Sequence modul implementira efikasan, funkcionalan red sa dva karaja u Haskelu. Implementacija koristi 2-3 stablo sa pribeleženim veličinama. Postoje i druge mogućnosti za implementaciju čisto funkcionalnih redova sa dva kraja (većinom koristeći lenjo izračunavanje).^[2][3]

• U implementaciji koja koristi dvostruko povezanu listu izuzimajući vreme potrebno za alokaciju/dealokaciju vremenska složenost svih operacija je O(1). Uzgred, vremenska složenost ubacivanja i brisanja elemenata u sredini je takođe O(1) ako se koristi iterator. Doduše, vremenska složenost za pristup elementu koristeći indeks je O(n).
• Koristeći proširiv niz, amortizovana vremenska složenost svih operacija je O(1). Takođe je i vremenska složenost nasumičnog pristupa elementu O(1), dok je vremenska složenost umetanja i brisanja elemenata iz sredine O(n).

Primer gde deque može biti upotrebljen je A-Steal algoritam za raspoređivanje poslova.^[4] Ovaj algoritam implementira raspoređivanje poslova za nekoliko procesora. Čuva se zaseban deque za svaki od procesora koji sadrži niti koje svaki procesor treba da izvrši. Da bi izvršio sledeću nit, procesor uzima element iz deque-a (koristeći operaciju "izbriši prvi element"). Ako trenutna nit napravi kopiju sebe(fork-uje), stavlja se na početak deque-a (koristeći operaciju "ubaciti na početak reda") i pokreće se nova nit. Kada jedan od procesora završi izvršenje svojih niti (tj. red je prazan), može da "ukrade" nit drugog procesora tako što uzima poslednji element iz deque-a drugog procesora (koristeći operaciju "izbriši poslednji element") i izvršava tu nit. Ovaj algoritam koristi Intel-ova Threading Building Blocks (TBB) biblioteka za paralelno programiranje.

• Red
• Red sa prioritetom

• Eitan Frachtenberg, Uwe Schwiegelshohn (2007). Job Scheduling Strategies for Parallel Processing: 12th International Workshop, JSSPP 2006. Springer. ISBN 978-3-540-71034-9.  See pp. 22.

• 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