Deque pozwala dodawać i usuwać elementy zarówno z przodu, jak i z tyłu. Przy implementacji jako bufor cykliczny lub lista te operacje są O(1).
Odpowiedź zaawansowana
Głębiej
Deque (double-ended queue) obsługuje O(1) dodawanie i usuwanie z obu końców: addFirst/addLast oraz removeFirst/removeLast. W praktyce często jest to implementacja tablicowa jako bufor cykliczny (dobra lokalność cache) albo lista.
Deque może działać jako:
Kolejka (FIFO): addLast + removeFirst
Stos (LIFO): addLast + removeLast
Przykłady
ArrayDeque<Integer> d = new ArrayDeque<>();
d.addLast(1);
d.addLast(2);
int first = d.removeFirst(); // 1
d.addFirst(10);
int last = d.removeLast(); // 2
Gdzie się przydaje
BFS: dodajesz sąsiadów na koniec, zdejmujesz z początku.
Sliding window / monotonic queue (np. maksimum w oknie).
0-1 BFS: krawędzie o wadze 0 wrzucasz na przód, a o wadze 1 na tył.
Typowe pułapki
Deque nie służy do dostępu po indeksie; usuwanie ze środka jest