Queue

Motivasi

Jika Stack diibaratkan tumpukan piring, maka Queue (Antrean) adalah barisan pelanggan di depan kasir. Pelanggan yang datang lebih dulu akan dilayani lebih dulu, dan yang baru datang harus mengantre di barisan paling belakang.

Prinsip ini dikenal dengan nama FIFO (First-In-First-Out). Struktur ini sangat penting dalam ilmu komputer, misalnya untuk mengatur urutan pencetakan dokumen pada printer atau pembagian waktu prosesor pada sistem operasi.

Berbeda dengan Stack yang hanya memiliki satu pintu (TOP), Queue memiliki dua pintu utama:

1. HEAD (Kepala): Pintu keluar. Tempat elemen diambil atau dilayani.
2. TAIL (Ekor): Pintu masuk. Tempat elemen baru ditambahkan.

Masalah "Penuh Semu"

Mengimplementasikan Queue menggunakan Array statis memiliki satu tantangan besar. Ketika sebuah elemen di depan dihapus (HEAD maju), ruang di depannya menjadi kosong. Namun, penunjuk TAIL akan terus bergerak ke arah kanan hingga mencapai batas maksimal Array.

Kondisi di mana TAIL sudah mentok di ujung Array padahal masih ada ruang kosong di bagian depan disebut Penuh Semu (False Full).

Kasus Penuh Semu (Kapasitas = 5):
[ ] [ ] [ ] [X] [X]
 1   2   3   4   5
             ^   ^
          HEAD  TAIL   -> TAIL mentok, tidak bisa tambah data padahal 1, 2, 3 kosong!

Solusi: Circular Buffer

Solusi terbaik untuk masalah ini adalah teknik Circular Buffer (Antrean Berputar). Kita menganggap Array sebagai sebuah lingkaran. Saat TAIL mencapai batas maksimal dan masih ada ruang kosong di awal Array, TAIL akan memutar kembali ke indeks 1. Hal yang sama juga berlaku untuk HEAD.

Aturan Operasi

Operasi Dasar

Berikut adalah cara kerja penambahan dan penghapusan data pada antrean melingkar.

Menambah Data (Add)

Saat menambah data, kita hanya perlu memajukan TAIL. Jika sudah di ujung, putar balik ke posisi awal.

void Add(Queue *Q, int x) {
    if (!IsFull(Q)) {
        if (IsEmpty(Q)) {
            Q->HEAD = 1;
            Q->TAIL = 1;
        } else {
            if (Q->TAIL == MaxEl) {
                Q->TAIL = 1; // Putar kembali ke awal
            } else {
                Q->TAIL++;
            }
        }
        Q->T[Q->TAIL] = x; 
    }
}

Menghapus Data (Del)

Saat menghapus atau melayani data, kita memajukan penunjuk HEAD.

void Del(Queue *Q, int *hapus) {
    if (!IsEmpty(Q)) {
        *hapus = Q->T[Q->HEAD]; 
        
        if (Q->HEAD == Q->TAIL) {
            // Jika data terakhir diambil, kosongkan antrean
            Q->HEAD = Nil;
            Q->TAIL = Nil;
        } else {
            if (Q->HEAD == MaxEl) {
                Q->HEAD = 1; // Putar kembali ke awal
            } else {
                Q->HEAD++;
            }
        }
    }
}