Deque

push · pop both ends O(1)

Deque (oboustranná fronta) je fronta otevřená na obou koncích: přidávat i odebírat můžeš vepředu i vzadu, vždy v konstantním čase. Zobecňuje zásobník i frontu a hodí se pro algoritmy s posuvným oknem nebo plánovače s kradením práce.

Deque
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. pushFront / pushBack přidá hodnotu vepředu nebo vzadu.
  2. popFront / popBack odebere hodnotu zepředu nebo zezadu.
  3. Jeden konec použiješ jako zásobník, oba jako frontu — podle potřeby algoritmu.

Pseudokód

1pushFront(v):  items.prepend(v)            # O(1)2pushBack(v):   items.append(v)             # O(1)34popFront():    return items.removeFirst()  # O(1)5popBack():     return items.removeLast()   # O(1)