PricingLoginStart free
Java Academy · Lektion

Deque-operationer: stack och kö

Använd LinkedList som en Deque för att implementera stackbeteende (push/pop) och köbeteende (offer/poll).

Lektion 2 av 413 steg

Deque-operationer: stack och kö är en gratis lektion i Java Academy på CoddyKit. Detta är lektion 2 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Java Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Java Academy innehåller totalt 4 lektioner.

Deque: dubbelsidig kö

En Deque (Double-Ended Queue) tillåter insättningar och borttagningar i båda ändarna. Javas Deque-gränssnitt implementeras av LinkedList och 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 jämfört med LinkedList som Deque

ArrayDeque föredras i allmänhet framför LinkedList som Deque:

  • Ingen nodöverkostnad per element
  • Bättre cachelokalitet
  • Något snabbare stack- och köoperationer

Välj endast LinkedList när ni även behöver List-gränssnittet.

Stackoperationer med Deque

Använd push (addFirst) och pop (removeFirst) för att simulera en LIFO-stack. Undvik den äldre klassen Stack — den är synkroniserad och föråldrad.

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

Använd offer (addLast) och poll (removeFirst) för att simulera en FIFO-kö. offer returnerar false vid fel, medan add kastar ett undantag.

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

Referenstabell för Deque-metoder

Deque erbjuder två metodfamiljer — en som kastar undantag och en som returnerar specialvärden:

  • addFirst/addLast jämfört med offerFirst/offerLast
  • removeFirst/removeLast jämfört med pollFirst/pollLast
  • getFirst/getLast jämfört med peekFirst/peekLast

Föredra offer/poll/peek-familjen för att undvika undantag när deque:n är tom.

Verkligt exempel: ångra/gör om med två stackar

Ett klassiskt användningsområde för Deque: ångrahistoriken är en stack. Gör om använder en annan 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 gör palindromkontroll elegant — jämför tecken från båda ändarna samtidigt.

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ö

Breadth-First Search använder en kö. ArrayDeque är standardvalet för BFS inom tävlingsprogrammering och graftraversering.

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

Depth-First Search använder en stack. Även här bör ni föredra ArrayDeque framför den äldre klassen 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);
    }
}

Begränsad Deque med storlekskontroll

ArrayDeque växer dynamiskt, men ni kan införa en kapacitetsgräns manuellt för att simulera en buffert med begränsad storlek:

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]

Prestandaanmärkningar

ArrayDeque använder en cirkulär array som fördubblas när den blir full. Den amorterade kostnaden för alla operationer är O(1). Den presterar bättre än LinkedList i de flesta mätningar tack vare cacheeffektiviteten. Synkronisera aldrig manuellt — använd ConcurrentLinkedDeque eller en blockerande kö för samtidighet.

Snabbkontroll

Vilken klass bör ni föredra framför den äldre Stack för LIFO-operationer?

Besvara frågan i den interaktiva lektionen

Sammanfattning: Deque-operationer

Viktiga slutsatser:

  • Deque tillåter O(1)-insättningar och borttagningar i båda ändarna
  • ArrayDeque föredras framför LinkedList för ren stack- eller köanvändning
  • push/pop → LIFO-stack; offer/poll → FIFO-kö
  • Klassiska användningsområden: ångra/gör om, BFS/DFS, glidande fönster och palindromkontroll
  • Undvik de äldre Stack- och Queue-klasserna
Gratis att börja

Lär dig Java med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser
104
Lektioner
374
Börja lära dig gratisVisa hela kursen

Vanliga frågor

Är lektionen ”Deque-operationer: stack och kö” gratis?

Ja – hela texten till ”Deque-operationer: stack och kö” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Java Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Java Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”Deque-operationer: stack och kö”?

Använd LinkedList som en Deque för att implementera stackbeteende (push/pop) och köbeteende (offer/poll). Ni övar på Java Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Java Academy?

Du behöver inga förkunskaper. Utbildningen i Java Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.

Hur lång tid tar lektionen ”Deque-operationer: stack och kö”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Java Academy-lektionen?

Ja. Varje Java Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

  1. LinkedList internt
  2. Deque-operationer: stack och kö
  3. LinkedList kontra ArrayList
  4. PriorityQueue för ordnad bearbetning
← Tillbaka till Java Academy