Operacje Deque: stos i kolejka
Używaj LinkedList jako Deque, aby implementować działanie stosu (push/pop) i kolejki (offer/poll).
Operacje Deque: stos i kolejka to bezpłatna lekcja Java Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Java Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Java Academy zawiera 4 lekcji w sumie.
Deque: kolejka dwustronna
Deque (kolejka dwustronna) umożliwia wstawianie i usuwanie elementów na obu końcach. Interfejs Deque w Javie jest implementowany przez LinkedList i ArrayDeque.
import java.util.Deque;
import java.util.ArrayDeque;
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("A"); // front
deque.addLast("B"); // back
deque.addFirst("Z"); // new front
System.out.println(deque); // [Z, A, B]ArrayDeque a LinkedList jako Deque
ArrayDeque jest zazwyczaj preferowana jako Deque zamiast LinkedList:
- Brak narzutu węzła dla każdego elementu
- Lepsza lokalność pamięci podręcznej
- Nieco szybsze operacje stosu/kolejki
LinkedList należy wybrać tylko wtedy, gdy potrzebny jest również interfejs List.
Operacje stosu za pomocą Deque
Użyj push (addFirst) i pop (removeFirst), aby zasymulować stos LIFO. Unikaj starszej klasy Stack — jest synchronizowana i przestarzała.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 3
System.out.println(stack.peek()); // 2 (no removal)
System.out.println(stack.pop()); // 2Operacje kolejki za pomocą Deque
Użyj offer (addLast) i poll (removeFirst), aby zasymulować kolejkę FIFO. offer zwraca false w razie niepowodzenia, a add zgłasza wyjątek.
Deque<String> queue = new ArrayDeque<>();
queue.offer("task1");
queue.offer("task2");
queue.offer("task3");
System.out.println(queue.poll()); // task1
System.out.println(queue.poll()); // task2
System.out.println(queue.size()); // 1Tabela metod Deque
Deque udostępnia dwie rodziny metod — jedna zgłasza wyjątki, druga zwraca wartości specjalne:
- addFirst/addLast i offerFirst/offerLast
- removeFirst/removeLast i pollFirst/pollLast
- getFirst/getLast i peekFirst/peekLast
Preferuj rodzinę offer/poll/peek, aby uniknąć wyjątków dla pustych kolejek dwustronnych.
Praktyczny przykład: cofanie/ponawianie za pomocą dwóch stosów
Klasyczne zastosowanie Deque: historia cofania jest stosem. Ponawianie zmian to drugi stos.
Deque<String> undo = new ArrayDeque<>();
Deque<String> redo = new ArrayDeque<>();
undo.push("type 'Hello'");
undo.push("type ' World'");
String action = undo.pop();
System.out.println("Undone: " + action); // type ' World'
redo.push(action);
System.out.println("Redo top: " + redo.peek()); // type ' World'Sprawdzanie palindromu za pomocą Deque
Deque upraszcza sprawdzanie palindromów — znaki z obu końców można porównywać jednocześnie.
Deque<Character> deque = new ArrayDeque<>();
for (char c : "racecar".toCharArray()) deque.add(c);
boolean isPalindrome = true;
while (deque.size() > 1) {
if (!deque.pollFirst().equals(deque.pollLast())) {
isPalindrome = false;
break;
}
}
System.out.println(isPalindrome); // trueBFS z kolejką
Przeszukiwanie wszerz korzysta z kolejki. ArrayDeque to standardowy wybór dla BFS w programowaniu konkursowym i podczas przechodzenia grafów.
import java.util.*;
// BFS on a simple adjacency list
Map<Integer,List<Integer>> graph = Map.of(
1, List.of(2,3),
2, List.of(4),
3, List.of(4),
4, List.of()
);
Deque<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(1);
while (!queue.isEmpty()) {
int node = queue.poll();
if (visited.add(node)) {
System.out.print(node + " ");
queue.addAll(graph.get(node));
}
}DFS ze stosem
Przeszukiwanie w głąb korzysta ze stosu. Ponownie preferuj ArrayDeque zamiast starszej klasy Stack.
Deque<Integer> stack = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
stack.push(1);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited.add(node)) {
System.out.print(node + " ");
// push neighbors (will be processed in reverse order)
List<Integer> neighbors = List.of(2, 3); // simplified
for (int n : neighbors) if (!visited.contains(n)) stack.push(n);
}
}Ograniczona Deque ze sprawdzaniem rozmiaru
ArrayDeque zwiększa rozmiar dynamicznie, ale można ręcznie wymusić limit pojemności, aby zasymulować bufor o ograniczonym rozmiarze:
Deque<Integer> buffer = new ArrayDeque<>();
int MAX = 3;
for (int i = 1; i <= 5; i++) {
if (buffer.size() >= MAX) {
buffer.pollFirst(); // drop oldest
}
buffer.offerLast(i);
}
System.out.println(buffer); // [3, 4, 5]Uwagi dotyczące wydajności
ArrayDeque korzysta z tablicy cyklicznej, która po zapełnieniu podwaja rozmiar. Zamortyzowany koszt wszystkich operacji wynosi O(1). W większości testów wydajności przewyższa LinkedList dzięki lepszemu wykorzystaniu pamięci podręcznej. Nigdy nie synchronizuj ręcznie — w przypadku współbieżności użyj ConcurrentLinkedDeque lub kolejki blokującej.
Szybki test
Którą klasę należy preferować zamiast starszej klasy Stack w operacjach LIFO?
Podsumowanie: operacje Deque
Najważniejsze informacje:
- Deque umożliwia wstawianie i usuwanie elementów na obu końcach w czasie O(1)
- ArrayDeque jest preferowana zamiast LinkedList do użycia wyłącznie jako stos lub kolejka
- push/pop → stos LIFO; offer/poll → kolejka FIFO
- Klasyczne zastosowania: cofanie/ponawianie, BFS/DFS, okno przesuwne, sprawdzanie palindromu
- Unikaj starszych klas Stack i Queue
Często zadawane pytania
Czy lekcja „Operacje Deque: stos i kolejka” jest bezpłatna?
Tak — pełny tekst „Operacje Deque: stos i kolejka” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Java Academy, przejdź na CoddyKit PRO. Kurs Java Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Operacje Deque: stos i kolejka”?
Używaj LinkedList jako Deque, aby implementować działanie stosu (push/pop) i kolejki (offer/poll). Ćwiczysz Java Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Java Academy?
Nie wymagamy żadnego doświadczenia. Java Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Operacje Deque: stos i kolejka”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Java Academy?
Tak. Każda lekcja Java Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Wewnętrzne działanie LinkedList
- Operacje Deque: stos i kolejka
- LinkedList a ArrayList — kompromisy
- PriorityQueue do uporządkowanego przetwarzania