Stack adalah struktur data LIFO (Last In, First Out): elemen terakhir yang dimasukkan adalah elemen pertama yang dikeluarkan. Bayarkan tumpukan piring: kita ambil dari atas dan menambah dari atas. Stack dipakai di banyak algoritma: pemrosesan rekursi (call stack), evaluasi ekspresi postfix, algoritma backtracking, dan cek kurung seimbang. Pada chapter ini kita akan mengimplementasikan stack dengan dua pendekatan: array statis (kapasitas tetap) dan linked list dinamis (tanpa batas kapasitas), lalu memakainya untuk solver cek kurung seimbang.

Operasi Dasar Stack #

Empat operasi standar stack:

  • Push: tambahkan elemen ke atas stack.
  • Pop: ambil elemen dari atas stack (dan hapus).
  • Peek: baca elemen atas tanpa menghapus.
  • IsEmpty / IsFull: cek kondisi stack.

Push dan pop idealnya O(1). Bila stack berbasis array penuh, push bisa gagal atau memicu realokasi O(n). Stack berbasis linked list selalu O(1) untuk push/pop, tetapi setiap elemen membutuhkan overhead pointer next.

Stack Berbasis Array #

Implementasi paling sederhana: array statis dengan indeks top. Indeks -1 berarti kosong; indeks kapasitas-1 berarti penuh.

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

#define KAPASITAS 8

typedef struct {
    int data[KAPASITAS];
    int top;
} stack_array;

void sa_init(stack_array *s) { s->top = -1; }
int sa_kosong(stack_array *s) { return s->top == -1; }
int sa_penuh(stack_array *s) { return s->top == KAPASITAS - 1; }

int sa_push(stack_array *s, int val) {
    if (sa_penuh(s)) return -1;
    s->data[++s->top] = val;
    return 0;
}

int sa_pop(stack_array *s, int *out) {
    if (sa_kosong(s)) return -1;
    *out = s->data[s->top--];
    return 0;
}

int sa_peek(stack_array *s, int *out) {
    if (sa_kosong(s)) return -1;
    *out = s->data[s->top];
    return 0;
}

int main(void) {
    stack_array s;
    sa_init(&s);

    for (int i = 10; i <= 60; i += 10) {
        if (sa_push(&s, i) == 0)
            printf("Push %d (top=%d)\n", i, s.top);
        else
            printf("Push %d gagal: stack penuh\n", i);
    }

    int top;
    if (sa_peek(&s, &top) == 0)
        printf("Peek: %d\n", top);

    for (int i = 70; i <= 100; i += 10) {
        if (sa_push(&s, i) != 0)
            printf("Push %d gagal: stack penuh\n", i);
        else
            printf("Push %d (top=%d)\n", i, s.top);
    }

    while (!sa_kosong(&s)) {
        int val;
        sa_pop(&s, &val);
        printf("Pop %d\n", val);
    }

    int val;
    if (sa_pop(&s, &val) != 0)
        printf("Pop gagal: stack kosong\n");

    return 0;
}

Output yang Dihasilkan:

text 
Push 10 (top=0)
Push 20 (top=1)
Push 30 (top=2)
Push 40 (top=3)
Push 50 (top=4)
Push 60 (top=5)
Peek: 60
Push 70 (top=6)
Push 80 (top=7)
Push 90 gagal: stack penuh
Push 100 gagal: stack penuh
Pop 80
Pop 70
Pop 60
Pop 50
Pop 40
Pop 30
Pop 20
Pop 10
Pop gagal: stack kosong

Stack berbasis array menolak push bila penuh (top == KAPASITAS-1) dan menolak pop bila kosong (top == -1). Output terurut terbalik dari input—karakteristik LIFO.

Mari kita telaah baris-baris kode di atas:

  1. Baris 7-10 (stack_array struct): struct berisi array data dengan kapasitas tetap dan indeks top. Inisialisasi top = -1 menandakan stack kosong.
  2. Baris 13 (sa_penuh): cek apakah top sudah di indeks terakhir. KAPASITAS - 1 karena indeks mulai dari 0.
  3. Baris 16-19 (sa_push): naikkan top dulu (++s->top), lalu tulis data[top]. Urutan ini penting: harus naikkan dulu karena top mulai dari -1. Bila penuh, return -1 sebagai kode error.
  4. Baris 21-25 (sa_pop): baca data[top], lalu turunkan top. Pakai postfix decrement s->top-- agar pembacaan terjadi sebelum pengurangan.
  5. Baris 27-31 (sa_peek): baca data[top] tanpa mengubah top. Berguna untuk lihat elemen atas tanpa mengeluarkannya.
  6. Baris 41 (sa_push(&s, i) == 0): pemanggil wajib cek return code. Push mengembalikan 0 sukses atau -1 gagal (stack penuh).

Stack Berbasis Linked List #

Stack berbasis linked list tidak punya batas kapasitas (selain memori sistem). Setiap push alokasi node baru; setiap pop membebaskan node.

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

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

typedef struct {
    node *top;
    size_t ukuran;
} stack_list;

void sl_init(stack_list *s) { s->top = NULL; s->ukuran = 0; }
int sl_kosong(stack_list *s) { return s->top == NULL; }

int sl_push(stack_list *s, int val) {
    node *n = malloc(sizeof(node));
    if (n == NULL) return -1;
    n->data = val;
    n->next = s->top;
    s->top = n;
    s->ukuran++;
    return 0;
}

int sl_pop(stack_list *s, int *out) {
    if (sl_kosong(s)) return -1;
    node *tmp = s->top;
    *out = tmp->data;
    s->top = tmp->next;
    free(tmp);
    s->ukuran--;
    return 0;
}

int sl_peek(stack_list *s, int *out) {
    if (sl_kosong(s)) return -1;
    *out = s->top->data;
    return 0;
}

void sl_hapus_semua(stack_list *s) {
    int val;
    while (sl_pop(s, &val) == 0) ;
}

/* Demo: cek kurung seimbang dengan stack */
int cek_kurung(const char *str) {
    stack_list s;
    sl_init(&s);
    int hasil = 1;

    for (size_t i = 0; str[i] != '\0'; i++) {
        char c = str[i];
        if (c == '(' || c == '[' || c == '{') {
            sl_push(&s, (int)c);
        } else if (c == ')' || c == ']' || c == '}') {
            int top;
            if (sl_pop(&s, &top) != 0) {
                hasil = 0;
                break;
            }
            char pasangan = (char)top;
            if ((c == ')' && pasangan != '(') ||
                (c == ']' && pasangan != '[') ||
                (c == '}' && pasangan != '{')) {
                hasil = 0;
                break;
            }
        }
    }

    if (hasil && !sl_kosong(&s)) hasil = 0;
    sl_hapus_semua(&s);
    return hasil;
}

int main(void) {
    stack_list s;
    sl_init(&s);

    for (int i = 1; i <= 5; i++) {
        sl_push(&s, i * 10);
        printf("Push %d (ukuran=%zu)\n", i * 10, s.ukuran);
    }

    int top;
    sl_peek(&s, &top);
    printf("Peek: %d\n", top);

    while (!sl_kosong(&s)) {
        int val;
        sl_pop(&s, &val);
        printf("Pop %d\n", val);
    }

    printf("\nCek kurung:\n");
    const char *uji[] = {"(a+b)", "(a+b]", "((a+b)*c)", "([{}])", "((())"};
    for (int i = 0; i < 5; i++) {
        printf("  '%s' -> %s\n", uji[i],
               cek_kurung(uji[i]) ? "seimbang" : "tidak seimbang");
    }

    return 0;
}

Output yang Dihasilkan:

text 
Push 10 (ukuran=1)
Push 20 (ukuran=2)
Push 30 (ukuran=3)
Push 40 (ukuran=4)
Push 50 (ukuran=5)
Peek: 50
Pop 50
Pop 40
Pop 30
Pop 20
Pop 10

Cek kurung:
  '(a+b)' -> seimbang
  '(a+b]' -> tidak seimbang
  '((a+b)*c)' -> seimbang
  '([{}])' -> seimbang
  '((())' -> tidak seimbang

Demo cek kurung seimbang memperlihatkan kekuatan stack: setiap kurung buka di-push, setiap kurung tutup di-pop dan dicocokkan. Bila pasangan tidak sesuai atau stack tidak kosong di akhir, kurung tidak seimbang.

Perbandingan Implementasi #

AspekArrayLinked List
KapasitasTetap (#define)Dinamis (terbatas memori)
PushO(1) atau gagalO(1) + malloc
PopO(1)O(1) + free
Memori overhead01 pointer per elemen
Cache localityBaikBuruk
Kegagalan pushBila penuhBila malloc gagal