# Tugas Pendahuluan - Linked List, Stack, Queue

Nama  : Abdallah Raffael Omari
NPM   : 2306247446

> Note: Soal Programming tidak perlu dicantumkan referensi, hanya soal Teori saja yang perlu referensi minimal 2.

## Teori

### 1. Jelaskan apa itu Linked List, jenis-jenis Linked List, dan keuntungan menggunakan Linked List! (15 poin)

---

Linked list adalah struktur data linear yang terdiri atas serangkaian elemen node. Node tersebut memiliki dua bagian (Data dan Pointer). Pembeda linked list dengan array adalah elemen yang tidak disimpan dalam lokasi memori yang berurutan namun membentuk rantai setiap node yang menunjuk ke node berikutnya.

Linked list terbagi beberapa jenis :
1. Single Linked List : Setiap node memiliki satu pointer ke node berikutnya dan hanya dapat dilakukan dalam satu arah.
2. Double linked list : Setiap node memiliki dua pointer dimana satu menunjuk ke node berikutnya dan yang lain menunjuk ke node sebelumnya. Berlaku dalam dua arah.
3. Circular linked list : Serupa dengan single linked list namun sebagai pembeda node terakhir akan menunjuk ke node pertama dan membentuk lingkaran, pada circular linked list ini tidak ada node yang menunjuk ke `NULL`

Keuntungan linked list :
1. Fleksibel ukurannya
2. Efisien operasi Insert dan Delete
3. Penggunaan memori yang dinamis dan efisien
4. Dasar implementasi struktur data seperti stack, queue, dan graph.

### Referensi:

- [1]geeksforgeeks, “Linked List Data Structure,” GeeksforGeeks, May 22, 2024. [Online]. Available: https://www.geeksforgeeks.org/linked-list-data-structure/ [Diakses: 10-Maret-2025]
- [2]“Types of Linked List,” GeeksforGeeks, Sep. 30, 2020.[Online]. Available: https://www.geeksforgeeks.org/types-of-linked-list/ [Diakses: 10-Maret-2025]
- [3]GeeksforGeeks, “Advantages and Disadvantages of Linked List,” GeeksforGeeks, Dec. 28, 2020. [Online]. Available: https://www.geeksforgeeks.org/advantages-and-disadvantages-of-linked-list/ [Diakses: 10-Maret-2025]
---

### 2. Jelaskan apa itu Stack, contoh kode Stack, dan keuntungan menggunakan Stack! (15 poin)

Stack adalah struktur data linear dengan prinsip Last In, First Out dimana elemen yang terakhir dimasukkan akan menjadi elemen pertama yang keluar. Dengan dua operasi yaitu push dan pop.

Keuntungan penggunaan stack :
1. Manajemen alokasi memori yang efisien
2. Implementasi menggunakan array ataupun linked list yang mudah
3. Menyimpan status pemanggilan fungsi rekursif
4. Aplikasi yang luas
5. Kemudahan untuk melacak operasi dengan prinsip LIFO

Contoh kode stack :

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

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1; // Top diatur ke -1 menandakan stack kosong

int isEmpty() {
    return top == -1;
}

int isFull() {
    return top == MAX_SIZE - 1;
}

void push(int value) {
    if (isFull()) {
        printf("Stack penuh, tidak dapat menambahkan elemen.\n");
    } else {
        top++;
        stack[top] = value;
        printf("Elemen %d ditambahkan ke stack.\n", value);
    }
}

int pop() {
    if (isEmpty()) {
        printf("Stack kosong, tidak dapat menghapus elemen.\n");
        return -1;
    } else {
        int value = stack[top];
        top--;
        printf("Elemen %d dihapus dari stack.\n", value);
        return value;
    }
}

int peek() {
    if (isEmpty()) {
        printf("Stack kosong.\n");
        return -1;
    } else {
        return stack[top];
    }
}

void displayStack() {
    if (isEmpty()) {
        printf("Stack kosong.\n");
    } else {
        printf("Isi stack: ");
        for (int i = 0; i <= top; i++) {
            printf("%d ", stack[i]);
        }
        printf("\n");
    }
}

int main() {
    push(10);
    push(20);
    push(30);

    displayStack(); // Output: Isi stack: 10 20 30

    printf("Elemen teratas: %d\n", peek()); // Output: Elemen teratas: 30

    pop(); // Output: Elemen 30 dihapus dari stack.
    displayStack(); // Output: Isi stack: 10 20

    return 0;
}

### Referensi:

- [1]GeeksforGeeks, “Applications, Advantages and Disadvantages of Stack,” GeeksforGeeks, May 16, 2022. [Online]. Available:
https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-stack/?ref=header_outind [Diakses: 10-Maret-2025]
- [2]Geeksforgeeks, “Stack Data Structure - GeeksforGeeks,” GeeksforGeeks, 2015. [Online]. Available: https://www.geeksforgeeks.org/stack-data-structure/ [Diakses: 10-Maret-2025]
---

### 3. Jelaskan apa itu Queue, jenis-jenis Queue, dan keuntungan menggunakan Queue! (15 poin)

Queue adalah struktur data linear dengan prinsip FIFO (First In, First Out), prinsip ini menggunakan elemen pertama yang dimasukkan menjadi elemen pertama yang dikeluarkan dengan dua operasi utama (Enqueue dan Dequeue).

Jenis Queue :
1. Linear Queue : queue standard dimana elemen ditambahkan di belakang dan dihapus di bagian depan
2. Circular Queue : queue dengan ruang kosong di awal array ketika bagian belakang telah mencapai akhir array
3. Priority Queue : elemen memiliki prioritas dimana yang prioritas tertinggi akan dikeluarkan terlebih dahulu (Tidak selalu menggunakan prinsip FIFO)
4. Double - Ended Queue (Dequeue) : memungkinkan penambahan dan penghapusan elemen dari ujung queue

Keuntungan Queue :
1. Pengelolaan data secara berurut
2. Efisiensi operasi
3. Mencegah Deadlock
4. Berguna dalam algoritma seperti BFS dan Buffering Data
5. Fleksibel

### Referensi:

- [1]GeeksforGeeks, “Queue Data Structure - GeeksforGeeks,” GeeksforGeeks, 2015. [Online]. Available: https://www.geeksforgeeks.org/queue-data-structure/ [Diakses: 10-Maret-2025]
- [2]GeeksforGeeks, “Different Types of Queues and its Applications,” GeeksforGeeks, May 19, 2020. [Online]. Available: https://www.geeksforgeeks.org/different-types-of-queues-and-its-applications/?ref=header_outind [Diakses: 10-Maret-2025]
---

## Programming

### 1. Buatlah program yang dapat mencari 3 angka terbesar menggunakan Linked List! Masukkan dulu angka-angka pada Linked List agar terisi, kemudian implementasikan fungsi untuk mencari 3 angka terbesar. Cantumkan kode program dan screenshot hasil outputnya! (10 poin)

> Untuk mengisi linked list, bebas cara untuk memasukkan angka atau langsung dihardcode juga boleh.

---

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

void NodeMasuk(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

void Podium(struct Node* head) {
    if (head == NULL || head->next == NULL || head->next->next == NULL) {
        printf("Linked List harus memiliki minimal 3 elemen.\n");
        return;
    }

    int first = -1, second = -1, third = -1;
    struct Node* temp = head;

    while (temp != NULL) {
        if (temp->data > first) {
            third = second;
            second = first;
            first = temp->data;
        } else if (temp->data > second) {
            third = second;
            second = temp->data;
        } else if (temp->data > third) {
            third = temp->data;
        }
        temp = temp->next;
    }
    printf("3 angka terbesar: %d, %d, %d\n", first, second, third);
}

void displayList(struct Node* head) {
    struct Node* temp = head;
    printf("Isi Linked List: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    struct Node* head = NULL;

    NodeMasuk(&head, 10);
    NodeMasuk(&head, 50);
    NodeMasuk(&head, 30);
    NodeMasuk(&head, 90);
    NodeMasuk(&head, 20);
    NodeMasuk(&head, 70);

    displayList(head);

    Podium(head);

    return 0;
}


### 2. Buatlah program yang dapat mencari hasil dari (angka_terbesar + angka_terkecil) / 2 menggunakan Queue! Masukkan dulu angka-angka pada Queue agar terisi, kemudian implementasikan fungsi mencari angka_terbesar dan fungsi lain untuk mencari angka_terkecil. Setelah itu, baru output hasil yang sesuai soal. Cantumkan kode program dan screenshot hasil outputnya! (10 poin)

> Untuk mengisi queue, bebas cara untuk memasukkan angka atau langsung dihardcode juga boleh.

---

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

#define gede_SIZE 100

int queue[gede_SIZE];
int front = -1, rear = -1;

int Kosongan() {
    return front == -1 && rear == -1;
}

void enqueue(int value) {
    if (rear == gede_SIZE - 1) {
        printf("Queue penuh, tidak dapat menambahkan elemen.\n");
    } else if (Kosongan()) {
        front = rear = 0;
        queue[rear] = value;
    } else {
        rear++;
        queue[rear] = value;
    }
}

int findGede() {
    if (Kosongan()) {
        printf("Queue kosong.\n");
        return -1;
    }

    int gede = queue[front]; 
    for (int i = front; i <= rear; i++) {
        if (queue[i] > gede) {
            gede = queue[i];
        }
    }
    return gede;
}

int findKecil() {
    if (Kosongan()) {
        printf("Queue kosong.\n");
        return -1;
    }

    int kecil = queue[front];
    for (int i = front; i <= rear; i++) {
        if (queue[i] < kecil) {
            kecil = queue[i];
        }
    }
    return kecil;
}

int main() {
    enqueue(10);
    enqueue(50);
    enqueue(30);
    enqueue(90);
    enqueue(20);
    enqueue(70);

    int gede = findGede();
    int kecil = findKecil();
    if (gede != -1 && kecil != -1) {
        double result = (gede + kecil) / 2.0;
        printf("Angka terbesar: %d\n", gede);
        printf("Angka terkecil: %d\n", kecil);
        printf("Hasil (angka_terbesar + angka_terkecil) / 2: %.2f\n", result);
    }

    return 0;
}


### 3. Well-Balanced Numbers (35 poin)

Buatlah program di bawah ini menggunakan Stack. Sebuah sekuens angka disebut *balanced* jika suatu angka 1 diikuti oleh angka 9, angka 2 diikuti oleh angka 8, angka 3 diikuti oleh angka 7, angka 4 diikuti oleh angka 6, dan angka 5 diikuti oleh angka 5. **Angka yang mengikuti** harus menutup angka yang diikuti secara berurutan, misal harus "28" dan tidak bisa "278". "278" tidak dianggap *balanced* karena angka 7 tidak menutup angka 2.

Diberikan sebuah string n, tentukan apakah string tersebut *balanced* atau tidak. Jika *balanced*, kembalikan `true`, jika tidak, kembalikan `false`. Berikut testcase yang sesuai: **(tidak ada angka 0 pada input)**

#### Example

Input: n = "19192846"
Output: true
Explanation: All the numbers are well-balanced.

Input: n = "123789"
Output: true
Explanation: All the numbers are well-balanced.

Input: n = "146"
Output: false
Explanation: The numbers above are not well-balanced because it doesn't end with 9 to close the 1.

Input: n = "251598"
Output: false
Explanation: The numbers above are not well-balanced because it is closed with 5 first before 9.

---

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

#define MAX_SIZE 100

char stack[MAX_SIZE];
int top = -1;

void push(char value) {
    if (top == MAX_SIZE - 1) {
        printf("Stack penuh, tidak dapat menambahkan elemen.\n");
    } else {
        top++;
        stack[top] = value;
    }
}

char pop() {
    if (top == -1) {
        printf("Stack kosong, tidak dapat menghapus elemen.\n");
        return '\0';
    } else {
        char value = stack[top];
        top--;
        return value;
    }
}

bool isBalanced(char* n) {
    int length = strlen(n);

    for (int i = 0; i < length; i++) {
        char current = n[i];

        if (current == '1' || current == '2' || current == '3' || current == '4' || current == '5') {
            push(current);
        }
        else if (current == '9' || current == '8' || current == '7' || current == '6') {
            if (top == -1) {
                return false; 
            }
            char opener = pop();
            if ((opener == '1' && current != '9') ||
                (opener == '2' && current != '8') ||
                (opener == '3' && current != '7') ||
                (opener == '4' && current != '6')) {
                return false;
            }
        }
        else if (current == '5') {
            if (top == -1) {
                return false;
            }
            char opener = pop();
            if (opener != '5') {
                return false;
            }
        }
    }
    return top == -1;
}

int main() {
    char n[MAX_SIZE];
    printf("Masukkan string angka: ");
    scanf("%s", n);
    if (isBalanced(n)) {
        printf("true\n");
    } else {
        printf("false\n");
    }

    return 0;
}