Dobbelt-endt kø

Deque, eller dobbelt-endt kø, muliggør arbejde med køer fra både forenden og bagenden.

Deque-interfacet udvider Queue-interfacet, så en klasse som LinkedList implementerer også dette interface.

Derfor vil du igen bruge LinkedList, men denne gang med et nyt interface.

Deklaration af et objekt med Deque-typen adskiller sig ikke fra Queue:

Main.java


              1
            
Deque<T> deque = new LinkedList<>();

Den væsentligste forskel opstår, når vi ser på metoderne i dette interface.

Da en Deque er en dobbelt-endt kø, hvilket betyder, at du kan arbejde med elementer både forrest og bagerst i køen, er dens metoder tilpasset denne funktionalitet.

Metoder

Nogle centrale metoder i Deque-interfacet er:

addFirst(element): tilføjer et element forrest i deque;
addLast(element): tilføjer et element bagerst i deque.

Det er tydeligt, at der i en deque findes metoder til at tilføje både forrest og bagerst. Navnene på disse metoder er selvforklarende. Lad os se nærmere på disse metoder i kode:

Main.java


              123456789101112131415
            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.addFirst("One");
        deque.addLast("Two");
        System.out.println("Deque: " + deque);
        deque.addFirst("Zero");
        System.out.println("Deque after the `addFirst()` method: " + deque);
    }
}

Som du kan se, efter brug af addFirst()-metoden, blev elementet tilføjet til begyndelsen af deque'en. Dette adskiller sig fra addLast()-metoden.

Deque har også en almindelig add()-metode, som fungerer på samme måde som addLast()-metoden. Derfor er det helt op til dig, hvilken metode du vælger at bruge.

Fjernelsesmetoder

Hvis der findes metoder til at tilføje elementer i begyndelsen og slutningen, bør der også være metoder til at fjerne fra begyndelsen og slutningen af deque'en.

removeFirst(): fjerner og returnerer elementet fra begyndelsen af deque'en;
removeLast(): fjerner og returnerer elementet fra slutningen af deque'en.

Metoderne addFirst() og addLast() udfører fjernelse af elementer fra begyndelsen og slutningen af deque'en.

Lad os se et eksempel på brug i koden:

Main.java


              1234567891011121314151617
            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.add("One");
        deque.add("Second");
        deque.add("Third");
        System.out.println("Deque: " + deque);
        deque.removeFirst();
        deque.removeLast();
        System.out.println("Deque after the removal methods method: " + deque);
    }
}

Som du kan se, har vi fjernet det første og sidste element fra deque'en, så kun det andet element er tilbage.

Det er enkelt og bekvemt, og metodenavnene taler for sig selv.

Hentemetoder

Lad os nu gå videre til metoderne til adgang til elementer i en deque.

getFirst(): henter, men fjerner ikke, elementet i forenden af deque'en;
getLast(): henter, men fjerner ikke, elementet i enden af deque'en.

Dette gør det muligt at tilgå første og sidste element i en dobbeltkøet kø.

Lad os nu se et eksempel i kode:

Main.java


              123456789101112131415161718
            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.add("One");
        deque.add("Second");
        deque.add("Third");
        System.out.println("Deque: " + deque);
        String first = deque.getFirst();
        String last = deque.getLast();
        System.out.println("The first element in the deque: " + first);
        System.out.println("The last element in the deque: " + last);
    }
}

Ved hjælp af metoderne getFirst() og getLast() blev de første og sidste elementer fra deque'en hentet og tildelt til nyoprettede variabler.

I Deque-interfacet findes også metoderne peekFirst() og peekLast(), som løser problemet med at kaste en undtagelse. I stedet for at kaste en undtagelse og stoppe programmet, returnerer de null, hvis køen er tom.

Lad os se på et eksempel:

Main.java


              123456789101112131415
            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        System.out.println("Deque: " + deque);
        String first = deque.peekFirst();
        System.out.println("The first element in the deque: " + first);
        String last = deque.getLast();
        System.out.println("The last element in the deque: " + last);
    }
}

Ud fra dette eksempel blev det tydeligt, at det er meget bedre at bruge metoderne peekFirst() og peekLast() i stedet for getFirst() og getLast(), da de ikke vil stoppe programmet i tilfælde af en fejl.

Dog må du ikke glemme NullPointerException! Denne undtagelse kan forårsage mange problemer i dit program.

Der findes også tilsvarende alternative metoder til metoderne addFirst(), addLast(), removeFirst() og removeLast(). Vi vil ikke dvæle længe ved dem, da du allerede forstår, hvordan disse metoder fungerer, men her er listen:

Alternative metoder

Metoder til at tilføje et element til deque'en:

offerFirst(E e): tilføjer et element forrest i deque'en, hvis det er muligt, og returnerer true. Returnerer false, hvis tilføjelsen ikke er mulig;
offerLast(E e): tilføjer et element bagerst i deque'en, hvis det er muligt, og returnerer true. Returnerer false, hvis tilføjelsen ikke er mulig;
push(E e): tilføjer et element forrest i deque'en, svarende til addFirst(). Bemærk, at push() også er en stak-metode i Deque-klassen.

Metoder til at fjerne et element fra deque'en:

pollFirst(): fjerner og returnerer det første element i deque'en. Returnerer null, hvis deque'en er tom;
pollLast(): fjerner og returnerer det sidste element i deque'en. Returnerer null, hvis deque'en er tom;
pop(): fjerner og returnerer det første element i deque'en, svarende til removeFirst().

Valget afhænger af programmets krav. Du kan altid løse alt med et almindeligt array, men det ville være ret udfordrende, og det ville ikke være optimeret. Derfor findes der så mange forskellige datastrukturer—for at gøre det mere bekvemt at skrive forskellige programmer.

Var alt klart?

Tak for dine kommentarer!

Sektion 2. Kapitel 2

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Suggested prompts:

What are some real-world use cases for a Deque?

Can you explain the difference between a Deque and a regular Queue?

How do I choose between using addFirst/addLast and offerFirst/offerLast?

Stryg for at vise menuen

Dobbelt-endt kø

Deque, eller dobbelt-endt kø, muliggør arbejde med køer fra både forenden og bagenden.

Deque-interfacet udvider Queue-interfacet, så en klasse som LinkedList implementerer også dette interface.

Derfor vil du igen bruge LinkedList, men denne gang med et nyt interface.

Deklaration af et objekt med Deque-typen adskiller sig ikke fra Queue:

Main.java


              1
            
Deque<T> deque = new LinkedList<>();

Den væsentligste forskel opstår, når vi ser på metoderne i dette interface.

Da en Deque er en dobbelt-endt kø, hvilket betyder, at du kan arbejde med elementer både forrest og bagerst i køen, er dens metoder tilpasset denne funktionalitet.

Metoder

Nogle centrale metoder i Deque-interfacet er:

addFirst(element): tilføjer et element forrest i deque;
addLast(element): tilføjer et element bagerst i deque.

Det er tydeligt, at der i en deque findes metoder til at tilføje både forrest og bagerst. Navnene på disse metoder er selvforklarende. Lad os se nærmere på disse metoder i kode:

Main.java


              123456789101112131415
            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.addFirst("One");
        deque.addLast("Two");
        System.out.println("Deque: " + deque);
        deque.addFirst("Zero");
        System.out.println("Deque after the `addFirst()` method: " + deque);
    }
}

Som du kan se, efter brug af addFirst()-metoden, blev elementet tilføjet til begyndelsen af deque'en. Dette adskiller sig fra addLast()-metoden.

Deque har også en almindelig add()-metode, som fungerer på samme måde som addLast()-metoden. Derfor er det helt op til dig, hvilken metode du vælger at bruge.

Fjernelsesmetoder

Hvis der findes metoder til at tilføje elementer i begyndelsen og slutningen, bør der også være metoder til at fjerne fra begyndelsen og slutningen af deque'en.

removeFirst(): fjerner og returnerer elementet fra begyndelsen af deque'en;
removeLast(): fjerner og returnerer elementet fra slutningen af deque'en.

Metoderne addFirst() og addLast() udfører fjernelse af elementer fra begyndelsen og slutningen af deque'en.

Lad os se et eksempel på brug i koden:

Main.java


              1234567891011121314151617
            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.add("One");
        deque.add("Second");
        deque.add("Third");
        System.out.println("Deque: " + deque);
        deque.removeFirst();
        deque.removeLast();
        System.out.println("Deque after the removal methods method: " + deque);
    }
}

Som du kan se, har vi fjernet det første og sidste element fra deque'en, så kun det andet element er tilbage.

Det er enkelt og bekvemt, og metodenavnene taler for sig selv.

Hentemetoder

Lad os nu gå videre til metoderne til adgang til elementer i en deque.

getFirst(): henter, men fjerner ikke, elementet i forenden af deque'en;
getLast(): henter, men fjerner ikke, elementet i enden af deque'en.

Dette gør det muligt at tilgå første og sidste element i en dobbeltkøet kø.

Lad os nu se et eksempel i kode:

Main.java


              123456789101112131415161718
            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.add("One");
        deque.add("Second");
        deque.add("Third");
        System.out.println("Deque: " + deque);
        String first = deque.getFirst();
        String last = deque.getLast();
        System.out.println("The first element in the deque: " + first);
        System.out.println("The last element in the deque: " + last);
    }
}

Ved hjælp af metoderne getFirst() og getLast() blev de første og sidste elementer fra deque'en hentet og tildelt til nyoprettede variabler.

Lad os se på et eksempel:

Main.java


              123456789101112131415
            
package com.example;

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        System.out.println("Deque: " + deque);
        String first = deque.peekFirst();
        System.out.println("The first element in the deque: " + first);
        String last = deque.getLast();
        System.out.println("The last element in the deque: " + last);
    }
}

Dog må du ikke glemme NullPointerException! Denne undtagelse kan forårsage mange problemer i dit program.

Alternative metoder

Metoder til at tilføje et element til deque'en:

offerFirst(E e): tilføjer et element forrest i deque'en, hvis det er muligt, og returnerer true. Returnerer false, hvis tilføjelsen ikke er mulig;
offerLast(E e): tilføjer et element bagerst i deque'en, hvis det er muligt, og returnerer true. Returnerer false, hvis tilføjelsen ikke er mulig;
push(E e): tilføjer et element forrest i deque'en, svarende til addFirst(). Bemærk, at push() også er en stak-metode i Deque-klassen.

Metoder til at fjerne et element fra deque'en:

pollFirst(): fjerner og returnerer det første element i deque'en. Returnerer null, hvis deque'en er tom;
pollLast(): fjerner og returnerer det sidste element i deque'en. Returnerer null, hvis deque'en er tom;
pop(): fjerner og returnerer det første element i deque'en, svarende til removeFirst().

Var alt klart?

Tak for dine kommentarer!

Sektion 2. Kapitel 2

Deque Datastruktur i Java

Dobbelt-endt kø

Metoder

Fjernelsesmetoder

Hentemetoder

Alternative metoder

1. Hvad står "Deque" for?

2. Hvilket interface i Java repræsenterer en Deque?

3. Hvad er formålet med metoden `addFirst()` i en Deque?

4. Hvilken metode bruges til at hente, men ikke fjerne, det sidste element i en Deque?

Deque Datastruktur i Java

Dobbelt-endt kø

Metoder

Fjernelsesmetoder

Hentemetoder

Alternative metoder

1. Hvad står "Deque" for?

2. Hvilket interface i Java repræsenterer en Deque?

3. Hvad er formålet med metoden `addFirst()` i en Deque?

4. Hvilken metode bruges til at hente, men ikke fjerne, det sidste element i en Deque?

Deque Datastruktur i Java

Dobbelt-endt kø

Metoder

Fjernelsesmetoder

Hentemetoder

Alternative metoder

1. Hvad står "Deque" for?

2. Hvilket interface i Java repræsenterer en Deque?

3. Hvad er formålet med metoden addFirst() i en Deque?

4. Hvilken metode bruges til at hente, men ikke fjerne, det sidste element i en Deque?

Deque Datastruktur i Java

Dobbelt-endt kø

Metoder

Fjernelsesmetoder

Hentemetoder

Alternative metoder

1. Hvad står "Deque" for?

2. Hvilket interface i Java repræsenterer en Deque?

3. Hvad er formålet med metoden addFirst() i en Deque?

4. Hvilken metode bruges til at hente, men ikke fjerne, det sidste element i en Deque?

3. Hvad er formålet med metoden `addFirst()` i en Deque?

3. Hvad er formålet med metoden `addFirst()` i en Deque?