Stack bisa dibilang sebagai array linear karena stack berupa tumpukan. Istilah dalam Stack yaitu LIFO ( Last In First Out) atau FILO (First In Last Out). Contoh dalam kehidupan sehari - hari seperti tumpukan buku atau piring.
Dalam Stack terdapat 2 variabel, yaitu TOP dan MAX.
Top digunakan untuk menunjukkan elemen paling atas dari Stack. sedangkan Max untuk menunjukkan jumlah data dalam Stack.
Jika Top = NULL maka berarti Stack kosong, jika Top = Max - 1 berarti Stack penuh.
Pada Stack, jika menambah data maka Top akan naik, tetapi jika ada hapus data maka Top akan turun.
Beberapa operasi pada Stack :
- is_empty(); = untuk mengecek stack kosong
- is_full(); = untuk mengecek stack penuh
- top(); atau peek(); = untuk kembali ke index top
- push(x); = untuk menambah x pada Top didalam stack
- pop(); = untuk menghapus data dari Top dalam stack
Representasi Stack dalam array:
Representasi Stack dalam Linked List:
Dalam Linked Stack, setiap node memiliki 2 bagian:
- 1 bagian untuk menyimpan data
- 1 bagiannya lagi untuk menyimpan alamat dari node selanjutnya
Start pointer pada linked list digunakan sebagai Top, dan semua penambahan serta pengurangan data dilakukan di node yang ditunjuk oleh TOP.
Code untuk Stack:
Untuk menambah data :
struct
stack *push (struct stack *top, int val){
struct stack *ptr;
ptr = (struct stack*) malloc (sizeof(struct
stack*));
ptr -> data = val;
if (top == NULL){
top = ptr;
top -> next = NULL;
} else {
ptr -> next = top;
top = ptr;
}
return top;
}
Untuk menghapus data :
struct
stack *pop (struct stack *top){
struct stack *ptr;
ptr = top;
if (top == NULL){
printf(“\n STACK UNDERFLOW”);
} else {
top = top -> next;
printf(“\nThe deleted value: %d”, ptr ->
data);
free(ptr);
}
return top;
}
Untuk menampilkan data :
struct
stack *display(struct stack *top){
struct stack *ptr;
ptr = top;
if (top == NULL){
printf(“\n STACK IS EMPTY”);
} else {
while(ptr != NULL){
printf(“\n%d”, ptr -> data);
ptr = ptr -> next;
}
}
return top;
}
Notasi Infix, Prefix, dan Infix
Prefix : operator ditulis sebelum operand
Infix : operator ditulis diantara operand
Postfix : operator ditulis setelah operand
Kita butuh notasi Prefix dan Postfix karena notasinya tidak membutuhkan kurung () untuk menghitungnya.
Prefix dan Postfix lebih mudah dihitung / dievaluasi oleh komputer.
Depth First Search (DFS) dan Breadth First Search (BFS)
Depth First Search merupakan algoritma untuk mencari didalam tree atau graph. DFS dimulai dari root hingga kebawah. Breadh First Search juga merupakan algoritma untuk mencari, bedanya dengan DFS, BFS mencari dengan menyebar kiri kekanan, sedangkan DFS mencari lurus hingga kedalaman.
Contoh DFS yang benar :
Contoh BFS :
No comments:
Post a Comment