Queue dan Deque

Queue memodelkan antrean (queue), yaitu koleksi yang menerima elemen di satu sisi dan mengeluarkannya dari sisi lain, sehingga elemen yang masuk lebih dulu keluar lebih dulu. Turunannya, Deque, menambah kemampuan bekerja di kedua ujung, sehingga satu struktur yang sama bisa dipakai sebagai antrean maupun tumpukan (stack). Topik ini mempraktikkan keduanya lewat ArrayDeque, lalu menutup dengan PriorityQueue yang mengeluarkan elemen berdasar prioritas, bukan berdasar urutan datang.

Antrean lewat interface Queue#

Tiga metode menjadi inti antrean, yaitu offer untuk memasukkan, peek untuk mengintip elemen terdepan tanpa mengeluarkannya, dan poll untuk mengeluarkan elemen terdepan. Kasus serah-terima loket adalah contohnya, orang yang datang lebih dulu dilayani lebih dulu. Implementasi yang lazim dipakai adalah ArrayDeque, yang menyimpan isinya dalam array melingkar dan menggeser indeks ujungnya, bukan menggeser elemennya.

import java.util.ArrayDeque;
import java.util.Queue;

public class DemoArrayDeque {

    public static void main(String[] args) {
        Queue<String> antreanLoket = new ArrayDeque<>();
        antreanLoket.offer("Ali");
        antreanLoket.offer("Budi");
        antreanLoket.offer("Citra");

        System.out.println("antrean    : " + antreanLoket);
        System.out.println("terdepan   : " + antreanLoket.peek());
        System.out.println("dipanggil  : " + antreanLoket.poll());
        System.out.println("dipanggil  : " + antreanLoket.poll());
        System.out.println("sisa       : " + antreanLoket);
    }
}

antrean    : [Ali, Budi, Citra]
terdepan   : Ali
dipanggil  : Ali
dipanggil  : Budi
sisa       : [Citra]

Keluarannya menegaskan kaidah masuk-pertama-keluar-pertama (first in, first out). peek membaca “Ali” tanpa mengubah isi, sedangkan poll mengeluarkannya sehingga sisa antrean tinggal satu. Selain pasangan offer, peek, dan poll, interface Queue juga punya pasangan add, element, dan remove yang perilakunya berbeda saat antrean kosong atau penuh.

Untuk kode sehari-hari, pasangan santai lebih sering dipilih karena tidak perlu try/catch pada keadaan yang memang wajar, misalnya antrean yang baru selesai dibersihkan.

Deque yang sama, dipakai sebagai tumpukan#

Deque adalah kependekan dari double-ended queue, antrean dua ujung. Selain offerFirst dan offerLast, interface ini menyediakan pasangan push dan pop yang bekerja di satu ujung saja, kaidah masuk-terakhir-keluar-pertama (last in, first out). Struktur dengan kaidah itu disebut tumpukan, dan analoginya adalah tumpukan piring, piring terakhir yang diletakkan justru yang pertama diambil.

import java.util.ArrayDeque;
import java.util.Deque;

public class DemoTumpukan {

    public static void main(String[] args) {
        Deque<String> tumpukanPiring = new ArrayDeque<>();
        tumpukanPiring.push("piring A");
        tumpukanPiring.push("piring B");
        tumpukanPiring.push("piring C");

        System.out.println("tumpukan   : " + tumpukanPiring);
        System.out.println("teratas    : " + tumpukanPiring.peek());
        System.out.println("diambil    : " + tumpukanPiring.pop());
        System.out.println("diambil    : " + tumpukanPiring.pop());
        System.out.println("sisa       : " + tumpukanPiring);
    }
}

tumpukan   : [piring C, piring B, piring A]
teratas    : piring C
diambil    : piring C
diambil    : piring B
sisa       : [piring A]

Tumpukan dicetak dengan elemen teratas di depan, yaitu “piring C” yang masuk terakhir. Metode peek pada Deque mengintip ujung atasnya, dan pop mengeluarkan dari ujung yang sama. Kebutuhan seperti riwayat langkah yang bisa dibatalkan satu per satu (undo) memakai pola persis ini.

ArrayDeque yang dipakai di kedua contoh tidak membatasi jumlah elemennya kecuali memori habis, sehingga tidak perlu menentukan kapasitas di awal. Selain pasangan push dan pop, interface Deque juga menyediakan getFirst, getLast, offerFirst, dan offerLast, sehingga pembacaan maupun penyisipan bisa dipilih ujungnya. Kebebasan ini yang membuat satu objek Deque dapat dipakai bergantian sebagai antrean dan tumpukan tanpa mengganti kelasnya.

PriorityQueue, keluar berdasar prioritas#

PriorityQueue mengabaikan kaidah serah-terima. Elemen tetap masuk lewat offer, tetapi poll mengeluarkan elemen dengan prioritas tertinggi, yang secara default berarti nilai terkecil menurut urutan alaminya. Kasus nyatanya antrean layanan yang mengutamakan tiket dengan tingkat kegentingan tertentu, bukan yang datang lebih dulu.

import java.util.PriorityQueue;
import java.util.Queue;

public class DemoPriorityQueue {

    public static void main(String[] args) {
        Queue<Integer> tugas = new PriorityQueue<>();
        tugas.offer(24);
        tugas.offer(3);
        tugas.offer(100);
        tugas.offer(10);

        System.out.println("isi saat iterasi biasa: " + tugas);
        System.out.println("urutan poll           :");
        while (!tugas.isEmpty()) {
            System.out.println("  ambil " + tugas.poll());
        }
    }
}

isi saat iterasi biasa: [3, 10, 100, 24]
urutan poll           :
  ambil 3
  ambil 10
  ambil 24
  ambil 100

Dua bagian keluaran itu sengaja diletakkan berdekatan karena perbedaannya mengejutkan. Pencetakan biasa memunculkan [3, 10, 100, 24], urutan internal struktur data yang memang tidak terurut penuh, sedangkan poll tetap mengeluarkan 3, 10, 24, lalu 100 sesuai prioritas. Elemen yang disimpan juga harus bisa dibandingkan, yaitu tipe yang menerapkan Comparable atau disertai Comparator, sebagaimana diulas pada topik Pengurutan.

Kesalahan umum#

• Memakai pop atau remove pada antrean yang bisa kosong. Kedua metode melempar exception saat tidak ada elemen. Gunakan poll atau peek yang mengembalikan null, lalu periksa hasilnya.
• Mengira Queue menjamin elemen terurut. Queue biasa menjamin urutan datang, bukan urutan nilai, dan PriorityQueue menjamin urutan keluar, bukan urutan simpan. Tentukan mana yang dimaksud sebelum memilih implementasi.
• Memilih LinkedList sebagai antrean. LinkedList memenuhi kontraknya, tetapi ArrayDeque lebih cepat karena pendiamnya array melingkar. ArrayDeque adalah pilihan bawaan yang lebih tepat untuk antrean maupun tumpukan.
• Menghapus elemen tengah antrean dalam perulangan sambil terus membacanya. Modifikasi semacam ini mengganggu pembaca, dan pada PriorityQueue urutan internalnya ikut tersusun ulang. Selesaikan pembacaan dulu, atau susun antrean baru berdasarkan saringan yang dikehendaki.

Ringkasan#

• Queue menegakkan kaidah masuk-pertama-keluar-pertama lewat offer, peek, dan poll, dengan pasangan add, element, remove sebagai versi tegasnya.
• Deque bekerja di dua ujung sekaligus, sehingga push dan pop menjadikannya tumpukan yang sah menggantikan kelas Stack lama.
• ArrayDeque adalah implementasi default yang tepat untuk keduanya karena array melingkarnya tidak menggeser elemen.
• PriorityQueue mengeluarkan elemen prioritas tertinggi lewat poll, tetapi urutan simpanannya tetap tidak terurut dan hanya terbaca lewat pengeluaran.

Referensi#

• Interface Queue (The Java Tutorials) — Oracle — pasangan metode Queue dan perbedaan perilakunya saat gagal.
• Interface Deque — Oracle Java SE 21 — kontrak antrean dua ujung beserta rekomendasi penggunaannya sebagai tumpukan.
• Class ArrayDeque — Oracle Java SE 21 — dokumentasi ArrayDeque dan posisinya menggantikan Stack serta LinkedList untuk antrean.