Java Academy · Oppitunti

Deque-toiminnot: pino ja jono

Käytä LinkedListia Deque-rakenteena pinon (push/pop) ja jonon (offer/poll) toteuttamiseen.

Oppitunti 2/413 vaihetta

Deque-toiminnot: pino ja jono on ilmainen Java Academy-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Java Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Java Academy-kurssilla on yhteensä 4 oppituntia.

Deque: kaksipäinen jono

Deque (kaksipäinen jono) mahdollistaa lisäykset ja poistot molemmista päistä. Javan Deque-rajapinnan toteuttavat LinkedList ja 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 ja LinkedList Deque-rakenteena

ArrayDeque-rakennetta suositellaan yleensä LinkedList-rakenteen sijaan Deque-rakenteeksi:

Ei alkiokohtaista solmujen aiheuttamaa lisäkuormaa
Parempi välimuistin paikallisuus
Hieman nopeampi pino- ja jonotoiminnoissa

Valitkaa LinkedList vain, jos tarvitsette lisäksi List-rajapinnan.

Pinotoiminnot Dequella

Käyttäkää push-menetelmää (addFirst) ja pop-menetelmää (removeFirst) LIFO-pinon simulointiin. Välttäkää vanhaa Stack-luokkaa — se on synkronoitu ja vanhentunut.

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

Jonotoiminnot Dequella

Käyttäkää offer-menetelmää (addLast) ja poll-menetelmää (removeFirst) FIFO-jonon simulointiin. offer palauttaa epäonnistuessaan arvon false; add heittää poikkeuksen.

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

Deque-metodien viitetaulukko

Deque tarjoaa kaksi metodiperhettä — toinen heittää poikkeuksia ja toinen palauttaa erityisarvoja:

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

Suosikaa offer/poll/peek-perhettä, jotta tyhjät Deque-rakenteet eivät aiheuta poikkeuksia.

Käytännön esimerkki: kumoaminen ja uudelleen tekeminen kahdella pinolla

Klassinen Dequen käyttötapaus: kumoamishistoria on pino. Uudelleen tekeminen on toinen pino.

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'

Palindromin tarkistus Dequella

Deque tekee palindromin tarkistamisesta eleganttia — merkkejä verrataan samanaikaisesti molemmista päistä.

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 jonon avulla

Leveyshaku (Breadth-First Search) käyttää jonoa. ArrayDeque on vakiovalinta BFS:ään kilpailuohjelmoinnissa ja graafien läpikäynnissä.

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 pinon avulla

Syvyyshaku (Depth-First Search) käyttää pinoa. Jälleen ArrayDeque-rakennetta kannattaa suosia vanhan Stack-luokan sijaan.

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

Rajoitettu Deque kokotarkistuksella

ArrayDeque kasvaa dynaamisesti, mutta kapasiteetin voi rajoittaa itse rajatun puskurin simuloimiseksi:

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]

Suorituskykyhuomioita

ArrayDeque käyttää pyöreää taulukkoa, jonka koko kaksinkertaistuu sen täyttyessä. Kaikkien toimintojen amortisoitu kustannus on O(1). Se suoriutuu useimmissa vertailuissa LinkedListiä paremmin välimuistitehokkuuden ansiosta. Älkää koskaan synkronoitko sitä itse — käyttäkää samanaikaisuuteen ConcurrentLinkedDeque-rakennetta tai blokkaavaa jonoa.

Pikatarkistus

Mitä luokkaa tulisi suosia vanhentuneen Stack-luokan sijaan LIFO-toiminnoissa?

Vastaa interaktiivisessa oppitunnissa

Kertaus: Deque-toiminnot

Tärkeimmät asiat:

Deque mahdollistaa O(1)-aikaiset lisäykset ja poistot molemmista päistä
ArrayDeque on suositeltavampi kuin LinkedList, kun tarvitaan pelkkä pino tai jono
push/pop → LIFO-pino; offer/poll → FIFO-jono
Klassisia käyttötapauksia: kumoa/tee uudelleen, BFS/DFS, liukuva ikkuna ja palindromin tarkistus
Välttäkää vanhoja Stack- ja Queue-luokkia

Aloita maksutta

Opi Java tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 104
Oppitunnit: 374

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Deque-toiminnot: pino ja jono” ilmainen?

Kyllä – oppitunnin ”Deque-toiminnot: pino ja jono” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Java Academy-kurssin, päivitä CoddyKit PROhon. Java Academy-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Deque-toiminnot: pino ja jono”?

Käytä LinkedListia Deque-rakenteena pinon (push/pop) ja jonon (offer/poll) toteuttamiseen. Harjoittelet Java Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Java Academy-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Java Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.

Kuinka kauan ”Deque-toiminnot: pino ja jono”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Java Academy-oppitunnilla?

Kyllä. Jokainen Java Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

LinkedListin sisäinen rakenne
Deque-toiminnot: pino ja jono
LinkedListin ja ArrayListin kompromissit
PriorityQueue järjestettyyn käsittelyyn

← Takaisin: Java Academy