Queue adalah struktur data FIFO (First In, First Out): elemen pertama yang dimasukkan adalah elemen pertama yang dikeluarkan. Berbeda dari stack yang hanya butuh pointer top, queue memerlukan dua pointer — head (depan, untuk dequeue) dan tail (belakang, untuk enqueue). Pada bagian ini kita membangun queue.h dan queue.c dengan operasi queue_enqueue dan queue_dequeue. Tujuan bagian ini adalah memahami kapan queue lebih cocok dari stack dan bagaimana menjaga konsistensi dua pointer.

Konsep #

Queue mensimulasikan antrian di dunia nyata: orang yang datang pertama dilayani pertama. Implementasi naive dengan satu pointer (hanya head) membuat enqueue menjadi O(n) karena kita harus traverse ke node terakhir setiap kali menambah. Solusinya: simpan pointer tail agar enqueue langsung menautkan ke tail->next tanpa traverse — operasi O(1).

Mekanisme enqueue: alokasikan node baru, isi nilai, set next = NULL. Bila queue kosong (tail == NULL), head dan tail keduanya menunjuk ke node baru. Bila tidak kosong, tail->next = n lalu update tail ke node baru. Mekanisme dequeue: bila head == NULL, kembalikan error; bila tidak, simpan nilai head, simpan pointer lama ke variabel sementara, update head ke head->next, lalu free node lama. Kasus khusus: bila head setelah update menjadi NULL, berarti queue baru saja kosong — kita juga harus reset tail = NULL agar konsisten.

Konsistensi dua pointer adalah hal paling rumit dalam implementasi queue. Bila tail tidak di-reset saat queue kosong, tail menjadi dangling pointer — operasi enqueue berikutnya akan dereference freed memory dan undefined behavior.

Implementasi #

Header queue.h:

c 
#ifndef QUEUE_H
#define QUEUE_H

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

typedef struct {
    QueueNode *head;
    QueueNode *tail;
    int size;
} Queue;

void queue_init(Queue *q);
int  queue_enqueue(Queue *q, int nilai);
int  queue_dequeue(Queue *q, int *out);
int  queue_is_empty(const Queue *q);

#endif /* QUEUE_H */

Implementasi queue.c:

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

void queue_init(Queue *q) {
    q->head = 0;
    q->tail = 0;
    q->size = 0;
}

int queue_enqueue(Queue *q, int nilai) {
    QueueNode *n = (QueueNode *)malloc(sizeof(QueueNode));
    if (n == 0) return -1;
    n->nilai = nilai;
    n->next = 0;
    if (q->tail == 0) {
        q->head = n;
        q->tail = n;
    } else {
        q->tail->next = n;
        q->tail = n;
    }
    q->size++;
    return 0;
}

int queue_dequeue(Queue *q, int *out) {
    if (q->head == 0) return -1;
    QueueNode *n = q->head;
    *out = n->nilai;
    q->head = n->next;
    if (q->head == 0) q->tail = 0;
    free(n);
    q->size--;
    return 0;
}

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

Demo mandiri:

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

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

typedef struct {
    QueueNode *head;
    QueueNode *tail;
    int size;
} Queue;

static void queue_init(Queue *q) {
    q->head = 0; q->tail = 0; q->size = 0;
}

static int queue_enqueue(Queue *q, int nilai) {
    QueueNode *n = (QueueNode *)malloc(sizeof(QueueNode));
    if (n == 0) return -1;
    n->nilai = nilai;
    n->next = 0;
    if (q->tail == 0) {
        q->head = n;
        q->tail = n;
    } else {
        q->tail->next = n;
        q->tail = n;
    }
    q->size++;
    return 0;
}

static int queue_dequeue(Queue *q, int *out) {
    if (q->head == 0) return -1;
    QueueNode *n = q->head;
    *out = n->nilai;
    q->head = n->next;
    if (q->head == 0) q->tail = 0;
    free(n);
    q->size--;
    return 0;
}

int main(void) {
    Queue q;
    queue_init(&q);
    printf("Enqueue: 100, 200, 300\n");
    queue_enqueue(&q, 100);
    queue_enqueue(&q, 200);
    queue_enqueue(&q, 300);
    printf("Size: %d\n", q.size);

    printf("Dequeue semua (FIFO): ");
    int v;
    while (queue_dequeue(&q, &v) == 0) {
        printf("%d ", v);
    }
    printf("\nSize setelah dequeue semua: %d\n", q.size);
    return 0;
}

Output yang Dihasilkan:

text 
Enqueue: 100, 200, 300
Size: 3
Dequeue semua (FIFO): 100 200 300
Size setelah dequeue semua: 0

Pengujian #

Build dan jalankan:

bash 
gcc -std=c11 -Wall -Wextra -o queue_demo queue.c main.c
./queue_demo

Verifikasi perilaku FIFO: enqueue 100, 200, 300 lalu dequeue harus menghasilkan 100, 200, 300 (urutan sama). Bila hasil berbeda (misalnya 300, 200, 100), itu stack — bug implementasi.

Verifikasi kasus khusus: enqueue 1 elemen, dequeue, lalu enqueue lagi. Bila tail tidak di-reset saat queue kosong, operasi enqueue kedua akan crash.

bash 
gcc -std=c11 -Wall -Wextra -fsanitize=address -o queue_asan queue.c main.c
./queue_asan

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

text 
Enqueue: 100, 200, 300
Size: 3
Dequeue semua (FIFO): 100 200 300
Size setelah dequeue semua: 0

Mari kita telaah baris-baris kunci pada queue_enqueue:

  1. Baris QueueNode *n = (QueueNode *)malloc(sizeof(QueueNode));: alokasi node baru di heap. Sama dengan linked list dan stack.
  2. Baris n->next = 0;: node baru selalu berdiri di belakang — next-nya NULL. Berbeda dari stack di mana node baru di-depan (next = top lama).
  3. Baris if (q->tail == 0): kasus queue kosong. Bila tail == NULL, pasti head juga NULL. Kita set keduanya ke node baru — node ini menjadi satu-satunya elemen.
  4. Baris q->head = n; q->tail = n;: dua pointer menunjuk ke node yang sama. Inilah kondisi queue dengan satu elemen.
  5. Baris q->tail->next = n; (else branch): tautkan node lama ke node baru. Setelah baris ini, tail lama tidak lagi menjadi node terakhir — next-nya sekarang menunjuk ke n.
  6. Baris q->tail = n;: update tail ke node baru. Sekarang tail menunjuk ke node terakhir (yaitu n).

Pada queue_dequeue:

  1. Baris q->head = n->next;: update head ke node berikutnya. Bila queue hanya punya satu elemen, n->next == NULL sehingga head menjadi NULL.
  2. Baris if (q->head == 0) q->tail = 0;: kasus kritis! Bila queue baru saja kosong (head jadi NULL), tail juga harus NULL. Tanpa baris ini, tail tetap menunjuk ke node yang sudah di-free — dangling pointer yang akan menyebabkan crash pada enqueue berikutnya.
  3. Baris free(n);: bebaskan node lama. Penting: free SETELAH selesai dengan *out dan update pointer — setelah free, akses ke n adalah undefined behavior.

Pada Bagian 4 kita akan membangun hash table — struktur O(1) untuk pencarian key-value dengan collision handling via chaining.

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;
}