Antrian

Antrian mengubah arah dari stack, yaitu elemen yang pertama masuk adalah yang pertama keluar. Prinsipnya disebut FIFO (first in, first out) dan meniru antrean tiket loket, orang yang datang lebih dulu dilayani lebih dulu. Topik ini membangun antrian dari array naif yang mahal, memperbaikinya menjadi buffer melingkar (circular buffer) yang berputar dan hemat memori, lalu menutup dengan versi bawaan Java. Implementasi akhirnya menghasilkan enqueue dan dequeue yang keduanya $O(1)$.

Prinsip FIFO#

Antrian (queue) menerima dan mengeluarkan elemen dari ujung yang berbeda. Elemen baru masuk di belakang lewat operasi enqueue, pengeluaran terjadi di depan lewat operasi dequeue, sedangkan peek membaca elemen terdepan tanpa menghapusnya. Karena tidak ada yang bisa melompati barisan, urutan keluar selalu sama dengan urutan masuk. Ketiga operasi dirancang berbiaya $O(1)$, dan sebagian besar topik ini justru membahas bagaimana mencapainya pada array.

Pemakaiannya tersebar luas pada sistem perangkat lunak. Antrean cetak, antrean pesan antarlayanan, penjadwalan tugas, dan penelusuran berbasis breadth-first search semuanya menuntut urutan kedatangan yang dihormati. Algoritma BFS memakai antrian sebagai jantungnya, sehingga antrian yang benar menjadi bekal untuk seluruh soal BFS di kemudian hari.

Antrian naif berbasis array#

Cara paling langsung menyimpan antrian pada array adalah mengisi dari kiri ke kanan, enqueue dengan append, dan dequeue dengan pop dari indeks 0. Versi naif ini bekerja, tetapi biayanya timpang. append berbiaya amortisasi $O(1)$, sedangkan pop(0) harus menggeser seluruh elemen yang tersisa satu tempat ke kiri agar indeks 0 kembali terisi, sehingga dequeue berbiaya $O(n)$. Pada antrian seratus ribu elemen, satu dequeue memindahkan seratus ribu nilai.

data = [10, 20, 30, 40]
print("sebelum pop(0):", data)
keluar = data.pop(0)          # semua elemen bergeser ke kiri
print("yang keluar   :", keluar)
print("sesudah pop(0):", data)

sebelum pop(0): [10, 20, 30, 40]
yang keluar   : 10
sesudah pop(0): [20, 30, 40]

Empat elemen terasa ringan, tetapi pergeserannya tumbuh linear terhadap panjang antrian. Dokumentasi Python pun memperingatkan bahwa memakai list sebagai antrian lewat pop(0) tidak efisien. Pertanyaannya menjadi bagaimana menyimpan antrian pada array tanpa menggeser apa pun, dan jawabannya adalah membiarkan ujung depan ikut berpindah.

Buffer melingkar#

Buffer melingkar menyimpan antrian pada array tetap, dengan ujung akhir array yang dianggap tersambung kembali ke ujung awal. Dua indeks mengatur pergerakannya, yaitu head yang menunjuk posisi dequeue berikutnya dan tail yang menunjuk slot kosong tempat enqueue berikutnya. Setelah indeks melewati slot terakhir, indeks kembali ke 0, perilaku yang disebut wrap-around. Pergeseran lenyap karena ujung depan antrian yang berpindah, bukan elemen-elemennya.

Diagram berikut memperlihatkan buffer berkapasitas delapan yang menampung empat elemen. head berada di slot 3 karena C adalah elemen berikutnya yang keluar, sedangkan tail berada di slot 7 sebagai slot kosong berikutnya. Panah putus-putus menunjukkan wrap-around, yaitu slot 0 menjadi tetangga slot 7 sehingga ruang yang sudah ditinggalkan dequeue dapat dipakai lagi.

Posisi tail tidak perlu disimpan terpisah karena dapat dihitung dari head dan jumlah elemen, yaitu $\text{tail} = (\text{head} + \text{jumlah}) \bmod \text{kapasitas}$. Penambahan dan pengurangan pada dua indeks inilah seluruh biaya enqueue dan dequeue, keduanya $O(1)$.

Implementasi dari nol#

Kelas berikut menyelesaikan masalah penuh-versus-kosong dengan penghitung jumlah. Enqueue menghitung tail dari head dan jumlah, lalu menulis nilai setelah memeriksa penuh, sedangkan dequeue membaca head, mengosongkan slotnya, dan menggeser head dengan modulo. Metode __repr__ menelusuri elemen dari head ke arah tail sehingga isi antrian tercetak berurutan meskipun posisi fisiknya di array tidak rapi.

"""Antrian FIFO dengan buffer melingkar (circular buffer) dari nol."""

class AntrianMelingkar:
    def __init__(self, kapasitas):
        self.data = [None] * kapasitas
        self.kapasitas = kapasitas
        self.head = 0       # posisi pengambilan (depan antrian)
        self.jumlah = 0     # banyak elemen yang sedang tersimpan

    def kosong(self):
        return self.jumlah == 0

    def penuh(self):
        return self.jumlah == self.kapasitas

    def enqueue(self, nilai):
        if self.penuh():
            raise IndexError("antrian penuh")
        tail = (self.head + self.jumlah) % self.kapasitas   # wrap-around
        self.data[tail] = nilai
        self.jumlah += 1

    def dequeue(self):
        if self.kosong():
            raise IndexError("antrian kosong")
        nilai = self.data[self.head]
        self.data[self.head] = None
        self.head = (self.head + 1) % self.kapasitas        # head ikut berputar
        self.jumlah -= 1
        return nilai

    def __repr__(self):
        isi = [str(self.data[(self.head + i) % self.kapasitas]) for i in range(self.jumlah)]
        return "antrian: [" + ", ".join(isi) + "]"


if __name__ == "__main__":
    antrian = AntrianMelingkar(4)
    antrian.enqueue("A")
    antrian.enqueue("B")
    antrian.enqueue("C")
    print(antrian)
    print("dequeue   :", antrian.dequeue())
    antrian.enqueue("D")
    antrian.enqueue("E")          # tail berputar ke indeks 0
    print(antrian)
    print("dequeue   :", antrian.dequeue())
    print("dequeue   :", antrian.dequeue())
    antrian.enqueue("F")
    antrian.enqueue("G")          # buffer kembali penuh
    print(antrian)
    try:
        antrian.enqueue("H")      # tidak muat lagi
    except IndexError as e:
        print("enqueue H ->", e)

antrian: [A, B, C]
dequeue   : A
antrian: [B, C, D, E]
dequeue   : B
dequeue   : C
antrian: [D, E, F, G]
enqueue H -> antrian penuh

Urutan operasinya sengaja dipilih agar wrap-around terlihat. Setelah A dikeluarkan, E ditambahkan dan tail berputar ke indeks 0, yaitu slot bekas A, sehingga buffer memakai kembali ruang yang sudah ditinggalkan. Pada kapasitas empat, E masuk tanpa menggeser B, C, dan D satu pun. Kondisi penuh ikut teruji, enqueue berikutnya memunculkan pesan error antrian penuh alih-alih menimpa data yang belum dikeluarkan.

Antrian bawaan Java: ArrayDeque#

Setelah implementasi dari nol menuntaskan mekanismenya, versi bawaan siap dipakai untuk pekerjaan nyata. Kelas java.util.ArrayDeque adalah antrian berbasis buffer melingkar yang tumbuh otomatis, persis melanjutkan ide yang baru saja dibangun. Bila dideklarasikan melalui tipe Queue, metode offer melakukan enqueue, poll melakukan dequeue, dan peek membaca terdepan, semuanya berbiaya amortisasi $O(1)$.

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

public class DemoAntrian {
    public static void main(String[] args) {
        Queue<String> antrian = new ArrayDeque<>();
        antrian.offer("A");            // masuk di belakang (tail)
        antrian.offer("B");
        antrian.offer("C");
        System.out.println("depan   : " + antrian.peek());   // lihat tanpa menghapus
        System.out.println("keluar  : " + antrian.poll());   // keluar dari depan (head)
        System.out.println("keluar  : " + antrian.poll());
        System.out.println("sisa    : " + antrian);
        System.out.println("kosong? : " + antrian.isEmpty());
    }
}

depan   : A
keluar  : A
keluar  : B
sisa    : [C]
kosong? : false

Keluarannya mengikuti FIFO ketat, A yang masuk lebih dulu keluar lebih dulu meskipun program tidak pernah mengurutkan apa pun. Dokumentasi Java menyatakan ArrayDeque biasanya lebih cepat daripada java.util.LinkedList untuk peran antrian karena tidak mengalokasikan node baru untuk setiap elemen, sehingga kelas ini menjadi pilihan bawaan yang aman.

Kesalahan umum#

1. Menganggap head == tail selalu berarti kosong. Pada buffer tanpa penghitung, keadaan itu juga terjadi saat penuh, sehingga enqueue berikutnya menimpa elemen yang belum dikeluarkan. Simpan jumlah elemen atau sisakan satu slot kosong.
2. Memakai pop(0) untuk antrian besar. Biaya per dequeue menjadi $O(n)$ dan total pekerjaannya mencapai $O(n^2)$. Untuk antrian yang keluar-masuk terus, gunakan buffer melingkar atau collections.deque.
3. Lupa modulo saat menggeser indeks. Penggeseran harus ditulis (head + 1) % kapasitas, bukan sekadar head + 1, agar indeks kembali ke 0 dan tidak keluar dari array.
4. Mencetak isi array mentah dari indeks 0. Setelah wrap-around terjadi, urutan fisik array bukan lagi urutan antrian. Telusuri dari head sebanyak jumlah elemen, seperti yang dilakukan __repr__.

Ringkasan#

• Antrian bekerja FIFO, enqueue di tail dan dequeue di head, dengan target biaya $O(1)$ untuk keduanya.
• Antrian naif berbasis list dengan pop(0) berbiaya $O(n)$ per dequeue karena seluruh elemen ikut bergeser.
• Buffer melingkar membiarkan head dan tail berputar dengan modulo kapasitas, dan penghitung jumlah membedakan keadaan penuh dari kosong.
• ArrayDeque pada Java adalah versi bawaan dari buffer melingkar yang sama dan siap dipakai untuk pekerjaan nyata.

Referensi#

• Circular buffer — Wikipedia — definisi head, tail, wrap-around, dan penanganan penuh-versus-kosong.
• Queue (abstract data type) — Wikipedia — definisi operasi antrian beserta contoh pemakaiannya.
• Using lists as stacks and queues — Python Software Foundation — peringatan resmi Python tentang pop(0) yang tidak efisien pada list.