Data Structure: Rangkuman-before-uts.

Stack & Queue

Stack

Pengertian Stack atau Tumpukan adalah suatu stuktur data yang penting dalam pemrograman yang mempunyai sifat LIFO (Last In First Out), barang yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack. Stack (Tumpukan) adalah list linier yang punya elemen puncaknya (TOP) dan Aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan dan Penghapusan selalu dilakukan di TOP.

Macam-macam operasi di stack :

Push(x) : memasukkan sebuah nilai ke dalam stack.
Pop() : menghapus nilai terakhir di posisi paling atas dari sebuah tumpukan.
Top() : posisi data teratas dari tumpukan.

Contoh-contoh 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.

Prefix, Infix, dan Postfix Notation.

Prefix : Operator yang di tulis sebelum operan. (operator operan operan)

Contoh: + 4 / *6 - 5 2 3

Infix : Operator yang ditulis diantara operan. (operan operator operan)

Contoh: 4 + 6 * (5 - 2) / 3

Postfix : Operator yang ditulis setelah operan. (operan operan operator)

Contoh: 4 6 5 2 - * 3 / +

Contoh penyelesaian dari persamaan prefix:

+ 4 / *6 - 5 2 3

+ 4 / *6 3 3

+ 4 / 18 3

+ 4 6

Contoh penyelesaian dari persamaan infix:

4 + 6 * (5 -2) / 3

4 + 6 * 3 / 3

4 + 18 /3

4 + 6

Contoh penyelesaian dari persamaan postfix:

4 6 5 2 - * 3 / +

4 6 3 * 3 / +

4 18 3 / +

4 6 +

============================================================

Queue

Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusannya saja, penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Queue(urutan) dapat diartikan adalah data yang pertama kali masuk maka data tersebut akan pertama kali keluar First in First Out (FIFO). Queue juga dapat diimplementasikan dengan penggunaan array atau linked list.

Seperti pada stake, queue juga memiliki beberapa operasi yang biasa digunakan seperti:

Push(x): menambahkan item x ke belakang antrian
Pop() : menghapus item dari depan antrian
Front(): mengungkapkan / mengembalikan item paling depan dari antrian.

I. Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut.

II. Algoritma DFS (Depth First Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Algoritma ini mirip dengan algorima BFS yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, kemudian berbalik kembali ke titik-titik sebelumnya sampai pada titik pertama.

Deques

Deques adalah suatu daftar/list dimana elemen yang digunakan untuk memasukkan(insert) atau menghapus(delete) di bagian kedua ujungnya yaitu head dan tail.

Priority Queue

Priority Queue adalah tipe data abstrak di mana masing-masing elemen diberi prioritas.

Aturan umum elemen antrian prioritas adalah:

Elemen dengan prioritas lebih tinggi adalah proses sebelum elemen dengan prioritas lebih rendah.
Dua elemen dengan prioritas yang sama diproses berdasarkan urutan kedatangan.

==============================================

Hashing Table

Apa itu Hashing

Hashing atau juga yang dikenal sebagai Hashing Algorithm adalah transformasi dari beberapa input menjadi fixed-value yang lebih pendek, dan simple dibanding dengan alamat data aslinya, yang mewakili input aslinya.

Hash atau Hashing berarti memenggal dan kemudian menggabungkan, dari konsep hashing tersebut Hash dapat membantu dalam proses mengindeksdan megambil data dalam database karena Memiliki keuntungan lebih cepat dalam insertion dan searching value yang ada di array, dari pada mencari dengan nilai aslinya.

Komponen yang harus dimiliki dalam hashing adalah:

key atau disebuh dengan hashed key adalah cara membuat karakter yang akan menjadi identifikasi baru dari value agar lebih mudah dicari datanya, dan akan dimasukan ke dalam hashing table.
Value adalah data yang dimasukkan ke dalam array.

Hash Table

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value didapatlah hash value. Tujuan dari hash table adalah untuk mempercepat proses pencarian dari banyak data yang disimpan. Karena dalam penyimpanan data di Hash table menggunakan key penyimpanan, sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) menjadi lebih cepat.

Ada beberapa cara hashing string menjadi key, diantaranya:

Mid-square
Division
Folding
Digit extraction
Rotating hash

Implementasi Hashing Table pada BlockChain
blockchain adalah implementasi peer-to-peer, yang berarti bahwa seluruh blockchain disimpan di setiap peer. List pada blockchain tersebut dapat terus bertambah hingga tak terhingga. Setiap blok memiliki nilai hash dari blok sebelumnya, waktu pembuatan blok, dan data. Desain blockchain yang seperti itu membuah tercegahnya resisten terhadapat pengubahan, karena setiap perubahan pada suatu blok akan membuat blok selanjutnya menjadi tidak valid. Untuk menambah keamanan, blockchain disimpan dalam jaringan terdistribusi dengan protokol peer-to-peer tertentu. Sehingga list blok tersebut terduplikasi di banyak server.

======================================================

Binary Tree

Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemen KHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untuk jelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree.

Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Istilah umum dalam tree :

1. Predecessor : node yang berada diatas node tertentu

2. Successor : node yang berada di bawah node tertentu

3. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama

4. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama

5. Parent : Predecessor level di atas suatu node

6. Child : successor satu level di bawah suatu node

7. Sibling : node-node yang memiliki parent yang sama dengan suatu node

8. Subtree : bagian dari tree yang berupa suatu node beserta descendant nya dan memiliki semua karakteristik dari tree tersebut

9. Size : banyaknya node dalam suatu tree

10. Height : banyaknya tingkatan/level dalam suatu tree

11. Root : satu-satunya node khusus dalam tree yang tak punya predecessor

12. Leaf : node-node dalam tree yang tak memiliki successor

13. Degree : banyaknya child yang dimiliki suatu node

Tipe - tipe binary tree

Perfect Binary Tree, yaitu Binary Tree yang tiap nodenya memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

Complete Binary Tree, Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child

Skewed Binar Tree, Binary Tree yang semua nodenya hanya memiliki satu child

Balanced Binary Tree, adalah jenis tree yang tidak ada daun yang lebih jauh dariakar daripada daun lainnya

Implementasi Binary Tree

Double pointer, maka fungsi insert / push, akan jadi seperti ini :

Perbedaan cara memanggil fungsi single dan double pointer adalah seperti ini :

o Contoh single: push(root,50);

o Contoh double: push2(&root,50);

Jika dilihat dari code di atas, code double pointer kita bisa melakukan passing by address. Sehingga ketika kita melakukan malloc atau memanggil newNode pada fungsi push2, maka root yang aslinya akan kena malloc juga. Berbeda dengan single pointer, jika kita melakukan node = newNode(a), maka root yang asli tidak akan ikut kena malloc, Karena ini merupakan passing by value.

Source:

https://study.com/academy/lesson/linked-lists-in-c-programming-definition-example.html
https://www.geeksforgeeks.org/circular-singly-linked-list-insertion/
https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/

https://en.wikipedia.org/wiki/Hash_table

https://tekslate.com/stack-using-linked-list-in-data-structures

https://www.chegg.com/homework-help/definitions/binary-s
https://en.wikipedia.org/wiki/Binary_tree

https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues earch-tree-3

https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm

https://www.geeksforgeeks.org/binary-tree-data-structure/