Queue adalah struktur data FIFO (First In, First Out): elemen pertama yang dimasukkan adalah elemen pertama yang dikeluarkan—seperti antrian di kasir. Queue dipakai dalam banyak algoritma: BFS (Breadth-First Search), penjadwalan task, buffering data streaming, dan message passing antar thread. Pada chapter ini kita akan mengimplementasikan queue dengan dua pendekatan: array sirkular (kapasitas tetap, wrap-around) dan linked list (dinamis). Setiap implementasi punya tradeoff yang akan kita bahas.

Operasi Dasar Queue #

Empat operasi standar queue:

  • Enqueue: tambahkan elemen di belakang queue.
  • Dequeue: ambil elemen dari depan queue (dan hapus).
  • Peek/Front: baca elemen depan tanpa menghapus.
  • IsEmpty / IsFull: cek kondisi queue.

Implementasi naive queue pakai array geser (geser seluruh elemen ke depan setiap dequeue) berbiaya O(n) per dequeue. Implementasi cerdas pakai array sirkular: dua indeks depan dan belakang yang berputar di dalam array, sehingga enqueue dan dequeue keduanya O(1).

Queue Berbasis Array Sirkular #

Pada queue sirkular, depan dan belakang berputar di dalam array lewat operasi modulo. Bila belakang mencapai akhir array, ia kembali ke indeks 0. Trik ini menghindari penggeseran elemen.

c 
#include <stdio.h>
#include <stdlib.h>

#define KAPASITAS 8

typedef struct {
    int data[KAPASITAS];
    int depan, belakang;
    size_t ukuran;
} queue_array;

void qa_init(queue_array *q) {
    q->depan = 0;
    q->belakang = 0;
    q->ukuran = 0;
}

int qa_kosong(queue_array *q) { return q->ukuran == 0; }
int qa_penuh(queue_array *q) { return q->ukuran == KAPASITAS; }

int qa_enqueue(queue_array *q, int val) {
    if (qa_penuh(q)) return -1;
    q->data[q->belakang] = val;
    q->belakang = (q->belakang + 1) % KAPASITAS;
    q->ukuran++;
    return 0;
}

int qa_dequeue(queue_array *q, int *out) {
    if (qa_kosong(q)) return -1;
    *out = q->data[q->depan];
    q->depan = (q->depan + 1) % KAPASITAS;
    q->ukuran--;
    return 0;
}

int qa_peek(queue_array *q, int *out) {
    if (qa_kosong(q)) return -1;
    *out = q->data[q->depan];
    return 0;
}

int main(void) {
    queue_array q;
    qa_init(&q);

    for (int i = 10; i <= 60; i += 10) {
        if (qa_enqueue(&q, i) == 0)
            printf("Enqueue %d (ukuran=%zu)\n", i, q.ukuran);
        else
            printf("Enqueue %d gagal: queue penuh\n", i);
    }

    int depan;
    qa_peek(&q, &depan);
    printf("Peek depan: %d\n", depan);

    /* Dequeue 3 elemen */
    for (int i = 0; i < 3; i++) {
        int val;
        qa_dequeue(&q, &val);
        printf("Dequeue %d\n", val);
    }

    /* Enqueue lagi - tes wrap-around */
    for (int i = 70; i <= 100; i += 10) {
        if (qa_enqueue(&q, i) == 0)
            printf("Enqueue %d (ukuran=%zu)\n", i, q.ukuran);
        else
            printf("Enqueue %d gagal: queue penuh\n", i);
    }

    /* Dequeue semua */
    while (!qa_kosong(&q)) {
        int val;
        qa_dequeue(&q, &val);
        printf("Dequeue %d\n", val);
    }

    int val;
    if (qa_dequeue(&q, &val) != 0)
        printf("Dequeue gagal: queue kosong\n");

    return 0;
}

Output yang Dihasilkan:

text 
Enqueue 10 (ukuran=1)
Enqueue 20 (ukuran=2)
Enqueue 30 (ukuran=3)
Enqueue 40 (ukuran=4)
Enqueue 50 (ukuran=5)
Enqueue 60 (ukuran=6)
Peek depan: 10
Dequeue 10
Dequeue 20
Dequeue 30
Enqueue 70 (ukuran=4)
Enqueue 80 (ukuran=5)
Enqueue 90 (ukuran=6)
Enqueue 100 (ukuran=7)
Dequeue 40
Dequeue 50
Dequeue 60
Dequeue 70
Dequeue 80
Dequeue 90
Dequeue 100
Dequeue gagal: queue kosong

Queue sirkular menangani wrap-around: setelah depan dan belakang dequeue/enqueue beberapa kali, belakang bisa kembali ke indeks 0. Operasi modulo % KAPASITAS memastikan indeks selalu valid.

Mari kita telaah baris-baris kode di atas:

  1. Baris 7-11 (queue_array struct): tiga field—array data, indeks depan dan belakang, serta ukuran untuk melacak jumlah elemen. Tanpa ukuran, kita tidak bisa membedakan queue kosong dari queue penuh (keduanya depan == belakang).
  2. Baris 17 (qa_enqueue): tulis data ke data[belakang], lalu majukan belakang dengan modulo: (belakang + 1) % KAPASITAS. Bila belakang sudah di KAPASITAS-1, ia kembali ke 0.
  3. Baris 24 (qa_dequeue): baca data[depan], lalu majukan depan dengan modulo yang sama. Logika simetris dengan enqueue.
  4. Baris 14 (qa_penuh): cek ukuran == KAPASITAS. Tanpa field ukuran, kita harus membandingkan (belakang + 1) % KAPASITAS == depan—tetapi ini hanya berlaku bila kita mengorbankan satu slot (queue terlihat penuh saat kapasitas KAPASITAS-1).
  5. Baris 50-53 (3 dequeue lalu enqueue lagi): ini menguji wrap-around. Setelah 3 dequeue, depan pindah ke indeks 3. Setelah 4 enqueue lagi, belakang melewati akhir array dan kembali ke 0—data tersebar di kedua ujung array.

Queue Berbasis Linked List #

Queue linked list menggunakan dua pointer: depan dan belakang. Enqueue menambah node di akhir, dequeue menghapus node di depan. Keduanya O(1).

c 
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *next;
} node;

typedef struct {
    node *depan;
    node *belakang;
    size_t ukuran;
} queue_list;

void ql_init(queue_list *q) {
    q->depan = NULL;
    q->belakang = NULL;
    q->ukuran = 0;
}

int ql_kosong(queue_list *q) { return q->depan == NULL; }

int ql_enqueue(queue_list *q, int val) {
    node *n = malloc(sizeof(node));
    if (n == NULL) return -1;
    n->data = val;
    n->next = NULL;
    if (q->belakang == NULL) {
        q->depan = n;
        q->belakang = n;
    } else {
        q->belakang->next = n;
        q->belakang = n;
    }
    q->ukuran++;
    return 0;
}

int ql_dequeue(queue_list *q, int *out) {
    if (ql_kosong(q)) return -1;
    node *tmp = q->depan;
    *out = tmp->data;
    q->depan = tmp->next;
    if (q->depan == NULL) q->belakang = NULL;
    free(tmp);
    q->ukuran--;
    return 0;
}

void ql_hapus_semua(queue_list *q) {
    int val;
    while (ql_dequeue(q, &val) == 0) ;
}

int main(void) {
    queue_list q;
    ql_init(&q);

    printf("Simulasi antrian loket:\n");
    const char *orang[] = {"Budi", "Siti", "Andi", "Wati", "Rina"};
    for (int i = 0; i < 5; i++) {
        ql_enqueue(&q, i + 1);
        printf("  Datang: %s (ambil nomor %d)\n", orang[i], i + 1);
    }

    int nomor;
    ql_dequeue(&q, &nomor);
    printf("  Dilayani: nomor %d (%s)\n", nomor, orang[nomor - 1]);
    ql_dequeue(&q, &nomor);
    printf("  Dilayani: nomor %d (%s)\n", nomor, orang[nomor - 1]);

    ql_enqueue(&q, 6);
    printf("  Datang: Dewi (ambil nomor 6)\n");

    printf("  Sisa antrian (ukuran=%zu):\n", q.ukuran);
    while (!ql_kosong(&q)) {
        ql_dequeue(&q, &nomor);
        printf("    nomor %d dilayani\n", nomor);
    }

    ql_hapus_semua(&q);
    return 0;
}

Output yang Dihasilkan:

text 
Simulasi antrian loket:
  Datang: Budi (ambil nomor 1)
  Datang: Siti (ambil nomor 2)
  Datang: Andi (ambil nomor 3)
  Datang: Wati (ambil nomor 4)
  Datang: Rina (ambil nomor 5)
  Dilayani: nomor 1 (Budi)
  Dilayani: nomor 2 (Siti)
  Datang: Dewi (ambil nomor 6)
  Sisa antrian (ukuran=4):
    nomor 3 dilayani
    nomor 4 dilayani
    nomor 5 dilayani
    nomor 6 dilayani

Simulasi antrian loket ini memperlihatkan FIFO: orang dilayani sesuai urutan kedatangan. Budi datang lebih dulu, jadi dilayani pertama. Dewi yang datang belakangan menempati posisi terakhir.

Perbandingan Implementasi #

AspekArray SirkularLinked List
KapasitasTetap (#define)Dinamis
EnqueueO(1) atau gagalO(1) + malloc
DequeueO(1)O(1) + free
Memori overhead0 (slot kosong dianggap overhead)1 pointer per elemen
Wrap-aroundYa (modulo)Tidak perlu (selalu tambah node)
Kegagalan enqueueBila penuhBila malloc gagal