Pertemuan 3 : Linked List Implementation II - 2101632225 - Hendy

Oleh

Stack

Stack adalah sebuah struktur data yang menyimpan elemennya secara berurutan dan menyerupai tumpukan yang berisi elemen maka semakin banyak elemen yang dimasukkan maka tumpukan data semakin tinggi keatas. Seperti namanya yaitu Stack, ketika kita memasukkan suatu elemen pertama kali maka elemen pertama tersebut adalah yang paling terakhir keluar (First In, Last Out) atau juga sebaliknya yaitu ketika kita memasukkan suatu elemen terakhir maka elemen tersebut yang paling pertama keluar (Last In, First Out).


Array Representation

Stack mempunyai 2 variabel yaitu TOP dan MAX :

TOP = Elemen teratas dari suatu struktur data yang disusun berdasarkan Stack (berdasarkan urutan Array yaitu dimulai dari index ke-0).

MAX = Index maksimum pada Stack.


Untuk mencari TOP maka kita bisa menggunakan rumus yaitu :

TOP = MAX - 1

Dari contoh diatas berarti MAX = 5, karena mempunyai 5 elemen. Untuk mencari TOP maka MAX dikurang 1 maka TOP dari data diatas yaitu pada index ke-4 yaitu 4. Berarti 4 adalah bagian teratas dari Stack


Jika tidak ada elemen maka TOP = NULL yaitu Stack mempunyai isi yang kosong dan tidak ada elemen apapun di dalam Stack tersebut.


Stack Operation

Operasi Stack terdiri dari 3 yaitu :
  1. Push(x) = berfungsi untuk memasukkan data atau menambah elemen, x yaitu berupa angka yang ingin kita masukkan ke data
  2. Pop() = untuk menghapus elemen atau data
  3. Top() = untuk mengembalikkan data pada bagian paling atas Stack


Infix, Postfix, and Prefix Notation

Terdapat 3 notasi aritmatika yaitu :
  1. Prefix Notation. contoh : *410
  2. Infix Notation. contoh : 4*10
  3. Postfix Notation. contoh : 410*
Komputer hanya bisa mengoperasikan berdasarkan Prefix dan Postfix saja.


Rumus untuk mengubah Infix menjadi Prefix dan Postfix menjadi lebih mudah :

Operand = 5,4,10 (berupa angka).
Operator = +, /, *, -, dan lain lain.

Prefix = Operator -> Left Operand -> Right Operand
Postfix = Left Operand -> Right Operand -> Operator

Postfix Notation akan scan dari kiri ke kanan sedangkan kalau Prefix Notation akan scan dari kanan ke kiri untuk menghitungnya.



Depth First Search (DFS)

Depth First Search adalah sebuah algoritma untuk mencari sebuah data di dalam tree atau graph.
Depth First Search menggunakan Stack yaitu dimulai dari yang paling bawah atau akar dari sebuah pohon yaitu A. lalu A bercabang kemudian lanjut lagi dengan dimasukkannya B dan C. Kemudian A dapat dibebaskan. Karena B bercabang maka C dahulu yang dibebaskan. Kemudian dari B terdapat masukkan lagi yaitu D dan E dan kemudian B bisa dibebaskan. Karena Stack menggunakan metode Last In First Out, maka E yang dikeluarkan dahulu kemudian dilanjutkan dengan D.

Hasilnya yaitu : A,C,B,E,D (sesuai urutan yang dikeluarkan atau pop).


Queue

Queue adalah suatu struktur data yang menyimpan elemennya berdasarkan aturan urutan dan hampir sama dengan Stack. Tetapi, Queue menggunakan metode yaitu First In, First Out atau sebaliknya yaitu Last In, Last Out.

Queue mempunyai 2 variabel yaitu :
  1. Front = Paling depan yang merupakan index paling pertama
  2. Rear = Paling belakang yang merupakan index paling terakhir
Dari gambar diatas berarti Front = 0 dan Rear = 4

Jika Front = Rear = Null yang menandakan queue kosong dan tidak terdapat elemen atau data sedikitpun.



Queue Operation

Queue Operation terdapat 3 yaitu :
  1. Push(x) = Memasukkan data
  2. Pop() = Menghapus data
  3. Front() = Elemen paling pertama akan ditampakkan atau dikembalikkan


Circular Queue

Pada Queue biasa, ketika kita ingin menambahkan data yang baru pada Queue sudah penuh. Maka data tidak bisa lagi ditambahkan karena sudah penuh dan tidak ada tempat kosong lagi walaupun ketika data yang pertama kali kita masukkan sudah dihapus atau dihilangkan (berbentuk batang)


Berbeda dengan Circular Queue yang berbentuk lingkaran, Front (bagian paling depan) dan Rear (bagian paling belakang) saling terhubung. Misalnya data dari gambar diatas ditambahkan, jadi pada index ke-5 yaitu 60 maka Rear berubah menjadi 60. Jika pada index ke-0 yaitu 10 dihapus maka index ke-1 menjadi Front.

Lalu jika pada index ke-6 dan ke-7 ditambahkan data 70 dan 80, maka kita bisa menambahkan data lagi pada index ke-0 karena data awalnya yaitu 10 telah dihapus dan bisa digunakan kembali. Jadi pada Circular Queue, kita bisa mengubah-ubah Front dan Rear dan juga bisa menambahkan data baru dengan cara menghapus data yang paling pertama.



Breadth First Search

Breadth First Search (BFS) hampir sama dengan Depth First Search (DFS) yaitu mulai dari yang paling bawah atau dari akar suatu tree atau pohon.



Breadth First Search (BFS) menggunakan Queue yaitu First In maka First Out jadi yang data yang pertama kali masuk maka data tersebutlah yang keluar duluan. Seperti contoh diatas, pertama adalah A kemudian dari A tersebut terdapat B dan C kemudian A bisa dilepas. Selanjutnya B mempunyai cabang yaitu D dan E kemudian B dan C bisa dihilangkan. Karena Queue, maka D dahulu yang keluar kemudian E yang keluar.

Maka Hasilnya : A, B, C, D, E



Terima kasih sudah membaca post ini yang merupakan rangkuman pembelajaran saya pada pertemuan ketiga belajar mengenai Data Structure. Semoga informasi ini bermanfaat bagi kalian semua. Terima Kasih.

LIHAT JUGA : Pertemuan 4 : Introduction to Tree, Binary Tree, and Expression Tree - 2101632225 - Hendy

Komentar

Posting Komentar

Postingan populer dari blog ini

Pertemuan 1 : Array, Pointer, and Introduction to Data Structure - 2101632225 - Hendy

Oleh
Gambar
Data Structure adalah suatu cara untuk menyimpan dan mengatur data di komputer sehingga bisa diakses dan dimodifikasi secara efisien. Dengan demikian, Data Structure adalah kumpulan nilai data, hubungan antar mereka, dan fungsi atau operasi yang bisa diterapkan pada data. Array, Pointer, and Data Structure Array Array merupakan kumpulan dari data homogen yang mempunyai index atau kunci untuk setiap contentnya. Array bersifat homogen yaitu mempunyai tipe data yang sama (int / float / double atau tipe data lainnya). Index pada array dimulai dari 0 hingga seterusnya seperti contoh dibawah ini. Antara satu variabel dengan variabel lain di dalam array dibedakan berdasarkan subscript . int maks[5] = {60, 22, 21, 50, 47}; index ke-0 atau maks[0] = 60 index ke-1 atau maks[1] = 22 index ke-2 atau maks[2] = 21 index ke-3 atau maks[3] = 50 index ke-4 atau maks[4] = 47 Array dibagi menjadi dua yaitu : 1. Array dua dimensi (Two Dimensional Array) int
Baca selengkapnya

Pertemuan 5 : Tree & Binary Tree - 2101632225 - Hendy

Oleh
Gambar
Binary Tree Binary Tree adalah Tree yang dimana paling banyak hanya memiliki 2 anak atau setiap node maksimal memiliki 2 anak. Seperti dibawah ini. Binary Tree Perbedaan Graph dan Tree Graph dan Tree berbentuk mirip dan hampir sama. Tetapi yang membedakan hanyalah sedikit yaitu : - Graph : Boleh melakukan looping sehingga terkesan bebas - Tree : Tidak boleh looping dan tidak terkesan bebas dan juga terdapat banyak jenis Tree tergantung dari kondisi bentuk Tree. Graph Binary Search Tree Binary Search Tree merupakan metode untuk membuat tree dari elemen yang kita dapatkan dan harus berbentuk Binary Tree yaitu setiap node hanya boleh maksimal memiliki 2 anak dan juga memiliki suatu aturan tertentu. Kita bisa membuat Binary Search Tree berdasarkan elemen yang kita dapatkan. Berikut beberapa metode dari Binary Search Tree. Kita menentukan dan memilih sebuah ROOT. Jika Nilai selanjutnya lebih kecil dari ROOT maka letakkan pada sisi kiri dan jika ni
Baca selengkapnya

Pertemuan 2 : Introduction and Implementation Linked List I - 2101632225 - Hendy

Oleh
Gambar
Introduction to Linked List Struktur data Linked List  sering digunakan untuk mengimplementasikan struktur data lainnya. Sebuah Linked List adalah urutan node dimana masing-masing node menyimpan data sendiri dan sebuah pointer (alamat) ke lokasi node berikutnya. Satu node terhubung pada node yang lain dan membentuk seperti rantai terikat. Item terakhir dalam list mempunyai pointer atau link ke NULL , yang menunjukkan akhir rantai. Linked List  hampir sama dengan Array , itu tidak terbatas pada sejumlah elemen yang dinyatakan. Selain itu, tidak seperti Array  yang menyimpan data secara berkelanjutan dalam memori atau disk, Linked List dapat dengan mudah insert atau remove elemen tanpa realokasi secara keseluruhan struktur karena item pada data tidak perlu disimpan secara bersamaan. Pada bagian paling depan Linked List dinamakan Head yang berarti kepala yang merupakan pointer yang menunjukkan kepada elemen pertama dan pada bagian terakhir disebut Tail yang berarti eko
Baca selengkapnya

Pertemuan 4 : Introduction to Tree, Binary Tree, and Expression Tree - 2101632225 - Hendy

Oleh
Gambar
Introduction to Tree Tree merupakan koleksi dari satu node atau lebih node. Seperti namanya, tree yaitu berbentuk seperti pohon yang terbalik. Pohon memiliki akar lalu juga ranting yang saling terhubung-hubung. Dalam struktur data, bentuk tree seperti berikut. DEGREE of 6 = 2 (Karena 6 mempunyai 2 anak) HEIGHT = 4 (Karena sampai LEVEL 4 kedalamannya) PARENT of 9 = 5 CHILDREN of 6 = 5,1 1 SIBLING of 5 = 11 ANCESTOR of 6 = 7, 2 DESCENDANT of 6 = 5, 11 LEAF = Sebuah node yang tidak mempunyai children (anak) ROOT = Merupakan akar yaitu leluhur paling tinggi Binary Tree Binary Tree yaitu data struktur yang dimana maksimal hanya boleh mempunyai hingga 2 anak (cabang) dan juga terdapat left child dan right child. ROOT = 2 LEAF = 2, 5, 11, 4 (tidak mempunyai anak) Type of Binary Tree Perfect Binary Tree = Tree yang dimana disetiap LEVELnya mempunyai kedalaman yang sama (jumlah anak yang sama dan tidak berbeda dari yang lainnya). Complete Bina
Baca selengkapnya