Stack = Tumpukkan
* Konsep
Last In First Out (LIFO), terakhir masuk pertama keluar
* Implementasi
- Perhitungan aritmatika postfix
- Back tracking (Depth First Search / DFS)
- Recursive
- Mengubah decimal menjadi biner
* Operasi
- Push (x) = Memasukkan data / push ke index x
- Pop() = Delete data dari paling atas
- Top() / Peek() = Mengambil (mereturn) nilai paling atas (tail)
Queue = Antrian
* Konsep
First In First Out (FIFO), pertama masuk pertama keluar
* Implementasi
- Sistem antrian
* Queue yang diterapkan dengan array akan memungkinkan bermasalah pada kapasitas. Bila data yang masuk melebihi kapasitas, maka data tidak dapat memasuki queue.
* Circular Queue adalah solusi untuk masalah di atas. Konsep ini mengulang pemasukkan data dari awal sehingga data pertama(Head) akan di timpa dengan data baru
BFS & DFS
* Breadth First Search
Algoritma pencarian data secara melebar dengan mengunjungi semua node yang bertetangga dan dilanjutkan dengan node level selanjut nya, begitu seterus nya hingga habis
* Depth First Search
Berbeda dengan BFS, DFS akan memasuki setiap akar(root) dari tiap node sampai ketemu dengan data yang dicari. Bila tidak bertemu ia akan lanjut ke tetangga nya.
Prefix, Postfix, Infix
* Prefix = Penulisan operasi aritmatika dengan meletakkan semua operator di depan dan operand di belakang nya
contoh = +ab, dibaca a+b
* Postfix = Penulisan operasi aritmatika dengan meletakkan semua operator di belakang dan operand di depan nya
contoh = ab+, dibaca a+b
*Infix = Penulisan operasi aritmatika biasa dan untuk precedence menggunakan kurung buka-tutup
contoh = penulisan notasi matematika biasa
*3 jenis penulisan ini bertujuan untuk mengatur precedence dalam operasi aritmatika pada bahasa pemrograman
*Postfix dan Prefix tidak menggunakan operator kurung buka-tutup sehingga dapat mempercepat komputasi, karena infix yang menggunakan kurung buka-tutup akan menyebabkan komputer mencari kurung buka-tutup terlebih dahulu sebelum memulai perhitungan
*rumus
Pre = opr opd opd
Post = opd opd opr
In = opd opr opd
Contoh soal prefix, postfix, infix
Infix = ((1+3) / (100*5) ^ 30)
Prefix? Postfix?
jawab
Prefix =
+ 1 3
+ 1 3 * 100 5
+ 1 3 ^ * 100 5 30
/ + 1 3 ^ * 100 5 30
Postfix =
1 3 +
1 3 + 100 5 *
1 3 + 100 5 * 30 ^
1 3 + 100 5 * 30 ^ /
Source :
* https://www.w3schools.in/wp-content/uploads/2016/09/Data-Structures-Algorithms-Stack.png
* https://id.wikipedia.org/wiki/Stack_(struktur_data)
* https://socs.binus.ac.id/2018/12/21/stack/
* https://www.w3schools.in/data-structures-tutorial/queue/
* https://socs.binus.ac.id/2018/12/21/queue/
* https://www.mahirkoding.com/struktur-data-queue-dan-implementasinya/
* https://piptools.net/algoritma-bfs-breadth-first-search/
* http://chandra-mahardika.blogspot.com/2015/10/materi-prefix-infix-dan-postfix.html
Tidak ada komentar:
Posting Komentar