dequeue)Obojsmerný rad1 (double-ended queue, čiže deque) je kombináciou zásobníka a radu. Môžeme doň vkladať aj odoberať z oboch strán, a tiež sa pozerať na začiatok aj koniec. Ako abstraktná dátová štruktúra podporuje nasledovné operácie:
Implementácia pomocou obojsmerne spájaného zoznamu je podobná ako pri zásobníku -- až na to, že si pamätáme dva smerníky, jeden na začiatok a druhý na koniec. Keďže používame obojsmerne spájaný zoznam, pridávanie a odoberanie prvkov na začiatku je symetrické k pridávaniu a odoberaniu prvkov na konci -- a funguje presne tak, ako fungovalo pridávanie a odoberanie prvkov v zásobníku (treba si len dať pozor na to, aby sme aktualizovali správny smerník). S pozeraním sa prvky je to tiež jednoduché -- stačí použiť správny smerník.
Implementácia pomocou poľa je podobnejšia implementácii radu. Máme také isté pole $A$ dĺžky $n$, index $zaciatok$ a premennú $k$. Keď chceme vkladať na začiatok obojsmerného radu (a používané pole nie je plné), $zaciatok$ zmeníme na $(zaciatok - 1) \% n$2, nový prvok vložíme na $A[zaciatok]$ a $k$ zväčšíme o $1$. Keď chceme odobrať posledný prvok (a používané pole nie je prázdne), $k$ jednoducho zmenšíme o $1$.
Obe implementácie majú rovnaké zložitosti. Pamäťová zložitosť celej štruktúry je $n$. Časové zložitosti jednotlivých operácií sú rovnaké -- $O(1)$. (Pre obojsmerný rad platí rovnaká poznámka o časovej zložitosti pridávania prvku ako pre zásobník a obyčajný rad.)
Poznámka pre pokročilých: obojsmerný rad sa používa pri implementácii BFS na grafe, ktorého hrany môžu mať ceny $0$ alebo $1$. ↩
Pozor, v niektorých jazykov operácia modulo funguje neintuitívne, a tak sa stane, že $9 \% 5$ nie je to isté ako $-1 \% 5$ (lebo $9 \% 5 = 4$, kým $-1 \% 5 = -1$). Pre tieto prípady je vždy, keď modulujeme, vhodné pripočítať číslo, ktorým modulujeme -- teda $(zaciatok - 1 + n) \% n$. ↩