Java Academy · leksjon

Deque-operasjoner: stack og kø

Bruk LinkedList som en Deque for å implementere stack- (push/pop) og køoppførsel (offer/poll).

Leksjon 2 av 413 trinn

Deque-operasjoner: stack og kø er en gratis leksjon i Java Academy på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Java Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Java Academy inneholder totalt 4 leksjoner.

Deque: Kø med to ender

En Deque (kø med to ender) tillater innsettinger og fjerninger i begge ender. Java's Deque-grensesnitt implementeres av 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 kontra LinkedList som Deque

ArrayDeque er vanligvis å foretrekke fremfor LinkedList som Deque:

Ingen nodeoverhead per element
Bedre cache-lokalitet
Litt raskere stack-/queue-operasjoner

Velg bare LinkedList når du også trenger List-grensesnittet.

Stack-operasjoner med Deque

Bruk push (addFirst) og pop (removeFirst) for å simulere en LIFO-stack. Unngå den eldre Stack-klassen — den er synkronisert og foreldet.

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

Queue-operasjoner med Deque

Bruk offer (addLast) og poll (removeFirst) for å simulere en FIFO-kø. offer returnerer false ved feil; add kaster et unntak.

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

Metodereferanse for Deque

Deque tilbyr to metodefamilier — én som kaster unntak, og én som returnerer spesialverdier:

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

Foretrekk offer/poll/peek-familien for å unngå unntak når deque-er er tomme.

Praktisk eksempel: Angre/gjør om med to stacker

Et klassisk bruksområde for Deque: Angre-historikken er en stack. Gjør om bruker en annen stack.

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'

Palindromkontroll med Deque

Deque gjør det elegant å kontrollere 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ø

Breddeførstesøk bruker en kø. ArrayDeque er standardvalget for BFS i konkurranseprogrammering og gjennomgang av 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 stack

Dybdeførstesøk bruker en stack. Også her bør du foretrekke ArrayDeque fremfor den eldre Stack-klassen.

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

Begrenset Deque med størrelseskontroll

ArrayDeque vokser dynamisk, men du kan håndheve en kapasitet manuelt for å simulere en begrenset buffer:

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]

Ytelsesmerknader

ArrayDeque bruker et sirkulært array som dobles når det er fullt. Den amortiserte kostnaden for alle operasjoner er O(1). Den er raskere enn LinkedList i de fleste ytelsesmålinger på grunn av bedre cache-utnyttelse. Synkroniser aldri manuelt — bruk ConcurrentLinkedDeque eller en blokkerende kø for samtidighet.

Kort sjekk

Hvilken klasse bør du foretrekke fremfor den eldre Stack-klassen for LIFO-operasjoner?

Besvar den i den interaktive leksjonen

Oppsummering: Deque-operasjoner

Viktigste punkter:

Deque tillater O(1)-innsettinger og -fjerninger i begge ender
ArrayDeque foretrekkes fremfor LinkedList når den utelukkende skal brukes som stack eller queue
push/pop → LIFO-stack; offer/poll → FIFO-kø
Klassiske bruksområder: angre/gjør om, BFS/DFS, glidende vindu og palindromkontroll
Unngå de eldre Stack- og Queue-klassene

Gratis å komme i gang

Lær deg Java med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 104
Leksjoner: 374

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Deque-operasjoner: stack og kø» gratis?

Ja – hele teksten i «Deque-operasjoner: stack og kø» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Java Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Java Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Deque-operasjoner: stack og kø»?

Bruk LinkedList som en Deque for å implementere stack- (push/pop) og køoppførsel (offer/poll). Du øver på Java Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Java Academy?

Ingen tidligere erfaring er nødvendig. Java Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.

Hvor lang tid tar leksjonen «Deque-operasjoner: stack og kø»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Java Academy-leksjonen?

Ja. Alle Java Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til Java Academy