Hay Gan, nie ane mau share sedikit pengetahuan ane dalam struktur data yang ane pelajari di kuilah ane semester 3, semoga bermanfaat dan mohon koreksi kesalahannya ya gan, okeh cekidot aja , :D
STRUKTUR
DATA TREE (POHON)
Tree structure (struktur pohon) sangat umum ditemui. Mulai dari struktur
folder/direktori di komputer Anda, sampai di setiap halaman web yang Anda
kunjungi (dokumen HTML memiliki struktur tree, setiap browser ada struktur tree
untuk DOM HTML). Beberapa contoh lain di mana Anda akan menemui struktur pohon:
- Memproses XML memerlukan pemahaman mengenai tree
- Pohon keluarga (family tree)
- Pohon organisasi
- Membuat pivot table yang kompleks memerlukan pemahaman
mengenai tree
Jika Anda menjadi administrator
database yang ingin bisa mengoptimasi sampai level penyimpanan, Anda harus tahu
struktur dasar seperti B-tree. Di beberapa database, misalnya Oracle, Anda bisa
mengatur ukuran blocksize untuk indeks B-tree.
Struktur graph (graf) juga
banyak digunakan sehari-hari:
- Node-node dalam sebuah jaringan membentuk graf, dan ini
perlu dipahami oleh administrator jaringan.
- Jalan dan lokasi di sebuah peta bisa dianggap sebagai
graf.
- Jaringan pertemanan (di Facebook, Friendster, dsb) juga
merupakan graf. Jika Anda membuat situs seperti itu, Anda perlu tahu
konsep graf.
Ada beberapa gabungan dari tree dan
graph. Jika Anda menjadi administrator jaringan, Anda perlu mengenal konsep
spanning tree untuk mengkonfigurasi STP (spanning tree protocol). Jika Anda
perlu membuat program peta sendiri, Anda perlu struktur data quad-tree untuk
mengakses dengan cepat node-node dalam graf yang Anda miliki.
Mungkin sebagian dari Anda berpikir:
itu kan hanya sebagian saja struktur data yang ada, bagaimana dengan yang lain?
Ketika belajar struktur data yang
sederhana akan membantu kita memahami struktur data yang lebih kompleks.
Misalnya jika seseorang tiba-tiba diminta mengimplementasikan tree dengan
pointer, dia biasanya akan bingung. Sementara jika diajari selangkah demi
selangkah mulai dari linked list, maka biasanya akan lebih mudah. Jadi fungsi
pertama struktur yang sederhana adalah untuk mempelajari struktur yang lebih
rumit. Dalam berbagai bahasa, struktur Linked List, Double Linked List, dsb
sudah masuk menjadi API standar.
Dalam mengimplementasikan suatu
struktur data, Anda bisa melihat kelebihan dan kekurangan masing-masing
struktur data. Misalnya linked list sangat efisien untuk menyimpan data yang
selalu ditambahkan di akhir. Ini akan membantu Anda memilih struktud data
terbaik untuk keperluan Anda (jadi Anda tidak selalu hanya memakai
java.util.Vector saja di Java). Jadi penggunaan struktur data spesifik berguna
untuk optimasi.
Misalnya Anda punya beberapa punya
struktur data yang hanya selalu ditambah saja di akhir. Struktur List akan
sangat efisien untuk hal ini. Jika Anda sudah tahu tepatnya berapa data yang
akan datang Anda bisa memakai array (atau std::vector di C++, atau
java.util.Vector di Java). Tapi jika Anda tidak tahu, setiap kali array mencapai
kapasitasnya, Anda perlu meresize memori (dan jika ternyata memori tidak cukup,
tanpa sepengetahuan Anda kadang perlu ada penyalinan data ke lokasi memori yang
baru). Jadi dalam kasus ini Anda bisa melihat bahwa List sederhana juga punya
kegunaan.
Kesimpulannya adalah: mempelajari
struktur data merupakan hal yang penting. Hanya di bidang yang sangat sempit
saja kita tidak perlu mempelajari struktur data. Dan bahkan dalam bidang yang
sempit itu, pemahaman struktur data akan bisa banyak membantu untuk membuat
program yang lebih baik.
STRUKTUR DATA QUEUE
Queue (antrian) adalah struktur data
dimana data yang pertama kali dimasukkan adalah data yang pertama kali bisa
dihapus. Atau bisa juga disebut dengan struktur data yang menggunakan mekanisme
FIFO (First In First Out). Queue dalam kehidupan sehari-hari seperti antrian
pada penjualan tiket kereta api, dimana orang yang pertama datang adalah orang
yang pertama kali dilayani untuk membeli tiket.
Jika ada orangbaru yang datang akan
membali tiket, maka posisinya berada pada urutan paling belakang dalam antrian
tersebut. Orang yang berada pada posisi terakhir dalam antrian adalah yang
terakhir kali dapat dilayani dan memperoleh tiket kereta api (kalau kurang
beruntung, maka akan kehabisan tiket). Contoh lain adalah nasabah yang antri di
teller bank, paket data yang menunggu untuk ditransmisikan lewat internet,
antrian printer dimana terdapat antrian print job yang menunggu giliran untuk
menggunakan printer, dsb. Istilah-istilah yang digunakan dalam queue (antrian)
Memasukkan data (insert) disebut juga dengan put, add, atau enqueue. Menghapus data (remove) biasa disebut dengan istilah delete, get, atau dequeue. Bagian belakang queue, dimana data bisa dimasukkan disebut dengan back, tail (ekor), atau end (akhir). Sedangkan bagian depan (front) queue dimana data bisa dihapus juga biasa disebut dengan istilah kepala (head).
Memasukkan data (insert) disebut juga dengan put, add, atau enqueue. Menghapus data (remove) biasa disebut dengan istilah delete, get, atau dequeue. Bagian belakang queue, dimana data bisa dimasukkan disebut dengan back, tail (ekor), atau end (akhir). Sedangkan bagian depan (front) queue dimana data bisa dihapus juga biasa disebut dengan istilah kepala (head).
Circular Queue
Di dunia nyata apabila seseorang sedang mengantri (misalnya antri tiket kereta api), apabila telah dilayani dan memperoleh tiket, maka ia akan keluar dari antrian dan orang-orang yang berada di belakangnya akan bergerak maju ke dapan. Kita bisa saja menggerakkan setiap item data ke depan apabila kita menghapus data yang terdepan, tetapi hal ini kurang efektif. Sebaliknya kita tetap menjaga setiap item data di posisinya, yang kita lakukan hanyalah merubah posisi front dan rear saja.
Yang menjadi permasalahan adalah apabila posisi rear berada pada bagian akhir dari array (atau pada nomor indeks yang terbesar). Meskipun ada bagian yang kosong di awal-awal array – karena mungkin data telah dihapus, data baru tidak bisa dimasukkan lagi karena rear-nya sudah tidak bisa bergerak lagi. Atau mungkinkah posisi rear nya bisa berpindah?
Di dunia nyata apabila seseorang sedang mengantri (misalnya antri tiket kereta api), apabila telah dilayani dan memperoleh tiket, maka ia akan keluar dari antrian dan orang-orang yang berada di belakangnya akan bergerak maju ke dapan. Kita bisa saja menggerakkan setiap item data ke depan apabila kita menghapus data yang terdepan, tetapi hal ini kurang efektif. Sebaliknya kita tetap menjaga setiap item data di posisinya, yang kita lakukan hanyalah merubah posisi front dan rear saja.
Yang menjadi permasalahan adalah apabila posisi rear berada pada bagian akhir dari array (atau pada nomor indeks yang terbesar). Meskipun ada bagian yang kosong di awal-awal array – karena mungkin data telah dihapus, data baru tidak bisa dimasukkan lagi karena rear-nya sudah tidak bisa bergerak lagi. Atau mungkinkah posisi rear nya bisa berpindah?
circular queueUntuk menghindari
permasalahan seperti itu (tidak bisa memasukkan data baru) – meskipun queue-nya
belum penuh, maka front dan rear-nya berputar (kembali) ke bagian awal array.
Struktur
Data Stack
Secara bahasa, Stack berarti
tumpukan. Jika dikaitkan dengan struktur data, Stack berarti sekumpulan data
yang organisasi atau strukturnya bersifat tumpukan atau menyerupai tumpukan.
Secara ilustrasi, stack dapat digambarkan dengan gambar di samping.
“Top “ merupakan pintu untuk keluar masuknya elemen – elemen stack. A, B, dan C merupakan suatukoleksi. Dari ilustrasi dapat digambarkan bahwa C merupakan elemen yang terakhir memasuki stack namunpertama keluar dari stack. Begitu sebaliknya dengan A. A merupakan elemen pertama yang memasukitumpukan namun terakhir saat keluar dari tumpukan.
Di dalam gambar juga terlihat urutan masuk dan keluar yang berkebalikan. Elemen yang masuk pertama akankeluar erakhir dan sebaliknya. Prinsip ini telah dikenal dalam struktur data dengan nama prinsip LIFO (Last In First Out).
Di dalam pengembangannya, stack dapat dikelompokkan menjadi dua bagian. Dua bagian tersebut yaitudan Double Stack. Single Stack
Single Stack
Single Stack atau Stack Tunggal adalah stack yang hanya terdiri dari satu koleksi. Bila stack inidirepresentasikan dengan array, maka pengisian dan penghapusan harus dilakukan bertahap dari indeksnya. TOP-
Di dalam proses single stack terdapat tiga macam proses utama, yaitu :
- Inisialisasi
- PUSH (Insert, Masuk, Simpan, Tulis)
- POP (Delete, Keluar, Ambil, Baca, Hapus)
Secara ilustrasi, stack dapat digambarkan dengan gambar di samping.
“Top “ merupakan pintu untuk keluar masuknya elemen – elemen stack. A, B, dan C merupakan suatukoleksi. Dari ilustrasi dapat digambarkan bahwa C merupakan elemen yang terakhir memasuki stack namunpertama keluar dari stack. Begitu sebaliknya dengan A. A merupakan elemen pertama yang memasukitumpukan namun terakhir saat keluar dari tumpukan.
Di dalam gambar juga terlihat urutan masuk dan keluar yang berkebalikan. Elemen yang masuk pertama akankeluar erakhir dan sebaliknya. Prinsip ini telah dikenal dalam struktur data dengan nama prinsip LIFO (Last In First Out).
Di dalam pengembangannya, stack dapat dikelompokkan menjadi dua bagian. Dua bagian tersebut yaitudan Double Stack. Single Stack
Single Stack
Single Stack atau Stack Tunggal adalah stack yang hanya terdiri dari satu koleksi. Bila stack inidirepresentasikan dengan array, maka pengisian dan penghapusan harus dilakukan bertahap dari indeksnya. TOP-
Di dalam proses single stack terdapat tiga macam proses utama, yaitu :
- Inisialisasi
- PUSH (Insert, Masuk, Simpan, Tulis)
- POP (Delete, Keluar, Ambil, Baca, Hapus)
Double Stack
Double Stack atau Stack Ganda adalah stack yang hanya terdiri dari dua single stack. Bila stack inidirepresentasikan dengan array, maka pengisian dan penghapusan harus melalui salah satu arah.
Di dalam proses double stack terdapat lima macam proses utama, yaitu :
- Inisialisasi
- PUSH1 (Proses Push untuk Single Stack pertama)
- POP1 (Proses Pop untuk Single Stack pertama)
- PUSH2 (Proses Push untuk Single Stack kedua)
- POP2 (Proses Pop untuk Single Stack kedua)
Algoritma dasar masing – masing proses adalah sebagai berikut :
Double Stack atau Stack Ganda adalah stack yang hanya terdiri dari dua single stack. Bila stack inidirepresentasikan dengan array, maka pengisian dan penghapusan harus melalui salah satu arah.
Di dalam proses double stack terdapat lima macam proses utama, yaitu :
- Inisialisasi
- PUSH1 (Proses Push untuk Single Stack pertama)
- POP1 (Proses Pop untuk Single Stack pertama)
- PUSH2 (Proses Push untuk Single Stack kedua)
- POP2 (Proses Pop untuk Single Stack kedua)
Algoritma dasar masing – masing proses adalah sebagai berikut :
INISIALISASI
|
top1 = -1; top2 = MAX_ARRAY;
|
PUSH1
|
top1 = top1 + 1; array[top1] = variable_tampung;
|
POP1
|
variable_tampung = array[top1]; top1 = top1 – 1;
|
PUSH2
|
top2 = top2 – 1; array[top2] = variable_tampung;
|
POP2
|
variable_tampung = array[top2];
top2 = top2 + 1;
|
