Kenapa penting

Banyak pekerjaan backend tidak langsung dikerjakan saat request datang, tetapi diantrekan: email konfirmasi pesanan, pembuatan invoice PDF, sinkronisasi stok ke marketplace. Ada juga pekerjaan yang butuh urutan "terakhir masuk, pertama keluar", seperti riwayat undo di editor produk atau memeriksa kurung pada ekspresi. Java menyediakan Queue, Deque, dan PriorityQueue untuk pola-pola ini. Memakai struktur yang tepat membuat kode lebih jelas daripada memanipulasi indeks List secara manual — dan jauh lebih efisien. Konsep antrean juga menjadi fondasi message broker seperti Kafka dan RabbitMQ yang akan kamu pelajari di level Advanced.

Konsep inti

Queue: antrean FIFO

Queue adalah interface untuk antrean FIFO (first in, first out): elemen yang masuk lebih dulu keluar lebih dulu, seperti antrean kasir. Implementasi yang paling sering dipakai adalah ArrayDeque. Seperti di bab List, tipe variabelnya ditulis sebagai interface (Queue<String>), dan <String> adalah tipe isinya — detail generics di M04.

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

public class QueueBasics {
    public static void main(String[] args) {
        Queue<String> orders = new ArrayDeque<>();
        orders.offer("INV-001");
        orders.offer("INV-002");
        orders.offer("INV-003");

        System.out.println("Antrean: " + orders);
        System.out.println("Berikutnya: " + orders.peek());   // lihat tanpa mengambil
        System.out.println("Diproses: " + orders.poll());     // ambil dari depan
        System.out.println("Diproses: " + orders.poll());
        System.out.println("Sisa: " + orders + ", ukuran " + orders.size());

        orders.poll();
        System.out.println("poll() saat kosong: " + orders.poll());
        System.out.println("peek() saat kosong: " + orders.peek());
    }
}

Output:

Antrean: [INV-001, INV-002, INV-003]
Berikutnya: INV-001
Diproses: INV-001
Diproses: INV-002
Sisa: [INV-003], ukuran 1
poll() saat kosong: null
peek() saat kosong: null

Queue punya dua "keluarga" method untuk operasi yang sama. Bedanya ada pada perilaku saat antrean kosong atau penuh:

Operasi	Mengembalikan nilai khusus	Melempar exception
Tambah di belakang	offer(x) → false	add(x)
Ambil dari depan	poll() → null	remove()
Lihat yang depan	peek() → null	element()

remove() pada antrean kosong menghentikan program dengan NoSuchElementException. Untuk antrean berkapasitas tetap (misalnya ArrayBlockingQueue), add melempar IllegalStateException: Queue full, sedangkan offer mengembalikan false. Bagi worker yang memproses antrean, kosong adalah keadaan normal — jadi pakai offer/poll/peek. Karena null dipakai sebagai tanda "kosong", ArrayDeque menolak elemen null (NullPointerException).

Deque dan ArrayDeque: dua ujung, juga stack

Deque (double-ended queue, dibaca "deck") bisa ditambah dan diambil di kedua ujung. Karena itu satu ArrayDeque bisa dipakai sebagai antrean FIFO maupun stack LIFO (last in, first out) dengan push, pop, dan peek. Deque juga termasuk sequenced collection (Java 21), jadi punya getFirst, getLast, dan reversed seperti List.

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

public class UndoHistory {
    public static void main(String[] args) {
        Deque<String> undo = new ArrayDeque<>();   // dipakai sebagai stack (LIFO)
        undo.push("ubah judul");
        undo.push("ubah harga");
        undo.push("hapus gambar");

        System.out.println("Stack: " + undo);
        System.out.println("Aksi terakhir: " + undo.peek());
        System.out.println("Undo: " + undo.pop());
        System.out.println("Undo: " + undo.pop());
        System.out.println("Sisa: " + undo);

        Deque<Integer> both = new ArrayDeque<>();  // dua ujung sekaligus
        both.addLast(2);
        both.addLast(3);
        both.addFirst(1);
        System.out.println(both + " pertama=" + both.getFirst() + " terakhir=" + both.getLast());
        System.out.println("terbalik: " + both.reversed());
        System.out.println(both.pollLast() + " " + both.pollFirst() + " → " + both);
    }
}

Output:

Stack: [hapus gambar, ubah harga, ubah judul]
Aksi terakhir: hapus gambar
Undo: hapus gambar
Undo: ubah harga
Sisa: [ubah judul]
[1, 2, 3] pertama=1 terakhir=3
terbalik: [3, 2, 1]
3 1 → [2]

push menaruh elemen di depan, sehingga stack tercetak dari yang terbaru. Java masih punya class Stack dari versi 1.0, tetapi jangan dipakai di kode baru: ia turunan Vector (setiap method disinkronkan sehingga lebih lambat) dan membuka akses lewat indeks yang merusak sifat LIFO. Dokumentasi Java sendiri menyarankan Deque.

Stack juga dipakai untuk memeriksa kurung: setiap kurung buka di-push, setiap kurung tutup harus cocok dengan hasil pop. Teks seimbang bila stack kosong di akhir. Kamu akan mengimplementasikannya di tantangan latihan bab ini.

PriorityQueue: yang terpenting keluar lebih dulu

PriorityQueue tidak FIFO. poll() selalu mengeluarkan elemen terkecil menurut urutan alaminya — angka terkecil, teks yang paling awal secara alfabet. Strukturnya adalah min-heap: elemen terkecil dijamin ada di depan, tetapi sisanya hanya "cukup teratur".

import java.util.PriorityQueue;

public class PriorityDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> deadlines = new PriorityQueue<>();
        deadlines.offer(30);
        deadlines.offer(5);
        deadlines.offer(20);
        deadlines.offer(1);
        deadlines.offer(15);

        System.out.println("Dicetak langsung: " + deadlines);
        System.out.println("Terkecil: " + deadlines.peek());

        StringBuilder order = new StringBuilder();
        while (!deadlines.isEmpty()) {
            order.append(deadlines.poll()).append(' ');
        }
        System.out.println("Urutan poll(): " + order);
    }
}

Output:

Dicetak langsung: [1, 5, 20, 30, 15]
Terkecil: 1
Urutan poll(): 1 5 15 20 30

Perhatikan baris pertama: mencetak atau mengiterasi PriorityQueue tidak memberi urutan terurut. Hanya peek() dan poll() yang dijamin. Untuk object buatanmu sendiri, "terkecil" ditentukan oleh method compareTo bila class itu mengimplementasikan Comparable (seperti contoh backend di bawah). Cara lain — memberi Comparator — dibahas di bab Iterasi & Sorting.

Kompleksitas sekilas

Operasi	ArrayDeque	PriorityQueue
Tambah (offer/push)	sangat cepat (O(1))	O(log n)
Ambil depan (poll/pop)	sangat cepat (O(1))	O(log n)
Lihat depan (peek)	O(1)	O(1)
Cari elemen tertentu (contains)	O(n)	O(n)

Notasi O(...) dibahas tuntas di bab Big-O & Memilih Struktur Data. Untuk sekarang, cukup ingat: operasi di ujung antrean murah, sedangkan mencari elemen di tengah antrean perlu menelusuri semuanya.

Deque berkapasitas: "N event terakhir"

Kadang kamu hanya perlu menyimpan beberapa data terbaru — 3 event terakhir pengguna untuk log audit, atau 100 request terakhir untuk menghitung rata-rata latency. Deque cocok untuk sliding window ini: tambah di belakang, buang yang paling lama dari depan.

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

public class RecentEvents {
    private static final int CAPACITY = 3;
    private final Deque<String> events = new ArrayDeque<>();

    void record(String event) {
        if (events.size() == CAPACITY) {
            events.pollFirst();          // buang event paling lama
        }
        events.addLast(event);
    }

    public static void main(String[] args) {
        RecentEvents log = new RecentEvents();
        String[] incoming = {"login", "lihat produk", "tambah keranjang", "checkout", "bayar"};
        for (String event : incoming) {
            log.record(event);
            System.out.println(event + " → " + log.events);
        }
    }
}

Output:

login → [login]
lihat produk → [login, lihat produk]
tambah keranjang → [login, lihat produk, tambah keranjang]
checkout → [lihat produk, tambah keranjang, checkout]
bayar → [tambah keranjang, checkout, bayar]

Contoh di dunia backend

Layanan notifikasi menampung email di outbox lalu mengirimnya bertahap, misalnya maksimal tiga email per putaran agar tidak terkena batas kirim penyedia email. Email yang mendesak — kode reset password, kode verifikasi — harus keluar lebih dulu daripada newsletter. Record EmailJob mengimplementasikan Comparable sehingga PriorityQueue tahu email mana yang "terkecil" (paling mendesak):

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

record EmailJob(String to, String subject, int urgency) implements Comparable<EmailJob> {
    // urgency kecil = lebih mendesak (1 = reset password, 3 = newsletter)
    @Override
    public int compareTo(EmailJob other) {
        return Integer.compare(urgency, other.urgency);
    }
}

public class EmailQueue {
    public static void main(String[] args) {
        Queue<EmailJob> outbox = new PriorityQueue<>();
        outbox.offer(new EmailJob("sari@contoh.com", "Promo akhir pekan", 3));
        outbox.offer(new EmailJob("budi@contoh.com", "Kode reset password", 1));
        outbox.offer(new EmailJob("andi@contoh.com", "Pesanan INV-7 dikirim", 2));
        outbox.offer(new EmailJob("rina@contoh.com", "Kode verifikasi", 1));

        int sent = 0;
        while (!outbox.isEmpty() && sent < 3) {       // kirim maksimal 3 per putaran
            EmailJob job = outbox.poll();
            System.out.println("Kirim [" + job.urgency() + "] " + job.subject() + " → " + job.to());
            sent++;
        }
        System.out.println("Menunggu putaran berikutnya: " + outbox.size() + " email");
    }
}

Output:

Kirim [1] Kode reset password → budi@contoh.com
Kirim [1] Kode verifikasi → rina@contoh.com
Kirim [2] Pesanan INV-7 dikirim → andi@contoh.com
Menunggu putaran berikutnya: 1 email

Integer.compare dipakai alih-alih pengurangan urgency - other.urgency; alasannya dibahas di bab Iterasi & Sorting. Ada satu kelemahan penting: dua email dengan urgensi sama (1) dianggap setara, dan PriorityQueue tidak menjamin urutan di antara keduanya — kebetulan di sini keluar sesuai urutan masuk, tetapi itu tidak dijanjikan. Di sistem nyata yang adil, pekerjaan berprioritas sama harus diproses sesuai urutan datangnya. Itulah inti latihan JobScheduler di bab ini. Di aplikasi production yang berjalan di banyak server, antrean seperti ini dipindahkan ke message broker (RabbitMQ, Kafka) agar tidak hilang saat aplikasi restart — topik level Advanced.

Pertanyaan interview

1. Apa beda Queue, Deque, dan PriorityQueue?

Queue adalah antrean FIFO: tambah di belakang, ambil dari depan. Deque bisa tambah dan ambil di kedua ujung, sehingga bisa dipakai sebagai queue maupun stack. PriorityQueue mengeluarkan elemen berdasarkan prioritas (urutan natural atau comparator), bukan urutan masuk, dan diimplementasikan sebagai heap.

2. Bagaimana mengimplementasikan stack di Java modern, dan kenapa tidak memakai class Stack?

Pakai Deque<T> stack = new ArrayDeque<>() dengan push, pop, dan peek. Class Stack adalah warisan Java 1.0 yang mewarisi Vector: setiap method disinkronkan (overhead yang biasanya tidak perlu) dan elemennya bisa diakses lewat indeks, sehingga sifat LIFO tidak terjaga.

3. Berapa kompleksitas operasi PriorityQueue, dan apakah iterasinya terurut?

offer dan poll O(log n), peek O(1), contains dan remove(Object) O(n). Iterasi dan toString() mengikuti susunan heap internal, jadi tidak terurut; untuk urutan penuh, ambil elemen satu per satu dengan poll().

Jebakan umum

• Memakai remove()/element() pada antrean yang bisa kosong → NoSuchElementException. Pakai poll()/peek() dan periksa null.
• Mengira PriorityQueue terurut saat diiterasi atau dicetak. Hanya poll()/peek() yang mengikuti prioritas.
• Mengandalkan urutan elemen berprioritas sama di PriorityQueue. Tambahkan kriteria pembeda, misalnya nomor urut kedatangan.
• Memasukkan null ke ArrayDeque/PriorityQueue → NullPointerException.
• Memakai LinkedList atau Stack untuk antrean/stack baru. ArrayDeque lebih cepat dan hemat memori.
• Antrean di memori dianggap tahan banting. Isinya hilang saat aplikasi restart; pekerjaan penting perlu antrean persisten (database atau message broker).

Ringkasan

• Queue = FIFO; pakai offer/poll/peek yang mengembalikan false/null alih-alih melempar exception.
• ArrayDeque adalah pilihan default untuk queue maupun stack (push/pop/peek); hindari class Stack.
• PriorityQueue mengeluarkan elemen terkecil lebih dulu (min-heap); iterasinya tidak terurut.
• Urutan object di PriorityQueue ditentukan compareTo (Comparable); prioritas sama tidak dijamin FIFO.
• Deque cocok untuk sliding window "N data terakhir": tambah di belakang, buang dari depan.

Bacaan lanjutan

• dev.java — Storing Elements in Stacks and Queues
• Java SE 25 API — Deque
• Java SE 25 API — PriorityQueue