Stack dan Queue

Implementasi stack dan queue dengan array maupun linked list beserta pemakaiannya.

Daftar isi

Stack dan queue adalah dua struktur data yang mengatur urutan masuk dan kelurnya data dengan aturan yang berlawanan, yaitu last in first out untuk stack dan first in first out untuk queue. Stack hanya mengizinkan penambahan dan pengambilan pada satu ujung yang disebut atas, sedangkan queue menerima data baru di belakang dan mengeluarkan data dari depan. Topik ini membangun keduanya dengan array, lalu memperbaiki kelemahannya memakai larik melingkar. Versi linked list menyusul, ditutup dengan contoh pemakaian keduanya pada program nyata.

Stack dengan array#

Versi array memakai satu indeks bernama atas yang menunjuk elemen teratas, dengan nilai -1 menandakan tumpukan kosong. Operasi push menaikkan atas lalu mengisi slotnya, sedangkan pop membaca elemen pada atas lalu menurunkannya. Kedua operasi hanya menyentuh satu ujung array sehingga biayanya tetap, tidak bergantung pada banyaknya isi. Selama operasi, anggota atas menjadi satu-satunya bagian yang berubah, sedangkan array penampungnya tetap sebagaimana deklarasinya. Karena C tidak memeriksa batas array, pemeriksaan penuh dan kosong menjadi tanggung jawab kode, dan keduanya dilaporkan melalui nilai kembali berupa int.

c tumpukan-array.c

#include <stdio.h>

#define KAPASITAS 8

struct tumpukan {
    int data[KAPASITAS];
    int atas;   /* indeks elemen teratas, -1 apabila kosong */
};

void inisialisasi(struct tumpukan *t)
{
    t->atas = -1;
}

int kosong(const struct tumpukan *t)
{
    return t->atas == -1;
}

int penuh(const struct tumpukan *t)
{
    return t->atas == KAPASITAS - 1;
}

int push(struct tumpukan *t, int nilai)
{
    if (penuh(t)) {
        return 0;
    }
    t->atas = t->atas + 1;
    t->data[t->atas] = nilai;
    return 1;
}

int pop(struct tumpukan *t, int *hasil)
{
    if (kosong(t)) {
        return 0;
    }
    *hasil = t->data[t->atas];
    t->atas = t->atas - 1;
    return 1;
}

void cetak(const struct tumpukan *t)
{
    printf("Tumpukan (atas di kiri): [");
    for (int i = t->atas; i >= 0; i--) {
        printf("%d", t->data[i]);
        if (i > 0) {
            printf(" ");
        }
    }
    printf("]\n");
}

int main(void)
{
    struct tumpukan t;
    inisialisasi(&t);
    int keluar;

    push(&t, 3);
    push(&t, 8);
    push(&t, 15);
    cetak(&t);

    if (pop(&t, &keluar)) {
        printf("pop mengambil %d\n", keluar);
    }
    if (pop(&t, &keluar)) {
        printf("pop mengambil %d\n", keluar);
    }
    printf("Elemen teratas sekarang: %d\n", t.data[t.atas]);

    while (pop(&t, &keluar)) {
        printf("pop mengambil %d\n", keluar);
    }
    if (kosong(&t)) {
        printf("Tumpukan kosong, pop berhenti.\n");
    }
    return 0;
}

text Keluaran

Tumpukan (atas di kiri): [15 8 3]
pop mengambil 15
pop mengambil 8
Elemen teratas sekarang: 3
pop mengambil 3
Tumpukan kosong, pop berhenti.

Fungsi pop tidak mengembalikan nilai langsung melalui return, melainkan menyalinnya ke parameter keluaran int *hasil dan memakai nilai kembali untuk melaporkan keberhasilan. Pola ini menghindari kebingungan antara nilai data dengan penanda gagal, karena setiap bilangan berpotensi menjadi isi tumpukan yang sah. Perulangan while (pop(&t, &keluar)) pada akhir program memperlihatkan kegunaan pola tersebut, yaitu mengosongkan tumpukan sampai pop melaporkan gagal.

Queue dengan array melingkar#

Queue versi array menuntut perlakuan berbeda karena data keluar dari depan, sehingga slot bekas elemen yang keluar menjadi lubang di awal array. Menggeser seluruh isi ke depan setiap kali dequeue memakan waktu sebanding dengan isi. Solusi yang lazim adalah larik melingkar (circular buffer), yaitu indeks depan dan belakang melompat kembali ke nol setelah mencapai ujung melalui operasi sisa bagi. Operasi sisa bagi aman dipakai karena kedua indeks hanya bergerak maju dan tidak pernah bernilai negatif. Pembungkus indeks ini membuat slot bekas dipakai ulang tanpa pergeseran apa pun.

c antrean-array.c

#include <stdio.h>

#define KAPASITAS 5

struct antrean {
    int data[KAPASITAS];
    int depan;     /* indeks elemen terdepan */
    int belakang;  /* indeks slot kosong berikutnya */
    int jumlah;    /* banyak elemen yang sedang antre */
};

void inisialisasi(struct antrean *a)
{
    a->depan = 0;
    a->belakang = 0;
    a->jumlah = 0;
}

int kosong(const struct antrean *a)
{
    return a->jumlah == 0;
}

int penuh(const struct antrean *a)
{
    return a->jumlah == KAPASITAS;
}

int enqueue(struct antrean *a, int nilai)
{
    if (penuh(a)) {
        return 0;
    }
    a->data[a->belakang] = nilai;
    a->belakang = (a->belakang + 1) % KAPASITAS;
    a->jumlah = a->jumlah + 1;
    return 1;
}

int dequeue(struct antrean *a, int *hasil)
{
    if (kosong(a)) {
        return 0;
    }
    *hasil = a->data[a->depan];
    a->depan = (a->depan + 1) % KAPASITAS;
    a->jumlah = a->jumlah - 1;
    return 1;
}

void cetak(const struct antrean *a)
{
    printf("Antrean: [");
    for (int i = 0; i < a->jumlah; i++) {
        int indeks = (a->depan + i) % KAPASITAS;
        printf("%d", a->data[indeks]);
        if (i < a->jumlah - 1) {
            printf(" ");
        }
    }
    printf("] depan=%d belakang=%d\n", a->depan, a->belakang);
}

int main(void)
{
    struct antrean a;
    inisialisasi(&a);
    int keluar;

    enqueue(&a, 7);
    enqueue(&a, 12);
    enqueue(&a, 19);
    cetak(&a);

    dequeue(&a, &keluar);
    printf("dequeue mengambil %d\n", keluar);
    dequeue(&a, &keluar);
    printf("dequeue mengambil %d\n", keluar);
    cetak(&a);

    enqueue(&a, 25);
    enqueue(&a, 31);
    cetak(&a);
    return 0;
}

text Keluaran

Antrean: [7 12 19] depan=0 belakang=3
dequeue mengambil 7
dequeue mengambil 12
Antrean: [19] depan=2 belakang=3
Antrean: [19 25 31] depan=2 belakang=0

Baris terakhir keluaran memperlihatkan saat kuncinya, yaitu belakang berpindah dari 4 kembali ke 0 sehingga antrean meliputi ujung array. Anggota jumlah wajib ada karena keadaan kosong dan keadaan penuh sama-sama menghasilkan pasangan depan dan belakang yang identik, sehingga indeks semata tidak cukup untuk membedakan keduanya. Dengan jumlah, pemeriksaan kosong dan penuh berupa satu perbandingan sederhana tanpa menyisakan satu slot untuk menghindari kebingungan itu.

Versi linked list#

Versi linked list menghilangkan batas kapasitas tetap karena setiap elemen dialokasikan lewat malloc saat dibutuhkan. Stack terbentuk dengan menyisipkan dan menghapus simpul hanya di kepala, sedangkan queue menyimpan dua pointer, yaitu kepala untuk keluar dan ekor untuk masuk. Program berikut memasukkan angka 10, 20, dan 30 ke kedua struktur dengan urutan yang sama, lalu selisih perilakunya langsung terlihat dari urutan keluarannya.

c tumpukan-antrean-linked.c

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

struct simpul {
    int nilai;
    struct simpul *berikut;
};

void push(struct simpul **kepala, int nilai)
{
    struct simpul *baru = malloc(sizeof(struct simpul));
    if (baru == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    baru->nilai = nilai;
    baru->berikut = *kepala;
    *kepala = baru;
}

int pop(struct simpul **kepala, int *hasil)
{
    if (*kepala == NULL) {
        return 0;
    }
    struct simpul *atas = *kepala;
    *hasil = atas->nilai;
    *kepala = atas->berikut;
    free(atas);
    return 1;
}

void enqueue(struct simpul **kepala, struct simpul **ekor, int nilai)
{
    struct simpul *baru = malloc(sizeof(struct simpul));
    if (baru == NULL) {
        fprintf(stderr, "Alokasi gagal.\n");
        exit(1);
    }
    baru->nilai = nilai;
    baru->berikut = NULL;

    if (*kepala == NULL) {
        *kepala = baru;
    } else {
        (*ekor)->berikut = baru;
    }
    *ekor = baru;
}

int dequeue(struct simpul **kepala, int *hasil)
{
    return pop(kepala, hasil);
}

int main(void)
{
    struct simpul *tumpukan = NULL;
    struct simpul *q_kepala = NULL;
    struct simpul *q_ekor = NULL;
    int keluar;

    for (int i = 1; i <= 3; i++) {
        push(&tumpukan, i * 10);
        enqueue(&q_kepala, &q_ekor, i * 10);
    }

    printf("Kedua struktur menerima 10, 20, 30 dengan urutan yang sama.\n");

    while (pop(&tumpukan, &keluar)) {
        printf("stack pop   : %d\n", keluar);
    }
    while (dequeue(&q_kepala, &keluar)) {
        printf("queue dequeue: %d\n", keluar);
    }
    return 0;
}

text Keluaran

Kedua struktur menerima 10, 20, 30 dengan urutan yang sama.
stack pop   : 30
stack pop   : 20
stack pop   : 10
queue dequeue: 10
queue dequeue: 20
queue dequeue: 30

Diagram berikut merangkum kedua struktur beserta ujung tempat operasinya bekerja, dan tabel di bawahnya membandingkan dua pilihan implementasi yang telah dibahas.

Stack dengan satu ujung operasi dan queue dengan dua ujung operasi

Aspek	Array	Linked list
Kapasitas	tetap sejak deklarasi	bertambah mengikuti memori
Biaya operasi inti	tetap	tetap
Memori per elemen	hanya data	data ditambah satu pointer
Lokasi memori	berurutan, ramah cache	tersebar di heap

Pemakaian pada program nyata#

Stack muncul pada setiap pemanggilan fungsi, karena C menyimpan variabel lokal dan alamat kembali pada memori stack yang bekerja persis dengan aturan masuk terakhir keluar pertama. Rekursi memanfaatkan mekanisme yang sama, yaitu setiap pemanggilan menumpuk frame baru di atas frame pemanggilnya. Aplikasi lain yang berpola sama adalah riwayat undo pada pengolah teks, karena langkah terakhir selalu menjadi langkah pertama yang dibatalkan.

Queue menjadi model alami untuk antrean tiket loket, buffer masukan keyboard, serta pengatur tugas yang melayani permintaan sesuai urutan kedatangannya. Prinsip keadilan urutan inilah alasan queue dipilih ketika setiap pesanan harus dilayani tanpa membedakan ukurannya. Apabila kebutuhan berubah menjadi prioritas, struktur yang lebih tepat adalah antrean berprioritas, tetapi bentuk dasarnya tetap queue.

Mengenali pola LIFO dan FIFO pada program nyata memudahkan pemilihan struktur ketika persyaratan serupa muncul, misalnya catatan peristiwa yang dibaca dari yang terbaru terlebih dahulu. Pemilihan yang salah hanya terasa pada waktu eksekusi, karena kode kedua struktur sama-sama ringkas dan tidak ada pesan error yang mengingatkan. Kebiasaan menanyakan urutan layanan itulah penentu utama pemilihan struktur.

Kesalahan umum#

Lima kesalahan berikut muncul karena kelalaian memeriksa keadaan tepi, yaitu kosong, penuh, dan simpul pertama.

Push tanpa memeriksa penuh. C tidak menolak penugasan di luar batas array, sehingga data menimpa memori lain dan kerusakan muncul di tempat yang tampaknya tidak berkaitan. Selalu periksa penuh sebelum menulis, atau laporkan kegagalan melalui nilai kembali.
Membaca tumpukan kosong. t.data[t.atas] ketika atas bernilai -1 membaca di luar array. Panggil pop atau periksa kosong terlebih dahulu sebelum menyentuh elemen teratas.
Menghitung kosong dan penuh dari indeks semata. Pada larik melingkar, depan == belakang berlaku untuk dua keadaan berlawanan. Pegang penghitung jumlah agar pemeriksaannya tetap jelas.
Lupa menginisialisasi ekor pada linked queue. Penugasan (*ekor)->berikut ketika ekor masih NULL menghentikan program. Beri cabang khusus untuk simpul pertama, sebagaimana dilakukan pada enqueue di atas.
Menumpuk status gagal dengan data. Bilangan apa pun dapat menjadi isi tumpukan yang sah, sehingga mengembalikan nilai data sekaligus penanda gagal melalui return menimbulkan kebingungan. Pisahkan keduanya dengan parameter keluaran, sebagaimana pola pop di atas.

Ringkasan#

Stack melayani data terakhir lebih dahulu melalui satu ujung, sedangkan queue melayani data terlebih dahulu masuk melalui dua ujung.
Implementasi array membutuhkan pemeriksaan penuh dan kosong, dan queue array memerlukan larik melingkar agar slot bekas dipakai ulang tanpa pergeseran.
Implementasi linked list membebaskan dari batas kapasitas dengan biaya satu pointer per elemen, dan selisih LIFO dengan FIFO terlihat langsung dari urutan keluaran program.

Referensi#

queue(3) — Linux man-pages project — Makro pustaka standar untuk membangun list, tail queue, dan circular queue di C.
malloc(3) — Linux man-pages project — Alokasi yang dipakai untuk setiap simpul pada versi linked list.