Fundamental Struktur Data

Panduan visual dan contoh soal lengkap untuk materi Stack, Queue, Tree, dan Graph.

πŸ“š

Stack (Tumpukan)

Contoh Soal: Operasi Push/Pop berurutan.

🚢

Queue (Antrian)

Contoh Soal: Circular Queue Wrap Around.

🌳

Binary Tree

Materi Detail: BST, Terminologi & Traversal.

πŸ•ΈοΈ

Graph

Contoh Soal: Adjacency Matrix & BFS.

πŸ“š

Stack

Last In, First Out (LIFO)

πŸ₯ž

Analogi: Tumpukan Piring

Piring yang terakhir dicuci ditaruh di paling atas, dan akan menjadi yang pertama diambil saat mau dipakai. Anda tidak bisa mengambil piring terbawah tanpa menjatuhkan yang diatasnya.

Visualisasi Operasi Stack

Ilustrasi dari Modul 2.

A B C Top
Contoh Soal (Modul 2)

Diketahui Stack kosong. Lakukan operasi berikut:

  1. Push(A)
  2. Push(B)
  3. Push(C)
  4. Pop()
  5. Push(D)

Jawaban:
1. Stack: [A]
2. Stack: [A, B]
3. Stack: [A, B, C]
4. C dihapus. Stack: [A, B]
5. Stack: [A, B, D]
Posisi Top: D

Implementasi Code

void Push(Stack S, int elemen) {
    if (S.Atas < MaxElemen) {
        S.Atas = S.Atas + 1;
        S.Isi[S.Atas] = elemen;
    } else {
        printf("Stack Penuh");
    }
}
🚢

Queue

First In, First Out (FIFO)

🎫

Analogi: Antrian Loket

Orang yang datang pertama dilayani pertama. Jika antrian array biasa penuh di belakang tapi kosong di depan, kita gunakan konsep "Circular" (berputar) agar efisien.

Visualisasi Circular Queue

Data Array[0..N] Depan Belakang
Contoh Soal (Modul 2)

Bagaimana rumus indeks agar Depan & Belakang bisa kembali ke 0 setelah mencapai batas array N?

Jawaban:
Menggunakan operasi Modulo (Sisa Bagi).
Belakang = (Belakang + 1) MOD N

Operasi Dasar

  • AddQ (Enqueue): Menambah elemen di posisi Belakang.
  • DeleteQ (Dequeue): Mengambil elemen dari posisi Depan.
🌳

Binary Tree & BST

Struktur Data Hierarkis & Binary Search Tree

πŸ“‚

Analogi: Struktur Organisasi / Folder

Root adalah CEO atau Drive Utama (C:). Branch adalah Manajer atau Sub-folder. Leaf (Daun) adalah Staff atau File yang tidak memiliki bawahan lagi. Dalam Binary Tree, setiap atasan maksimal punya 2 bawahan.

1. Terminologi Dasar

Istilah yang wajib dipahami dalam struktur pohon:

Root Node paling atas (tidak punya parent).
Edge Garis penghubung antar node.
Leaf Node yang tidak memiliki anak (child).
Parent/Child Hubungan orang tua dan anak secara langsung.
Height Panjang jalur terpanjang dari node ke leaf (kedalaman).

2. Binary Search Tree (BST)

BST adalah jenis khusus di mana tata letak data memiliki aturan ketat agar pencarian cepat:

  • Kiri: Nilai lebih KECIL dari Root.
  • Kanan: Nilai lebih BESAR dari Root.
50 30 70 20 60 80

Perhatikan: 20 < 30 < 50 < 60 < 70 < 80

3. Metode Traversal (Penelusuran)

Cara mengunjungi setiap node tepat satu kali. Gunakan pohon pada gambar di samping (BST) sebagai contoh.

Studi Kasus Traversal

Pre-Order (Visit - Left - Right)
Kegunaan: Menyalin pohon (Cloning).
Urutan: 50 β†’ 30 β†’ 20 β†’ 70 β†’ 60 β†’ 80

In-Order (Left - Visit - Right)
Kegunaan: Menghasilkan data terurut (Sorting).
Urutan: 20 β†’ 30 β†’ 50 β†’ 60 β†’ 70 β†’ 80
(Lihat! Angkanya jadi urut dari kecil ke besar)

Post-Order (Left - Right - Visit)
Kegunaan: Menghapus pohon (Delete) dari bawah.
Urutan: 20 β†’ 30 β†’ 60 β†’ 80 β†’ 70 β†’ 50

4. Implementasi Penting

Dua fungsi paling sering ditanyakan: Traversal dan Search (Pencarian).

// 1. Struktur Node
struct Node {
    int data;
    Node *left, *right;
};

// 2. Fungsi Search (Khusus BST)
bool search(Node* root, int key) {
    // Base case: kosong atau ketemu
    if (root == NULL) return false;
    if (root->data == key) return true;

    // Jika data < root, cari ke kiri
    if (key < root->data) 
        return search(root->left, key);
    
    // Jika data > root, cari ke kanan
    return search(root->right, key);
}

// 3. Fungsi InOrder Rekursif
void inOrder(Node* node) {
    if (node == NULL) return;
    
    inOrder(node->left);  // Kiri
    printf("%d ", node->data); // Cetak
    inOrder(node->right); // Kanan
}

Pada BST, kompleksitas pencarian adalah O(log n), jauh lebih cepat daripada Array biasa O(n).

πŸ•ΈοΈ

Graph

Kumpulan Vertex & Edge

✈️

Analogi: Peta Penerbangan

Vertex (Node) adalah Bandara. Edge adalah rute penerbangan. Weight (Bobot) adalah harga tiket atau durasi. Directed artinya rute satu arah (misal angin kencang).

1. Terminologi Penting

Vertex (V) Titik atau Node dalam graph.
Edge (E) Garis penghubung antar vertex.
Weight Nilai pada Edge (jarak/biaya).
Directed Graph dengan arah panah (A ke B, tidak sebaliknya).
Degree Jumlah edge yang terhubung ke vertex.

2. Visualisasi Weighted Graph

Contoh: Jarak antar kota (A, B, C).

5 10 2 A B C

Jarak A ke C langsung = 10.
Jarak A ke C via B = 5 + 2 = 7 (Lebih Cepat).

3. Representasi Data

Dua cara menyimpan Graph dalam memori:

A. Adjacency Matrix

Array 2D M[A][B] = 1. Cepat mengecek koneksi, tapi boros memori jika vertex banyak (O(VΒ²)).

B. Adjacency List

Array Linked List. Setiap node punya daftar tetangga. Hemat memori (O(V+E)), tapi lambat cek koneksi tertentu.

4. BFS vs DFS

Metode menelusuri seluruh node:

BFS (Breadth First Search)
  • Prinsip: Melebar (Layer by Layer).
  • Struktur Data: Queue.
  • Guna: Mencari rute terpendek (Shortest Path) pada unweighted graph.
DFS (Depth First Search)
  • Prinsip: Mendalam (Mentok baru balik).
  • Struktur Data: Stack (atau Rekursif).
  • Guna: Maze solving, mendeteksi cycle.

5. Implementasi Struct Graph

#define MAX_V 10

struct Graph {
    int matrix[MAX_V][MAX_V]; // Adjacency Matrix
    int numVertices;
};

void addEdge(Graph *g, int src, int dest) {
    // Untuk Undirected Graph (Dua arah)
    g->matrix[src][dest] = 1;
    g->matrix[dest][src] = 1; 
}

void initGraph(Graph *g, int v) {
    g->numVertices = v;
    // Set semua 0 (tidak terhubung)
    for(int i=0; imatrix[i][j] = 0;
}