Obojsmerná fronta (deque)

Obojsmerná fronta (double-ended queue, čiže deque) je kombináciou zásobníka a fronty. 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:

  • pridať prvok na koniec alebo na začiatok,
  • odobrať prvok z konca alebo zo začiatku,
  • pozrieť sa na prvý alebo posledný prvok.

Pamäťová zložitosť celej štruktúry je $O(n)$. Časové zložitosti jednotlivých operácií sú rovnaké -- $O(1)$.

Implementácia

Pridanie prvku na začiatok

Metóda appendleft() pridá prvok na začiatok deque.

from collections import deque

deq = deque()
deq.appendleft(1)
deq.appendleft(2)

# deq aktuálne obsahuje [2, 1]

Pridanie prvku na koniec

Metóda append() pridá prvok na koniec deque.

deq.append(3)

# deq obsahuje [2, 1, 3]

Odstránenie prvku zo začiatku

Metóda popleft() vráti a odstráni prvok zo začiatku deque.

deq.popleft()  # dostaneme 2

Odstránenie prvku z konca

Metóda pop() odstráni prvok z konca deque.

deq.pop()  # dostaneme 3

Nahliadnutie na prvok na začiatku

Prístup k prvku na začiatku deque môžeme spraviť cez index 0.

deq[0]

Nahliadnutie na prvok na konci

Prístup k poslednému prvku deque môžeme spraviť cez index -1.

deq[-1]

Pred prístupom k indexu 0 alebo -1 je však dobré vždy skontrolovať, či deque nie je prázdna. Ak by bola prázdna, viedlo by to k chybe IndexError.

Ďalej