Java Academy · Lektion

Deque-operationer: stack og queue

Brug LinkedList som en Deque til at implementere stack-adfærd (push/pop) og queue-adfærd (offer/poll).

Lektion 2 af 413 trin

Deque-operationer: stack og queue er en gratis Java Academy-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Java Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Java Academy-kurset indeholder 4 lektioner i alt.

Deque: Kø med to ender

En Deque, altså en kø med to ender, tillader indsættelser og fjernelser i begge ender. Javas Deque-grænseflade implementeres af LinkedList og 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 og LinkedList som Deque

ArrayDeque foretrækkes normalt frem for LinkedList som Deque:

Intet overhead fra knuder pr. element
Bedre cache-lokalitet
Lidt hurtigere til stak- og køoperationer

Vælg kun LinkedList, når du også har brug for List-grænsefladen.

Stakoperationer med Deque

Brug push (addFirst) og pop (removeFirst) til at simulere en LIFO-stak. Undgå den forældede Stack-klasse — den er synkroniseret og forældet.

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());  // 2

Køoperationer med Deque

Brug offer (addLast) og poll (removeFirst) til at simulere en FIFO-kø. offer returnerer false ved fejl; add kaster en undtagelse.

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());  // 1

Referencetabel for Deque-metoder

Deque tilbyder to metodefamilier — én, der kaster undtagelser, og én, der returnerer særlige værdier:

addFirst/addLast over for offerFirst/offerLast
removeFirst/removeLast over for pollFirst/pollLast
getFirst/getLast over for peekFirst/peekLast

Foretræk offer/poll/peek-familien for at undgå undtagelser, når deques er tomme.

Virkeligt eksempel: Fortryd/gentag med to stakke

En klassisk anvendelse af Deque: Fortrydelseshistorikken er en stak. Gentagelse er en anden stak.

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'

Palindromtjek med Deque

Deques gør det elegant at tjekke for palindromer — sammenlign tegn fra begge ender samtidig.

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); // true

BFS med kø

Bredde-først-søgning bruger en kø. ArrayDeque er det almindelige valg til BFS i konkurrenceprogrammering og gennemløb af grafer.

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 med stak

Dybde-først-søgning bruger en stak. Foretræk igen ArrayDeque frem for den forældede Stack-klasse.

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);
    }
}

Begrænset Deque med størrelsestjek

ArrayDeque vokser dynamisk, men du kan håndhæve en kapacitet manuelt for at simulere en buffer med begrænset størrelse:

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]

Bemærkninger om ydeevne

ArrayDeque bruger et cirkulært array, der fordobles, når det er fuldt. Den amortiserede omkostning ved alle operationer er O(1). Den klarer sig bedre end LinkedList i de fleste benchmarks på grund af bedre cacheeffektivitet. Synkronisér aldrig manuelt — brug ConcurrentLinkedDeque eller en blokerende kø til samtidighed.

Hurtigt tjek

Hvilken klasse bør du foretrække frem for den forældede Stack til LIFO-operationer?

Besvar den i den interaktive lektion

Opsummering: Deque-operationer

Vigtigste pointer:

Deque tillader O(1)-indsættelser og -fjernelser i begge ender
ArrayDeque foretrækkes frem for LinkedList til ren stak- eller køanvendelse
push/pop → LIFO-stak; offer/poll → FIFO-kø
Klassiske anvendelser: fortryd/gentag, BFS/DFS, glidende vindue og palindromtjek
Undgå de forældede Stack- og Queue-klasser

Gratis at komme i gang

Lær Java med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 104
Lektioner: 374

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Deque-operationer: stack og queue” gratis?

Ja — hele teksten til “Deque-operationer: stack og queue” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Java Academy-kurset, skal du opgradere til CoddyKit PRO. Java Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Deque-operationer: stack og queue”?

Brug LinkedList som en Deque til at implementere stack-adfærd (push/pop) og queue-adfærd (offer/poll). Du øver dig i Java Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på Java Academy?

Der kræves ingen tidligere erfaring. Java Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.

Hvor lang tid tager lektionen “Deque-operationer: stack og queue”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne Java Academy-lektion?

Ja. Alle Java Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til Java Academy