# Tugas Pendahuluan - Linked List, Stack, Queue

Nama  : Hasan Abdullah Azzam
NPM   : 2406428314

> 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 merupakkan salah satu struktur data yang dapat digunakkan dalam bahasa C. Linked List terdiri dari serangkaian Node yang saling terhubung satu sama lain. setiap Node memiliki 2 bagian:
- Data: berisi variabel yang disimpan.
- Pointer : sebuah pointer yang mengarah ke alamat node selanjutnya.

Kelebihan dari Linked List adalah ukuranya yang dinamis dan bisa ditambahkan, selain itu, struktur ini tidak tersusun secara berurutan tetapi bebas dimanapun dan dihubungkan dengan pointer, sehingga elemen didalamnya sangat mudah dioperasikan entah itu dihapus atau disisip dengan hanya mengatur pointer yang ada.

jenis-jenis linked list:
- Singly Linked List: linked List yang setiap Node hanya memiliki satu pointer kerah selanjutnya, sehingga hanya memungkinakan traversal satu arah ke depan.
- Doubly Linked List : Linked List yang memiliki 2 pointer, sehingga memungkinkan traversal ke dua arah.
- circular Linked List : Linked list yang Node terkahirya terhubung dengan Node awal, sehingga membentuk kesinambungan.

### Referensi:

- GeeksforGeeks, “Linked List in C,” GeeksforGeeks, Jun. 11, 2024. https://www.geeksforgeeks.org/linked-list-in-c/. [Diakses: 10-Maret-2025]
- GeeksforGeeks, “What is Linked List,” GeeksforGeeks, Mar. 08, 2013. https://www.geeksforgeeks.org/what-is-linked-list/. [Diakses: 10-Maret-2025]
- Modul Algoritma dan Pemrograman - Chapter 6: Linked List [Diakses: 10-Maret-2025]
‌

---

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

Stack adalah structur data yang menganut prisip LIFO atau Last in, First out. Dimana data yang terakhir kali di masukkan akan menempati posisi atas dan dapat diakses pertama kali.

keuntungan dari penggunaan stack adalah kesederhananya dan sangat efisien saat dijalankan, selain itu struktur ini juga menggunakan LIFO sehingga berguna di beberapa kondisi yang membutuhkanya.
dalam membuatnya ada 2 cara umum, menggunakan array atau Linked list:

secara general Stack memiliki beberapa fungsi dasar yang sering digunakkan yaitu:
- Push: memasukkan data awal ke TOP
- Pop : mengambil data di posisi TOP
- Peek : mengambil data ke suatu urutan dari TOP
- cekFull : cek apakah Stack sudah melebihi SIZE
- isEmpty : cek apakah stack kosong

typedef Sturct{
    int Size;//menyimpan ukuran Stack
    int Top;//menyimpan indeks posisi data TOP
    int *s;// pointer ke data yng di masukkan
}Stack;

void push(Stack *st, int x) {// fungsi push
    if (st->top == st->size - 1) {//cek apakah Stack full
        printf("Stack Overflow\n");
    } else {
        st->top++;//update TOP
        st->s[st->top] = x;//isi data Stack
    }
}

int pop(struct stack *st) {// fungsi pop
    int x = -1;
    if (st->top == -1) {
        printf("Stack Underflow\n");// cek apakah ada isi dari Stack
    } else {
        x = st->s[st->top];// ambil nilai di indek TOP
        st->top --;// update TOP ke selanjtnya
    }
    return x;
}

int peek(struct stack st, int pos) {// fungsi peek, mirip dengan pop dengan tambahan pos
    int x = -1;
    if (st.top - pos + 1 < 0) {
        printf("Invalid Position\n");
    } else {
        x = st.s[st.top - pos + 1];// ambil data di sesuai posisi yg diinginkan
    }
    return x;
}

int isEmpty(struct stack st) {// fungsi cek Stack apakah kosong atau tidak
    if (st.top == -1) {
        return 1;
    } else {
        return 0;
    }
}

### Referensi:

- GeeksforGeeks, “Introduction to Stack - Data Structure and Algorithm Tutorials,” GeeksforGeeks, May 06, 2017. https://www.geeksforgeeks.org/introduction-to-stack-data-structure-and-algorithm-tutorials/ . [Diakses: 10-Maret-2025]
‌- GeeksforGeeks, “Applications, Advantages and Disadvantages of Stack,” GeeksforGeeks, May 16, 2022. https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-stack/ . [Diakses: 10-Maret-2025]
- Modul Algoritma dan Pemrograman - Chapter 6: Linked List. [Diakses: 10-Maret-2025]
‌

---

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

Queue, adalah structur data yang berlawanan dengan stack, struktur ini menggunakkan prinsip FIFO, First in, First out. Dimana data yang pertama kali di masukkan akan menempati posisi awal dan dapat diakses pertama kali.

kelebihan dari penggunaan struktur ini adlaah kemampuanya untuk melakukkan pengurutan data sehingga bisa digunakkan pada kondisi yang membutuhkan semacam antrian atau jadwal berurutan.

Sama seperti Stack, dalam membuat Queue ada 2 cara umum, menggunakan array atau Linked list:

secara general Stack memiliki beberapa fungsi dasar yang sering digunakkan yaitu:
- enqueue: memasukkan data kedalam Queue
- dequeue : mengambil data dari queue

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

typedef struct Queue {
    Node *front; // Pointer keelemen pertama
    Node *rear; // Pointer kelemen terakhir
}Queue;


void enqueue(Queue *que, int data){
    Node *temp = (Node *)malloc(sizeof(Node));
	
	if(temp == NULL){
		printf("error");
		return;
	}
	
	temp->data = data;
	temp->next = NULL;
	
	if(que->rear == NULL){
		que->front = que->rear = temp;
	}else{
		que->rear->next = temp;
		que->rear = temp;
	}
}

int dequeue(Queue *q) {
    int x = -1;
    Node *p;
    
    if (q->front == NULL) {
        printf("Queue is Empty\n");
    } else {
        p = q->front;
        q->front = q->front ->next;
        x = p->data;
        free(p);
    }
    
    return x;
}

### Referensi:

- “Queue - Linked List Implementation - GeeksforGeeks,” GeeksforGeeks, Feb. 07, 2014. https://www.geeksforgeeks.org/queue-linked-list-implementation/ . [Diakses: 10-Maret-2025]
- “Introduction to Queue - Data Structure and Algorithm Tutorials,” GeeksforGeeks, Aug. 05, 2022. https://www.geeksforgeeks.org/introduction-to-queue-data-structure-and-algorithm-tutorials/ . [Diakses: 10-Maret-2025]
- Modul Algoritma dan Pemrograman - Chapter 6: Linked List. [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.

---

// Nama: Hasan Abdullah Azzam
// NMP : 2406428314
// TP 5 No 1
// deskripsi : program untuk mencari 3 nilai terbesar menggunakkan linked list

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

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

typedef struct{
	int top1;
	int top2;
	int top3;
}Top;

void add(Node **head, int data){
	Node *temp = (Node *)malloc(sizeof(Node));
	
	if(temp == NULL){
		printf("error");
		return;
	}
	
	temp->data = data;
	temp->next = *head;
	*head = temp;
}

Top cekTop(Node *head){
	
	Node *temp = head;
	Top data;
	
	data.top1 = 0;
	data.top2 = 0;
	data.top3 = 0;
	
	while(temp != NULL){
		
		if(temp->data > data.top1){
			
			data.top3 = data.top2;
			data.top2 = data.top1;
			data.top1 = temp->data;
			
		}else if(temp->data > data.top2){
			
			data.top3 = data.top2;
			data.top2 = temp->data;
			
		}else if(temp->data > data.top3){
			data.top3 = temp->data;
		}
	                    
		temp = temp->next;
	}
	
	return data;
}

void printTop(Top data){
	printf("\n----------\n\n");
	printf("inilah 3 angka tertinggi :\n\n");
	printf("Top 1 = %d\n", data.top1);
	printf("Top 2 = %d\n", data.top2);
	printf("Top 3 = %d\n", data.top3);
	printf("\n--------------------\n\n");
}

void freeList(Node **head){
	Node *temp;
	
	while(*head != NULL){
		temp = *head;
		*head =  (*head)->next;
		free(temp);
	}
	
	*head = NULL;
}

int main(){
	int n, nilai;
	
	Top nilaiTop;
	
	Node *head = NULL;
	
	while(1){
		
		printf("masukkan jumlah angka (-1 = exit): ");
		scanf(" %d", &n);
		printf("\n----------\n");
		
		if(n == -1){
			printf("\nParogram Telah selesai, Terimkasih!!\n");
			freeList(&head);
			break;
		}
		
		for(int i=0; i < n; i++){
			printf("\nmasukkan angka ke-%d (x > 0): ", i+1);
			scanf(" %d", &nilai);
			add(&head, nilai);
		}
		
		nilaiTop = cekTop(head);
		
		printTop(nilaiTop);
		
		freeList(&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.

---

// Nama: Hasan Abdullah Azzam
// NMP : 2406428314
// TP 5 No 2
// deskripsi : program untuk mencari hasil dari function F=(MIN  + MAX)/2 menggunakkan queue
#include<stdio.h>
#include<stdlib.h>

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

typedef  struct Queue{
	Node *front, *rear;
}Queue;

void enqueue(Queue *que, int data){
	Node *temp = (Node *)malloc(sizeof(Node));
	
	if(temp == NULL){
		printf("error");
		return;
	}
	
	temp->data = data;
	temp->next = NULL;
	
	if(que->rear == NULL){
		que->front = que->rear = temp;
	}else{
		que->rear->next = temp;
		que->rear = temp;
	}
}

int higher(Queue *que){
	
	Node *sign = que->front;
	int max = sign->data;
	
	while(sign != NULL){
		
		if(max < sign->data){
			max = sign->data;
		}
		
		sign = sign->next;
		
	}
	
	return max;
}

int lower(Queue *que){

	Node *sign = que->front;
	int min = sign->data;
	
	while(sign != NULL){
		
		if(min > sign->data){
			min = sign->data;
		}
		
		sign = sign->next;
		
	}
	
	return min;
}

float rumus(int min, int max){
	float hasil = (min + max) / 2.00;
	
	return hasil;
}

void freeList(Queue *que){
	Node *temp;
	
	while(que->front != NULL){
		temp = que->front;
		que->front = que->front->next;
		free(temp);
	}
	
}


int main(){
	
	int n, nilai,max,min;
	float hasil;
	
	Queue *angka = (Queue *)malloc(sizeof(Queue));
	
	if(angka == NULL){
		printf("error");
		return 1;
	}
	
	angka->front = angka->rear = NULL;
	
	
	while(1){
		
		printf("masukkan jumlah angka (-1 = exit): ");
		scanf(" %d", &n);
		printf("\n----------\n");
		
		if(n == -1){
			printf("\nParogram Telah selesai, Terimkasih!!\n");
			break;
		}else if(n <= 0){
			printf("jumlah angka tidak boleh kurang dari sama dengan 0!!\n");
			continue;
		}
		
		for(int i=0; i < n; i++){
			printf("\nmasukkan angka ke-%d (x > 0): ", i+1);
			scanf(" %d", &nilai);
			enqueue(angka, nilai);
		}
		
		max = higher(angka);
		min = lower(angka);
		
		hasil = rumus(min, max);
		
		printf("\nhasil akhir dari rumus : %.2f \n",hasil);
		printf("\n--------------------\n\n");
		
		freeList(angka);
		angka->front = angka->rear = NULL;
		
	}
	
	free(angka);

	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.

---

// Nama: Hasan Abdullah Azzam
// NMP : 2406428314
// TP 5 No 3
// deskripsi : program untuk mengecek apakah suatu deret yng diberikkan WEll balance atau tidak, sesuai kriteria yang diberikkan dan menggunakkan stack
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct{
	int size;
	int top;
	char *s;
}Stack;

void push(Stack *stack, char data){
	if(stack->top == stack->size - 1){
		printf("stack penuh!!\n");
	}else{
		stack->top++;
		stack->s[stack->top] = data;
	}
}

int balance(char a , char b){
	if(a == '1' && b == '9') return 1;
	if(a == '2' && b == '8') return 1;
	if(a == '3' && b == '7') return 1;
	if(a == '4' && b == '6') return 1;
	if(a == '5' && b == '5') return 1;
	return 0;
}

int main(){
	char input[50];
	int balanced;
	
	Stack *deret = (Stack *)malloc(sizeof(Stack));
	
	if(deret == NULL){
		printf("error");
		return 1;
	}
	
	while(1){
		
		printf("\nmasukkan deret angka (1-9)(-1 = exit): ");
		scanf("%s",input);
		
		if(strcmp(input,"-1") == 0){
			printf("\nParogram Telah selesai, Terimkasih!!\n");
			break;
		}
		
		int len = strlen(input);
		
		deret->size = len;
		deret->top = -1;
		deret->s = (char * )malloc(len * sizeof(char));
		
		if(deret->s == NULL){
			printf("error");
			continue;
		}
		
		char temp = '\0';
		
		for(int i = 0; i < len; i++){
			
			if( input[i] == '1' || input[i] == '2' || input[i] == '3' || input[i] == '4'){
				push(deret,input[i]);
			}else if(input[i] == '5' && deret->s[deret->top] != '5'){
				push(deret,input[i]);
			}else{
				if(deret->top == -1){
					temp = input[i];
					printf("Deret tidak well-balanced karena ada angka %c diakhir\n",input[i]);
					break;
				}else{
					if(balance(deret->s[deret->top],input[i]) == 1){
						deret->top--;
					}else{
						temp = input[i];
						break;
					}
				}
			}
			temp = input[i];
		}
		
		if(deret->top == -1){
			
			printf("Output : True\n");
			printf("deret well-balanced\n");
			
		}else if(deret->top == 0){
			
			int x = 10 - (deret->s[deret->top] - '0'); 
			printf("Output : Fasle\n");
			printf("Deret tidak well-balanced karena tidak diakhiri %d untuk menutup %c",x,deret->s[deret->top]);
			
		}else if(deret->top == len-1){
			
			printf("Output : Fasle\n");	
			printf("Deret tidak well-balanced karena tidak ada yang menutup setiap angka");
			
		}else{
			
			int x = 10 - (deret->s[deret->top] -'0');
			printf("Output : Fasle\n");
			printf("Deret tidak well-balanced karena tidak diakhiri %d sebelum %c", x, temp);
			
		}

		printf("\n----------\n");
		free(deret->s);
	}
	
	free(deret);
	return 0;
}