STACK
(Tumpukan)
A. Pengertian Stack (Tumpukan)
Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi ATAS (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.
Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack. Tumpukan disebut juga “Push Down Stack” yaitu penambahan elemen baru (PUSH)ndan penghapusan elemen dari tumpukann(POP). Contoh pada PDA (Push Down Automaton). Sistem pada pengaksesan pada tumpukan menggunakn system LIFO (Last In First Out), artinya elemen yang terakhir masuk itu yang akan pertama dikeluarkan dari tumpukan (Stack). Ilustrasi tumpukan (Stack) dapat digambarkan seperti tumpukan CD atau tumpukan sate. Stack merupakan suatu susunan koleksi data dimana dapat ditambahkan dan dihapus selalu dilakukan pada bagian akhir data, yang disebut dengan Top Of Stack.
Sebelum struktur data tumpukan ini bisa digunakan, harus dideklarasikan dahulu dalam kamus data. Ada beberapa cara pendeklarasian struktur data ini, salah satunya dengan menggunakan tata susunan linear (larik) dan sebuah variable, yang dikemas dalam tipe data record. Stack (tumpukan) adalah struktur data bertipe record yang terdiri dari field elemen, bertipe larik/array dengan indek dari 1 sampai dengan MaksTum (Maksimum Tumpukan), atas, bertipe interger berkisar dari 0 (saat kosong) sampai dengan MaksTum (Maksimum Tumpukan).
B. Operasi – operasi pada Stack (Tumpukan)
Operasi yang sering diterapkan pada struktur data Stack (Tumpukan) adalah Push dan Pop. Operasi – operasi yang dapat diterapkan adalah sebagai berikut :
1. Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.
2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
5. MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
6. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
7. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.
Pada proses Push, Tumpukan (Stack) harus diperiksa apakah jumlah elemen sudah mencapai masimum atau tidak. Jika sudah mencapai maksimum maka OVERFLOW, artinya Tumpukan penuh tidak ada elemen yang dapat dimasukkan ke dalam Tumpukan. Sedangkan pada proses Pop, Tumpukan harus diperiksa apakah ada elemen yang hendak dikeluarkan atau tidak. Jika tidak ada maka UNDERFLOW, artinya tumpukan kosong tidak ada elemen yang dapat diambil.
C. Macam – macam Stack
1. Stack dengan Array
Sesuai dengan sifat stack, pengambilan atau penghapusan elemen dalam stack harus dimulai dari elemen teratas.
2. Double Stack dengan Array
Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.
QUEUE (ANTRIAN)
A. Definisi Queue (Antrian)
Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.
Tumpukan disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue jika diartikan secara harfiah, queue berarti antrian. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli tiket.
Istilah yang cukup sering dipakai apabila seseorang masuk dalam sebuah antrian adalah enqueue. Sedang istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.
B. Operasi-operasi pada Queue
1. Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.
2. Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.
3. EnQueue : berfungsi memasukkan data kedalam antrian.
4. DeqQueue : berfungsi mengeluarkan data terdepan dari antrian.
5. Clear : Menghapus seluruh Antrian
6. IsEmpty : memeriksa apakah antrian kosong
7. IsFull : memeriksa apakah antrian penuh.
Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data.
Yang perlu diperhatikan untuk membuat hash function adalah:
- Ukuran array/table size
- Key value/nilai yang didapat dari data
- hash value/hash index/indeks yang dituju
Binary Tree adalah sebuah struktur data yang berbentuk tree/pohon. Dimana dari pohon tersebut mempunyai turunan/anak di sebelah kiri dan kanan pohon. syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya dinamakan kiri dan kanan.
Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).
 |
| Ilustrasi Binary Tree |
D. Binary Search Tree
Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :
- PreOrder : Print data, telusur ke kiri, telusur ke kanan
- InOrder : Telusur ke kiri, print data, telusur ke kanan
- Post Order : Telusur ke kiri, telusur ke kanan, print data
Ilustrasi Binary Search Tree |
#include <stdio.h>
#include <stdlib.h>
//inisialisasi struct
struct data{
int number;
//pointer untuk menampung percabangan kiri dan kanan
data *left, *right;
}*root;
//fungsi push untuk menambah data
void push(data **current, int number){
//jika pointer current kosong maka akan membuat blok data baru
if((*current)==NULL){
(*current) = (struct data *)malloc(sizeof data);
//mengisi data
(*current)->number=number;
(*current)->left = (*current)->right = NULL;
//jika tidak kosong, maka akan dibandingkan apakah angka yang
//ingin dimasukkan lebih kecil dari pada root
//kalau iya, maka belok ke kiri dan lakukan rekursif
//terus menerus hingga kosong
}else if(number < (*current)->number){
push(&(*current)->left, number);
//jika lebih besar, belok ke kanan
}else if(number >= (*current)->number){
push(&(*current)->right, number);
}
}
//preOrder : cetak, kiri, kanan
void preOrder(data **current){
if((*current)!=NULL){
printf("%d -> ", (*current)->number);
preOrder(&(*current)->left);
preOrder(&(*current)->right);
}
}
//inOrder : kiri, cetak, kanan
void inOrder(data **current){
if((*current)!=NULL){
inOrder(&(*current)->left);
printf("%d -> ", (*current)->number);
inOrder(&(*current)->right);
}
}
//postOrder : kiri, kanan, cetak
void postOrder(data **current){
if((*current)!=NULL){
postOrder(&(*current)->left);
postOrder(&(*current)->right);
printf("%d -> ", (*current)->number);
}
}
//searching data
void search(data **current, int number){
//jika pointer current memiliki data
if((*current)!=NULL){
//cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
if(number<(*current)->number){
search(&(*current)->left,number);
//jika lebih besar, maka belok ke kanan
}else if(number>(*current)->number){
search(&(*current)->right,number);
//jika sama dengan, maka angka ketemu
}else{
printf("Found : %d", (*current)->number);
}
//jika tidak ada data lagi (not found)
}else{
printf("Not Found.");
}
}
void main(){
push(&root, 11);
push(&root, 22);
push(&root, 13);
push(&root, 15);
push(&root, 9);
inOrder(&root);
printf("\n");
preOrder(&root);
printf("\n");
postOrder(&root);
printf("\n");
search(&root,91);
getchar();
}
No comments:
Post a Comment