Java Academy · Pelajaran

Operasi Deque: Timbunan dan Baris Gilir

Gunakan LinkedList sebagai Deque untuk melaksanakan tingkah laku timbunan (push/pop) dan baris gilir (offer/poll).

Pelajaran 2 daripada 413 langkah

Operasi Deque: Timbunan dan Baris Gilir ialah pelajaran Java Academy percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Java Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Java Academy merangkumi sejumlah 4 pelajaran.

Baris Dua Hujung: Baris Gilir Dua Hujung

Baris gilir dua hujung membolehkan penyisipan dan penyingkiran pada kedua-dua hujung. Antara muka Deque Java dilaksanakan oleh LinkedList dan 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 berbanding LinkedList sebagai Baris Dua Hujung

ArrayDeque biasanya lebih disyorkan berbanding LinkedList sebagai baris gilir dua hujung:

Tiada overhed nod bagi setiap elemen
Lokasi cache yang lebih baik
Sedikit lebih pantas untuk operasi tindanan atau baris gilir

Pilih LinkedList hanya apabila anda juga memerlukan antara muka List.

Operasi Tindanan dengan Baris Dua Hujung

Gunakan push (addFirst) dan pop (removeFirst) untuk mensimulasikan tindanan LIFO. Elakkan kelas Stack lama — ia disegerakkan dan sudah usang.

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

Operasi Baris Gilir dengan Baris Dua Hujung

Gunakan offer (addLast) dan poll (removeFirst) untuk mensimulasikan baris gilir FIFO. offer mengembalikan palsu apabila gagal; add mencetuskan pengecualian.

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

Jadual Rujukan Kaedah Baris Dua Hujung

Baris gilir dua hujung menyediakan dua keluarga kaedah — satu yang mencetuskan pengecualian, satu lagi yang mengembalikan nilai khas:

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

Utamakan keluarga offer/poll/peek untuk mengelakkan pengecualian pada baris gilir dua hujung yang kosong.

Contoh Sebenar: Buat Asal/Buat Semula dengan Dua Tindanan

Kes penggunaan klasik baris gilir dua hujung: sejarah buat asal ialah tindanan. Buat semula ialah tindanan lain.

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'

Semakan Palindrom dengan Baris Dua Hujung

Baris gilir dua hujung menjadikan semakan palindrom elegan — bandingkan aksara dari kedua-dua hujung secara serentak.

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 dengan Baris Gilir

Carian Lebar-Dahulu menggunakan baris gilir. ArrayDeque ialah pilihan standard untuk BFS dalam pengaturcaraan kompetitif dan penelusuran graf.

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 dengan Tindanan

Carian Kedalaman-Dahulu menggunakan tindanan. Sekali lagi, utamakan ArrayDeque berbanding kelas Stack lama.

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

Baris Dua Hujung Terhad dengan Semakan Saiz

ArrayDeque berkembang secara dinamik, tetapi anda boleh menguatkuasakan kapasiti secara manual untuk mensimulasikan penimbal terhad:

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]

Nota Prestasi

ArrayDeque menggunakan tatasusunan bulat yang digandakan apabila penuh. Kos beramortisasi bagi semua operasi ialah O(1). Prestasinya mengatasi LinkedList dalam kebanyakan penanda aras kerana kecekapan cache. Jangan sekali-kali menyegerakkan secara manual — gunakan ConcurrentLinkedDeque atau baris gilir penyekat untuk keserentakan.

Semakan Pantas

Kelas manakah yang patut diutamakan berbanding Stack lama untuk operasi LIFO?

Jawab dalam pelajaran interaktif

Imbas Kembali: Operasi Baris Dua Hujung

Perkara penting:

Baris gilir dua hujung membenarkan penyisipan dan penyingkiran O(1) pada kedua-dua hujung
ArrayDeque lebih disyorkan berbanding LinkedList untuk penggunaan tindanan atau baris gilir semata-mata
push/pop → tindanan LIFO; offer/poll → baris gilir FIFO
Kegunaan klasik: buat asal/buat semula, BFS/DFS, tetingkap gelangsar dan semakan palindrom
Elakkan kelas Stack dan Queue lama

Percuma untuk bermula

Pelajari Java dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 104
Pelajaran: 374

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Operasi Deque: Timbunan dan Baris Gilir” percuma?

Ya — teks penuh “Operasi Deque: Timbunan dan Baris Gilir” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Java Academy, tingkat taraf kepada CoddyKit PRO. Kursus Java Academy merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Operasi Deque: Timbunan dan Baris Gilir”?

Gunakan LinkedList sebagai Deque untuk melaksanakan tingkah laku timbunan (push/pop) dan baris gilir (offer/poll). Anda berlatih Java Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan Java Academy?

Tiada pengalaman terdahulu diperlukan. Pembelajaran Java Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.

Berapa lamakah pelajaran “Operasi Deque: Timbunan dan Baris Gilir” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran Java Academy ini?

Ya. Setiap pelajaran Java Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

Bahagian Dalaman LinkedList
Operasi Deque: Timbunan dan Baris Gilir
Pertukaran antara LinkedList dan ArrayList
PriorityQueue untuk Pemprosesan Teratur

← Kembali ke Java Academy