CA01-002
Rangkuman Pertemuan 2 CA01
Linked List
Butuh malloc untuk alokasi value ke memory yang berbeda
Pointer next dibuat untuk menyimpan data setelahnya, struct data
untuk recursive
Indikator posisi awal dengan if head==NULL
Pergeseran dilakukan dengan next->curr
Tail->Next==NULL Sebagai penanda akhir list
Next adalah alamat curr setelah bergeser
Menghapus/pop dengan menggeser curr/tail ke alamat sebelumnya
struct node{
int
value;
struct
node* next;
} *head = NULL, *tail = NULL, *curr;
void push_head(int x){
curr =
(struct node*)malloc(sizeof(struct node));
curr->value
= x;
curr->next
= NULL;
if(head
== NULL){
head
= tail = curr;
}else{
curr->next
= head;
head
= curr;
}
}
void pop_head(){
if(head
== NULL){ // no data
puts("FAILED,
NO DATA");
}else
if(head == tail){ // 1 data
curr
= head;
free(curr);
head
= tail = NULL;
}else{
// >1 data
curr
= head;
head
= head->next;
free(curr);
}
}
void print(){
curr =
head;
while(curr
!= NULL){
printf("%d\n",
curr->value);
curr
= curr->next;
}
}
STACK & QUEUE
Perbedaan Dasar Stack dan Queue
Stack/tumpuk merupakan LIFO (Last In First Out) karena hanya memiliki head/kepala. Jika digambarkan, seperti tumpukan piring.
Jika ditambah, piring paling baru ada di paling atas, dan
saat diambil, piring paling atas lah yang terambil terlebih dahulu. Jika
diasumsikan hanya dapat mengambil/menambah satu piring secara berurutan, maka
Stack hanya mengenal kepala/Top/Head, dan piring-piring setelahnya.
Di sisi lain, Queue merupakan FIFO (First In, First Out),
karena memiliki head dan tail, jika digambarkan, seperti barisan piring
Jika ditambah, maka piring paling baru ada di paling belakang, sedangkan ketika diambil, piring paling depan yang diambil terlebih dahulu. Jika diasumsikan hanya dapat mengambil/menambah satu piring secara berurutan, maka Queue mengenal kepala/Top/Head barisan, ekor/tail/belakang barisan, dan piring-piring setelah ekor/sebelum kepala.
Stack
Stack dalam Data Structure merupakan struktur yang cara
penambahan/penghapusan melalui satu end saja, yaitu kepala/head. Seperti
penjelasan awal, Push/Insert data dimasukkan dari depan, begitu juga Pop/Delete
Kegunaan Stack
konsep Stack dalam aplikasi adalah undo/redo browser. Ketika
halaman baru dibuka, maka dilakukan insert, dan ketika undo, maka akan dilakukan
pop dari halaman sekarang/head. Konsep Stack untuk undo/redo juga diaplikasikan
di beberapa text editor.
Notasi Postfix, infix, dan prefix
Postfix, infix dan prefix adalah cara penulisan operasi
matematika. Postfix berarti operator ditulis setelah angka/operand, prefix
berarti operator ditulis sebelum operand, dan infix berarti ditulis diantara
operand. Adannya prefix/postfix karena kecepatan algoritma untuk menyelesaikan
proses tersebut memiliki Big-O Notation berupa O(N), tidak seperti infix yang memiliki
Big-O Notation berupa o(N)^2. Hal ini disebabkan komputer tidak perlu
memperhatikan tanda kurung/prioritas operand terlebih dahulu untuk melakukan
perhitungan.
Postfix
Prefix
Stack digunakan dalam melakuak perhitungan postfix/prefix,
juga mengubah infix ke profix/prefix.
perhitungan dengan
postfix
Stack digunakan sebagai tempat penyimpanan angka-angka yang
akan dihitung. Setiap kali ada operasi
yang dilakuka, operand akan di pop, dan hasil perhitungan akan di insert ke stack.
hal yang sama
dilakukan dengan perhitungan prefix. Berdasarkan operasi tersebut, maka
langkah-langkah yang dilakukan adalah:
1.
Push (2)
2.
Push (3)
3.
Pop (3) dan (2), push (3^2)
4.
Push (5)
5.
Push (6)
6.
Pop (6) dan (5), push (6*5)
7.
Pop (30) dan (9), push (30-9)
8.
Push (7)
9.
Pop (21) dan (7), push (21+7)
Stack juga digunakan untuk konversi infix ke prefix/postfix.
|
Expression
|
Stack
|
Output
|
Comment
|
|
5^E+D*(C^B+A)
|
Empty
|
-
|
Initial
|
|
^E+D*(C^B+A)
|
Empty
|
5
|
Print
|
|
E+D*(C^B+A)
|
^
|
5
|
Push
|
|
+D*(C^B+A)
|
^
|
5E
|
Push
|
|
D*(C^B+A)
|
+
|
5E^
|
Pop And
Push
|
|
*(C^B+A)
|
+
|
5E^D
|
Print
|
|
(C^B+A)
|
+*
|
5E^D
|
Push
|
|
C^B+A)
|
+*(
|
5E^D
|
Push
|
|
^B+A)
|
+*(
|
5E^DC
|
Print
|
|
B+A)
|
+*(^
|
5E^DC
|
Push
|
|
+A)
|
+*(^
|
5E^DCB
|
Print
|
|
A)
|
+*(+
|
5E^DCB^
|
Pop And
Push
|
|
)
|
+*(+
|
5E^DCB^A
|
Print
|
|
End
|
+*
|
5E^DCB^A+
|
Pop
Until '('
|
|
End
|
Empty
|
5E^DCB^A+*+
|
Pop
Every element
|
Konversi
Infix ke Prefix
Hasil konversi itu dibalik, sehingga hasil akhirnya
adalah +*+A^BCD^E5
DFS/Depth First Search
DFS adalah sebuah algoritma untuk mencari/berpindah dalah
sebuah graf/tree. Jika memungkinkan, DFS akan bergeser tanpa melewati garis
yang sama. DFS digunakan untuk menentukan graf Acyllic, topology sorting dll.
Queue
Queue dalam Data Structure merupakan struktur yang cara
penambahan/penghapusan melalui dua end, yaitu kepala/head dan ekor/tail. Push/Insert data dilakukan di head/kepala, dan
penghapusan dilakukan di ekor/tail.
Kegunaan Queue
Penggunaan Queue ada dalam CPU Scheduling, Multiprogramming,
dan asynchronous data transfer. Dalam sehari-hari, seperti urutan panggilan di
call center, dan antrian kasir.
Variasi Queue
Queue memiliki variasi lain yaitu Circular Queue, dimana
head dan tail tersambung, membentuk sebuah lingkaran
Deque
Deque, atau Deck. Deck adalah sebuah queue yang dapat di insert/delete
dari head, juga dari tail.
Ada dua jenis Deque, yaitu Input Restricted Deque, dan
Output Restricted Deque. Sesuai Namanya, Input restricted berarti insert
hanya dapat dilakukan di satu end, tetapi penghapusan data dapat dilakukan dari
kedua end, begitu juga kebalikannya dengan Output Restricted.
Priority Queue
Priority Queue adalah perkembangan lebih lanjut dari queue.
Priority Queue memiliki urutan dequeue dan enqueue sesuai dengan nilai yang
paling dicari. Semakin mendekati hasil, maka nilai itulahy yang akan
dikeluarkan terlebih dahulu
BFS/Breadth First Search
BFS adalah sebuah cara untuk menempuh graf/tree. Perbedaan
BFS dan DFS selain dari stack dan queue yang menjadi dasar, adalah cara
menempuh. DFS bergeser secara jalur, sedangakn BFS bergerak secara tingkatan.
BFS digunakan untuk menggunakan graf bipartite, jalur tempuh paling singkat,
P2P networks, dll.
Komentar
Posting Komentar