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

Imenovanje

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.

Razlike i podtipovi

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.

Operacije

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:

operacija	uobičajena imena	Ada	C++	Java	Perl	PHP	Python	Ruby	JavaScript
ubaciti element na kraj	inject, snoc	Append	push_back	offerLast	push	array_push	append	push	push
ubaciti element na početak	push, cons	Prepend	push_front	offerFirst	unshift	array_unshift	appendleft	unshift	unshift
izbrisati poslednji element	eject	Delete_Last	pop_back	pollLast	pop	array_pop	pop	pop	pop
izbrisati prvi element	pop	Delete_First	pop_front	pollFirst	shift	array_shift	popleft	shift	shift
pogledati poslednji element		Last_Element	back	peekLast	$array[-1]	end	<obj>[-1]	last	<obj>[<obj>.length - 1]
pogledati prvi element		First_Element	front	peekFirst	$array[0]	reset	<obj>[0]	first	<obj>[0]

Implementacije

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.

Podrška od strane programskih jezika

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

Složenost

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

Primene

Primer gde deque može biti upotrebljen je A-Steal algoritam za raspoređivanje poslova. 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.

Vidi još

• Red
• Red sa prioritetom

Literatura

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

Spoljašnje veze

• 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