Deque Interface

Queue membatasi akses pada satu kepala dan satu ekor, tetapi banyak masalah nyata justru butuh pintu di kedua ujung sekaligus: riwayat undo yang menampung aksi terbaru di depan dan membuang aksi terlama dari belakang, deck kartu yang dibagikan dari atas dan dikembalikan ke bawah, atau antrean VIP yang boleh menyelip di depan. Interface Deque (double-ended queue, dibaca “deck”) adalah perluasan Queue yang membuka kedua ujung tersebut secara setara: penyisipan, pengambilan, dan pembacaan tersedia untuk kepala maupun ekor. Implementasi andalannya adalah ArrayDeque — struktur berbasis array melingkar yang menjadi rekomendasi resmi Java baik untuk antrean maupun stack. Pada Chapter ini kita berlatih operasi dua ujung, memakai Deque sebagai stack, lalu menimbang tiga kandidat implementasi.

Kontrak Dua Ujung #

Seluruh operasi Queue yang kita bahas sebelumnya hadir kembali dalam dua versi: offerFirst/offerLast, pollFirst/pollLast, peekFirst/peekLast — plus pasangan bentuk exception addFirst/addLast, removeFirst/removeLast, getFirst/getLast. Sebagai tambahan, Deque menyediakan kosakata khusus stack: push(e) sama dengan addFirst(e), pop() sama dengan removeFirst(), dan peek() sama dengan peekFirst(). Dengan satu struktur yang sama, kita bisa menyatakan niat “antrean” maupun niat “tumpukan” langsung dari pilihan method-nya.

Sebagai perluasan Queue, seluruh method Queue juga tetap berlaku pada objek Deque: offer(e) menyisip di ekor, poll() mengambil dari kepala, dan peek() membaca kepala — perilaku FIFO standar tanpa embel-embel First/Last.

Antrean Dua Arah dalam Praktik #

Program berikut mengisi ArrayDeque dari kedua ujung, membaca dan mengambil dari kedua ujung, lalu memperlihatkan bahwa method Queue biasa tetap bekerja pada objek yang sama:

import java.util.*;

public class AntreanDuaUjung {
    public static void main(String[] args) {
        Deque<Integer> antrean = new ArrayDeque<>();

        // Isi dari kedua ujung: offerLast ke ekor, offerFirst ke kepala.
        antrean.offerLast(10);
        antrean.offerLast(20);
        antrean.offerFirst(5);
        antrean.offerLast(30);
        System.out.println("Isi          : " + antrean);

        // Membaca kedua ujung tanpa menghapus.
        System.out.println("peekFirst()  : " + antrean.peekFirst());
        System.out.println("peekLast()   : " + antrean.peekLast());

        // Mengambil dari kedua ujung.
        System.out.println("pollFirst()  : " + antrean.pollFirst());
        System.out.println("pollLast()   : " + antrean.pollLast());
        System.out.println("Sisa         : " + antrean);

        // Variabel bertipe Queue hanya melihat sisi FIFO (ekor masuk, kepala keluar).
        antrean.offer(99);
        System.out.println("Setelah offer(99): " + antrean);
        System.out.println("poll()       : " + antrean.poll());
        System.out.println("Sisa         : " + antrean);
    }
}

Output yang Dihasilkan:

Isi          : [5, 10, 20, 30]
peekFirst()  : 5
peekLast()   : 30
pollFirst()  : 5
pollLast()   : 30
Sisa         : [10, 20]
Setelah offer(99): [10, 20, 99]
poll()       : 10
Sisa         : [20, 99]

Mari kita bedah baris-baris pentingnya:

1. Baris 8-11 (offerLast dan offerFirst): 10 dan 20 masuk lewat ekor, lalu 5 menyelip lewat kepala sehingga cetakan menjadi [5, 10, 20, 30] — urutan dari kepala ke ekor.
2. Baris 14-15 (peekFirst / peekLast): membaca kedua ujung tanpa menghapus apa pun.
3. Baris 18-19 (pollFirst / pollLast): 5 keluar dari depan dan 30 keluar dari belakang pada baris yang berdekatan — dua ujung benar-benar setara.
4. Baris 23-26 (offer dan poll tanpa akhiran): method Queue warisan tetap hidup di Deque: offer(99) menempel di ekor, poll() mengambil 10 dari kepala. Satu objek, dua dialek operasi.

Deque sebagai Stack #

Stack bekerja dengan aturan LIFO (last-in, first-out): elemen terakhir yang masuk menjadi elemen pertama yang keluar. Kosakata push/pop/peek pada Deque menerapkan aturan tersebut seluruhnya di ujung kepala. Program berikut menumpuk piring dan mengambilnya kembali:

import java.util.*;

public class TumpukanPiring {
    public static void main(String[] args) {
        // ArrayDeque sebagai stack (LIFO): push/pop/peek bekerja di kepala.
        Deque<String> piring = new ArrayDeque<>();
        piring.push("piring merah");
        piring.push("piring biru");
        piring.push("piring putih");
        System.out.println("Tumpukan    : " + piring);

        // peek = peekFirst: melihat piring paling atas tanpa mengambil.
        System.out.println("peek()      : " + piring.peek());

        // pop = removeFirst: mengambil piring paling atas (yang terakhir masuk).
        System.out.println("pop()       : " + piring.pop());
        System.out.println("pop()       : " + piring.pop());
        System.out.println("Sisa        : " + piring);
    }
}

Output yang Dihasilkan:

Tumpukan    : [piring putih, piring biru, piring merah]
peek()      : piring putih
pop()       : piring putih
pop()       : piring biru
Sisa        : [piring merah]

Poin bedahnya:

1. Baris 7-10 (push tiga kali): setiap push menaruh piring baru di kepala deque, terlihat dari cetakan [piring putih, piring biru, piring merah] — piring terakhir yang didorong berada paling depan.
2. Baris 13 (peek()): mengembalikan piring putih, piring paling atas, tanpa membongkar tumpukan.
3. Baris 16-17 (pop() dua kali): mengambil piring putih lalu piring biru — persis kebalikan urutan penyimpanan, itulah LIFO.

Memilih Implementasi Deque #

ArrayDeque menang telak untuk kebutuhan antrean dan stack murni: array melingkar dan penunjuk kepala/ekor membuat operasi ujung berlangsung tanpa penggeseran elemen, dan tidak ada biaya memori per node. LinkedList hanya relevan bila struktur yang sama perlu juga dipakai sebagai List berindeks. Kedalaman perbandingan biaya antar-implementasi dibahas pada Chapter Collection Performance.

Dua ujung Deque mengeluarkan elemen berdasarkan posisi. Ada satu bentuk antrean terakhir yang mengeluarkan elemen berdasarkan kepentingan: tugas paling mendesak keluar lebih dulu walau masuk paling akhir. Chapter penutup cabang ini membahas PriorityQueue dan struktur heap di baliknya.

Referensi #

• Java API Specification: java.util.Deque
• Java API Specification: java.util.ArrayDeque
• Dev.java: The Java Collections Framework

import java.util.*;

public class AntreanDuaUjung {
    public static void main(String[] args) {
        Deque<Integer> antrean = new ArrayDeque<>();

        // Isi dari kedua ujung: offerLast ke ekor, offerFirst ke kepala.
        antrean.offerLast(10);
        antrean.offerLast(20);
        antrean.offerFirst(5);
        antrean.offerLast(30);
        System.out.println("Isi          : " + antrean);

        // Membaca kedua ujung tanpa menghapus.
        System.out.println("peekFirst()  : " + antrean.peekFirst());
        System.out.println("peekLast()   : " + antrean.peekLast());

        // Mengambil dari kedua ujung.
        System.out.println("pollFirst()  : " + antrean.pollFirst());
        System.out.println("pollLast()   : " + antrean.pollLast());
        System.out.println("Sisa         : " + antrean);

        // Variabel bertipe Queue hanya melihat sisi FIFO (ekor masuk, kepala keluar).
        antrean.offer(99);
        System.out.println("Setelah offer(99): " + antrean);
        System.out.println("poll()       : " + antrean.poll());
        System.out.println("Sisa         : " + antrean);
    }
}

import java.util.*;

public class TumpukanPiring {
    public static void main(String[] args) {
        // ArrayDeque sebagai stack (LIFO): push/pop/peek bekerja di kepala.
        Deque<String> piring = new ArrayDeque<>();
        piring.push("piring merah");
        piring.push("piring biru");
        piring.push("piring putih");
        System.out.println("Tumpukan    : " + piring);

        // peek = peekFirst: melihat piring paling atas tanpa mengambil.
        System.out.println("peek()      : " + piring.peek());

        // pop = removeFirst: mengambil piring paling atas (yang terakhir masuk).
        System.out.println("pop()       : " + piring.pop());
        System.out.println("pop()       : " + piring.pop());
        System.out.println("Sisa        : " + piring);
    }
}