Stack adalah struktur data LIFO (Last In, First Out): elemen terakhir yang dimasukkan adalah elemen pertama yang dikeluarkan. Pada bagian ini kita memakai singly linked list dari Bagian 1 sebagai fondasi stack, dengan operasi stack_push (setara list_insert_depan) dan stack_pop (ambil dari head lalu hapus). Tujuan bagian ini adalah memahami bagaimana struktur LIFO bekerja dan kapan memakainya — undo/redo, evaluation expression, depth-first search.

Konsep #

Stack punya dua operasi inti: push menambah elemen ke puncak (top), pop mengambil elemen dari puncak. Karena kita hanya berinteraksi dengan puncak, kedua operasi bisa O(1). Implementasi dengan linked list memakai head sebagai top — push sama dengan list_insert_depan, pop sama dengan list_hapus_depan dengan nilai dikembalikan ke pemanggil.

Mekanisme push: alokasikan node baru, isi nilai, set next ke top lama, lalu update top ke node baru. Mekanisme pop: bila top kosong, kembalikan error (-1); bila tidak, simpan nilai top ke *out, simpan pointer top ke variabel sementara, update top ke next-nya, lalu free node lama. Operasi pop yang benar membebaskan node yang tidak lagi dipakai — bila lupa free, terjadi memory leak.

Field size pada struct Stack melacak jumlah elemen. Tanpa field ini, kita harus traverse untuk menghitung size — O(n). Dengan field, stack_size menjadi O(1). Pola “menyimpan metadata yang sering dipakai” adalah optimasi umum dalam struktur data.

Implementasi #

Header stack.h:

c 
#ifndef STACK_H
#define STACK_H

typedef struct StackNode {
    int nilai;
    struct StackNode *next;
} StackNode;

typedef struct {
    StackNode *top;
    int size;
} Stack;

void stack_init(Stack *s);
int  stack_push(Stack *s, int nilai);
int  stack_pop(Stack *s, int *out);
int  stack_is_empty(const Stack *s);

#endif /* STACK_H */

Implementasi stack.c:

c 
#include "stack.h"
#include <stdlib.h>

void stack_init(Stack *s) {
    s->top = 0;
    s->size = 0;
}

int stack_push(Stack *s, int nilai) {
    StackNode *n = (StackNode *)malloc(sizeof(StackNode));
    if (n == 0) return -1;
    n->nilai = nilai;
    n->next = s->top;
    s->top = n;
    s->size++;
    return 0;
}

int stack_pop(Stack *s, int *out) {
    if (s->top == 0) return -1;
    StackNode *n = s->top;
    *out = n->nilai;
    s->top = n->next;
    free(n);
    s->size--;
    return 0;
}

int stack_is_empty(const Stack *s) {
    return s->top == 0;
}

Demo mandiri:

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

typedef struct StackNode {
    int nilai;
    struct StackNode *next;
} StackNode;

typedef struct {
    StackNode *top;
    int size;
} Stack;

static void stack_init(Stack *s) {
    s->top = 0;
    s->size = 0;
}

static int stack_push(Stack *s, int nilai) {
    StackNode *n = (StackNode *)malloc(sizeof(StackNode));
    if (n == 0) return -1;
    n->nilai = nilai;
    n->next = s->top;
    s->top = n;
    s->size++;
    return 0;
}

static int stack_pop(Stack *s, int *out) {
    if (s->top == 0) return -1;
    StackNode *n = s->top;
    *out = n->nilai;
    s->top = n->next;
    free(n);
    s->size--;
    return 0;
}

static int stack_is_empty(const Stack *s) {
    return s->top == 0;
}

int main(void) {
    Stack s;
    stack_init(&s);
    printf("Push: 10, 20, 30\n");
    stack_push(&s, 10);
    stack_push(&s, 20);
    stack_push(&s, 30);
    printf("Size: %d\n", s.size);

    printf("Pop semua: ");
    while (!stack_is_empty(&s)) {
        int v;
        stack_pop(&s, &v);
        printf("%d ", v);
    }
    printf("\n");
    printf("Size setelah pop semua: %d\n", s.size);
    return 0;
}

Output yang Dihasilkan:

text 
Push: 10, 20, 30
Size: 3
Pop semua: 30 20 10
Size setelah pop semua: 0

Pengujian #

Build dan jalankan:

bash 
gcc -std=c11 -Wall -Wextra -o stack_demo stack.c main.c
./stack_demo

Verifikasi perilaku LIFO dengan urutan balik: kita push 10, 20, 30 dan pop menghasilkan 30, 20, 10. Bila hasil pop adalah 10, 20, 30 (urutan asli), itu bukan stack melainkan queue — bug implementasi.

Build dengan AddressSanitizer untuk verifikasi tidak ada leak:

bash 
gcc -std=c11 -Wall -Wextra -fsanitize=address -o stack_asan stack.c main.c
./stack_asan

Output yang Dihasilkan (sama dengan run biasa, tanpa pesan error ASan):

text 
Push: 10, 20, 30
Size: 3
Pop semua: 30 20 10
Size setelah pop semua: 0

Mari kita telaah baris-baris kunci pada stack_pop:

  1. Baris if (s->top == 0) return -1;: penjaga underflow. Bila stack kosong, pop tidak boleh dereference s->top (NULL). Mengembalikan -1 memberi sinyal error ke pemanggil tanpa crash.
  2. Baris StackNode *n = s->top;: simpan pointer top ke variabel lokal. Setelah kita update s->top, kita masih bisa free(n) karena variabel lokal n tidak terpengaruh.
  3. Baris *out = n->nilai;: tulis nilai ke parameter output lewat pointer. Pola ini memungkinkan fungsi mengembalikan kode status (0 sukses / -1 error) sekaligus menulis nilai aktual ke pemanggil.
  4. Baris s->top = n->next;: update top ke node berikutnya. Bila n adalah node terakhir, n->next == NULL sehingga stack menjadi kosong setelah pop.
  5. Baris free(n);: bebaskan node lama. Tanpa free, node yang sudah tidak terpakai tetap di heap — memory leak yang terakumulasi bila pop dipanggil ribuan kali.
  6. Baris s->size--;: decrement counter. Pemanggil bisa query size dalam O(1) tanpa traverse.
  7. Baris return 0;: sukses. Pemanggil memeriksa nilai kembalian untuk membedakan “stack kosong” (return -1) dari “pop berhasil” (return 0).

Pada Bagian 3 kita akan membangun queue — struktur FIFO yang memerlukan pointer tambahan tail agar enqueue tetap O(1).

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

hash_table.c

Unduh berkas
c 
/* hash_table.c -- simple hash table with chaining. */
#define _POSIX_C_SOURCE 200809L /* for strdup */
#include "hash_table.h"

#include <stdlib.h>
#include <string.h>

/* djb2 hash function by Daniel J. Bernstein. */
static unsigned long hash_djb2(const char *str) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*str++)) {
        h = ((h << 5) + h) + c; /* h * 33 + c */
    }
    return h;
}

int ht_init(HashTable *ht, size_t capacity) {
    if (!ht || capacity == 0) return -1;
    ht->buckets = calloc(capacity, sizeof(HTNode *));
    if (!ht->buckets) return -1;
    ht->capacity = capacity;
    ht->size = 0;
    return 0;
}

void ht_destroy(HashTable *ht) {
    if (!ht) return;
    for (size_t i = 0; i < ht->capacity; i++) {
        HTNode *cur = ht->buckets[i];
        while (cur) {
            HTNode *next = cur->next;
            free(cur->key);
            free(cur);
            cur = next;
        }
    }
    free(ht->buckets);
    ht->buckets = NULL;
    ht->capacity = 0;
    ht->size = 0;
}

int ht_put(HashTable *ht, const char *key, int value) {
    if (!ht || !key) return -1;
    unsigned long h = hash_djb2(key) % ht->capacity;
    /* Update if key exists. */
    HTNode *cur = ht->buckets[h];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value;
            return 0;
        }
        cur = cur->next;
    }
    /* Insert new node at head. */
    HTNode *node = malloc(sizeof(*node));
    if (!node) return -1;
    node->key = strdup(key);
    if (!node->key) {
        free(node);
        return -1;
    }
    node->value = value;
    node->next = ht->buckets[h];
    ht->buckets[h] = node;
    ht->size++;
    return 0;
}

int ht_get(const HashTable *ht, const char *key, int *out) {
    if (!ht || !key) return -1;
    unsigned long h = hash_djb2(key) % ht->capacity;
    HTNode *cur = ht->buckets[h];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (out) *out = cur->value;
            return 0;
        }
        cur = cur->next;
    }
    return -1;
}

int ht_remove(HashTable *ht, const char *key) {
    if (!ht || !key) return -1;
    unsigned long h = hash_djb2(key) % ht->capacity;
    HTNode *cur = ht->buckets[h];
    HTNode *prev = NULL;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next;
            else      ht->buckets[h] = cur->next;
            free(cur->key);
            free(cur);
            ht->size--;
            return 0;
        }
        prev = cur;
        cur = cur->next;
    }
    return -1;
}

size_t ht_size(const HashTable *ht) {
    return ht ? ht->size : 0;
}

linked_list.c

Unduh berkas
c 
/* linked_list.c -- singly linked list implementation. */
#include "linked_list.h"

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

void ll_init(LinkedList *list) {
    if (!list) return;
    list->head = NULL;
    list->size = 0;
}

void ll_destroy(LinkedList *list) {
    if (!list) return;
    LLNode *cur = list->head;
    while (cur) {
        LLNode *next = cur->next;
        free(cur);
        cur = next;
    }
    list->head = NULL;
    list->size = 0;
}

int ll_push_front(LinkedList *list, int value) {
    if (!list) return -1;
    LLNode *node = malloc(sizeof(*node));
    if (!node) return -1;
    node->data = value;
    node->next = list->head;
    list->head = node;
    list->size++;
    return 0;
}

int ll_push_back(LinkedList *list, int value) {
    if (!list) return -1;
    LLNode *node = malloc(sizeof(*node));
    if (!node) return -1;
    node->data = value;
    node->next = NULL;
    if (!list->head) {
        list->head = node;
    } else {
        LLNode *cur = list->head;
        while (cur->next) cur = cur->next;
        cur->next = node;
    }
    list->size++;
    return 0;
}

int ll_pop_front(LinkedList *list, int *out) {
    if (!list || !list->head) return -1;
    LLNode *node = list->head;
    if (out) *out = node->data;
    list->head = node->next;
    free(node);
    list->size--;
    return 0;
}

int ll_get(const LinkedList *list, size_t index, int *out) {
    if (!list || !out || index >= list->size) return -1;
    LLNode *cur = list->head;
    for (size_t i = 0; i < index; i++) cur = cur->next;
    *out = cur->data;
    return 0;
}

int ll_remove(LinkedList *list, size_t index) {
    if (!list || index >= list->size) return -1;
    LLNode *to_free;
    if (index == 0) {
        to_free = list->head;
        list->head = to_free->next;
    } else {
        LLNode *prev = list->head;
        for (size_t i = 0; i < index - 1; i++) prev = prev->next;
        to_free = prev->next;
        prev->next = to_free->next;
    }
    free(to_free);
    list->size--;
    return 0;
}

int ll_find(const LinkedList *list, int value) {
    if (!list) return -1;
    LLNode *cur = list->head;
    int index = 0;
    while (cur) {
        if (cur->data == value) return index;
        cur = cur->next;
        index++;
    }
    return -1;
}

size_t ll_size(const LinkedList *list) {
    return list ? list->size : 0;
}

void ll_print(const LinkedList *list) {
    if (!list) return;
    printf("[");
    LLNode *cur = list->head;
    while (cur) {
        printf("%d", cur->data);
        if (cur->next) printf(", ");
        cur = cur->next;
    }
    printf("]\n");
}

main.c

Unduh berkas
c 
/* main.c -- demo of all four data structures. */
#include "linked_list.h"
#include "stack.h"
#include "queue.h"
#include "hash_table.h"

#include <stdio.h>
#include <string.h>

static void demo_linked_list(void) {
    printf("--- Linked List ---\n");
    LinkedList list;
    ll_init(&list);

    ll_push_back(&list, 10);
    ll_push_back(&list, 20);
    ll_push_back(&list, 30);
    ll_push_front(&list, 5);
    printf("After pushes: ");
    ll_print(&list);
    printf("Size: %zu\n", ll_size(&list));
    printf("Find 20: index %d\n", ll_find(&list, 20));

    int v;
    ll_pop_front(&list, &v);
    printf("After pop_front (%d): ", v);
    ll_print(&list);

    ll_destroy(&list);
    printf("\n");
}

static void demo_stack(void) {
    printf("--- Stack ---\n");
    Stack s;
    if (stack_init(&s, 4) != 0) {
        printf("stack_init failed\n");
        return;
    }

    stack_push(&s, 1);
    stack_push(&s, 2);
    stack_push(&s, 3);
    printf("Size: %zu\n", stack_size(&s));

    int v;
    while (!stack_is_empty(&s)) {
        stack_pop(&s, &v);
        printf("Popped: %d\n", v);
    }

    stack_destroy(&s);
    printf("\n");
}

static void demo_queue(void) {
    printf("--- Queue ---\n");
    Queue q;
    if (queue_init(&q, 4) != 0) {
        printf("queue_init failed\n");
        return;
    }

    queue_enqueue(&q, 10);
    queue_enqueue(&q, 20);
    queue_enqueue(&q, 30);
    printf("Size: %zu\n", queue_size(&q));

    int v;
    while (!queue_is_empty(&q)) {
        queue_dequeue(&q, &v);
        printf("Dequeued: %d\n", v);
    }

    queue_destroy(&q);
    printf("\n");
}

static void demo_hash_table(void) {
    printf("--- Hash Table ---\n");
    HashTable ht;
    if (ht_init(&ht, 8) != 0) {
        printf("ht_init failed\n");
        return;
    }

    ht_put(&ht, "satu", 1);
    ht_put(&ht, "dua", 2);
    ht_put(&ht, "tiga", 3);
    printf("Size: %zu\n", ht_size(&ht));

    int v;
    if (ht_get(&ht, "dua", &v) == 0) printf("get(dua) = %d\n", v);
    if (ht_get(&ht, "empat", &v) != 0) printf("get(empat) not found\n");

    ht_remove(&ht, "dua");
    printf("After remove dua, size: %zu\n", ht_size(&ht));

    ht_destroy(&ht);
    printf("\n");
}

int main(void) {
    printf("== Struktur Data Demo ==\n\n");
    demo_linked_list();
    demo_stack();
    demo_queue();
    demo_hash_table();
    printf("== Selesai ==\n");
    return 0;
}

queue.c

Unduh berkas
c 
/* queue.c -- FIFO queue (circular buffer). */
#include "queue.h"

#include <stdlib.h>

int queue_init(Queue *q, size_t capacity) {
    if (!q || capacity == 0) return -1;
    q->data = malloc(capacity * sizeof(int));
    if (!q->data) return -1;
    q->capacity = capacity;
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    return 0;
}

void queue_destroy(Queue *q) {
    if (!q) return;
    free(q->data);
    q->data = NULL;
    q->capacity = 0;
    q->head = q->tail = q->size = 0;
}

int queue_enqueue(Queue *q, int value) {
    if (!q || q->size >= q->capacity) return -1;
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % q->capacity;
    q->size++;
    return 0;
}

int queue_dequeue(Queue *q, int *out) {
    if (!q || q->size == 0) return -1;
    if (out) *out = q->data[q->head];
    q->head = (q->head + 1) % q->capacity;
    q->size--;
    return 0;
}

int queue_is_empty(const Queue *q) {
    return !q || q->size == 0;
}

size_t queue_size(const Queue *q) {
    return q ? q->size : 0;
}

stack.c

Unduh berkas
c 
/* stack.c -- LIFO stack (dynamic array). */
#include "stack.h"

#include <stdlib.h>

int stack_init(Stack *s, size_t capacity) {
    if (!s || capacity == 0) return -1;
    s->data = malloc(capacity * sizeof(int));
    if (!s->data) return -1;
    s->capacity = capacity;
    s->size = 0;
    return 0;
}

void stack_destroy(Stack *s) {
    if (!s) return;
    free(s->data);
    s->data = NULL;
    s->capacity = 0;
    s->size = 0;
}

int stack_push(Stack *s, int value) {
    if (!s) return -1;
    if (s->size >= s->capacity) {
        size_t new_cap = s->capacity * 2;
        int *p = realloc(s->data, new_cap * sizeof(int));
        if (!p) return -1;
        s->data = p;
        s->capacity = new_cap;
    }
    s->data[s->size++] = value;
    return 0;
}

int stack_pop(Stack *s, int *out) {
    if (!s || stack_is_empty(s)) return -1;
    if (out) *out = s->data[--s->size];
    return 0;
}

int stack_peek(const Stack *s, int *out) {
    if (!s || stack_is_empty(s) || !out) return -1;
    *out = s->data[s->size - 1];
    return 0;
}

int stack_is_empty(const Stack *s) {
    return !s || s->size == 0;
}

size_t stack_size(const Stack *s) {
    return s ? s->size : 0;
}

tests.c

Unduh berkas
c 
/* tests.c -- unit tests for all four data structures.
 *
 * Compile with:
 *   gcc -std=c11 -Wall -Wextra -fsanitize=address,undefined \
 *       tests.c linked_list.c stack.c queue.c hash_table.c -o test_runner
 */
#include "linked_list.h"
#include "stack.h"
#include "queue.h"
#include "hash_table.h"

#include <stdio.h>
#include <string.h>

static int tests_passed = 0;
static int tests_failed = 0;

#define ASSERT(cond, msg) do { \
    if (cond) { tests_passed++; } \
    else { tests_failed++; printf("FAIL: %s (line %d)\n", msg, __LINE__); } \
} while (0)

static void test_linked_list(void) {
    LinkedList list;
    ll_init(&list);
    ASSERT(ll_size(&list) == 0, "ll empty size");

    ll_push_back(&list, 10);
    ll_push_back(&list, 20);
    ll_push_front(&list, 5);
    ASSERT(ll_size(&list) == 3, "ll size after push");

    int v;
    ASSERT(ll_get(&list, 0, &v) == 0 && v == 5, "ll get(0) == 5");
    ASSERT(ll_get(&list, 2, &v) == 0 && v == 20, "ll get(2) == 20");

    ASSERT(ll_find(&list, 10) == 1, "ll find(10) == 1");
    ASSERT(ll_find(&list, 99) == -1, "ll find(99) not found");

    ASSERT(ll_pop_front(&list, &v) == 0 && v == 5, "ll pop_front == 5");
    ASSERT(ll_size(&list) == 2, "ll size after pop");

    ll_remove(&list, 0);
    ASSERT(ll_size(&list) == 1, "ll size after remove");

    ll_destroy(&list);
    ASSERT(ll_size(&list) == 0, "ll size after destroy");
}

static void test_stack(void) {
    Stack s;
    ASSERT(stack_init(&s, 2) == 0, "stack_init ok");
    ASSERT(stack_is_empty(&s), "stack empty initially");

    ASSERT(stack_push(&s, 100) == 0, "stack_push 100");
    ASSERT(stack_push(&s, 200) == 0, "stack_push 200");
    /* Force a grow. */
    ASSERT(stack_push(&s, 300) == 0, "stack_push 300 (grow)");

    ASSERT(stack_size(&s) == 3, "stack size 3");

    int v;
    ASSERT(stack_peek(&s, &v) == 0 && v == 300, "stack_peek == 300");
    ASSERT(stack_pop(&s, &v) == 0 && v == 300, "stack_pop == 300");
    ASSERT(stack_pop(&s, &v) == 0 && v == 200, "stack_pop == 200");
    ASSERT(stack_pop(&s, &v) == 0 && v == 100, "stack_pop == 100");
    ASSERT(stack_is_empty(&s), "stack empty at end");
    ASSERT(stack_pop(&s, &v) == -1, "stack_pop on empty returns -1");

    stack_destroy(&s);
}

static void test_queue(void) {
    Queue q;
    ASSERT(queue_init(&q, 4) == 0, "queue_init ok");
    ASSERT(queue_is_empty(&q), "queue empty initially");

    for (int i = 1; i <= 4; i++) {
        ASSERT(queue_enqueue(&q, i * 10) == 0, "queue_enqueue");
    }
    ASSERT(queue_size(&q) == 4, "queue full size");

    int v;
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 10, "queue_dequeue 10");
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 20, "queue_dequeue 20");
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 30, "queue_dequeue 30");
    ASSERT(queue_dequeue(&q, &v) == 0 && v == 40, "queue_dequeue 40");
    ASSERT(queue_is_empty(&q), "queue empty after drain");
    ASSERT(queue_dequeue(&q, &v) == -1, "queue_dequeue on empty");

    queue_destroy(&q);
}

static void test_hash_table(void) {
    HashTable ht;
    ASSERT(ht_init(&ht, 4) == 0, "ht_init ok");
    ASSERT(ht_size(&ht) == 0, "ht empty");

    ASSERT(ht_put(&ht, "alpha", 1) == 0, "ht_put alpha");
    ASSERT(ht_put(&ht, "beta", 2) == 0, "ht_put beta");
    ASSERT(ht_put(&ht, "gamma", 3) == 0, "ht_put gamma");
    ASSERT(ht_size(&ht) == 3, "ht size 3");

    int v;
    ASSERT(ht_get(&ht, "beta", &v) == 0 && v == 2, "ht_get beta");
    ASSERT(ht_get(&ht, "missing", &v) == -1, "ht_get missing");

    /* Update existing key. */
    ASSERT(ht_put(&ht, "beta", 22) == 0, "ht_put beta update");
    ASSERT(ht_get(&ht, "beta", &v) == 0 && v == 22, "ht_get beta updated");
    ASSERT(ht_size(&ht) == 3, "ht size unchanged after update");

    ASSERT(ht_remove(&ht, "alpha") == 0, "ht_remove alpha");
    ASSERT(ht_get(&ht, "alpha", &v) == -1, "ht_get alpha gone");
    ASSERT(ht_size(&ht) == 2, "ht size 2 after remove");

    ht_destroy(&ht);
}

int main(void) {
    test_linked_list();
    test_stack();
    test_queue();
    test_hash_table();

    printf("\n=== Test Results ===\n");
    printf("Passed: %d\n", tests_passed);
    printf("Failed: %d\n", tests_failed);
    if (tests_failed == 0) {
        printf("Lulus : %d\n", tests_passed);
        return 0;
    }
    return 1;
}