Pengikut

Sabtu, 19 Juli 2014

Struktur Data

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:
  1. Memproses XML memerlukan pemahaman mengenai tree
  2. Pohon keluarga (family tree)
  3. Pohon organisasi
  4. 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:
  1. Node-node dalam sebuah jaringan membentuk graf, dan ini perlu dipahami oleh administrator jaringan.
  2. Jalan dan lokasi di sebuah peta bisa dianggap sebagai graf.
  3. 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).

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?

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)

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 :
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;
 

Tidak ada komentar:

Posting Komentar