Rabu, 04 Maret 2020
Stack
Stack merupakan struktur data yang menyimpan elemen-elemennya secara teratur menggunakan prinsip LIFO (Last in First out). Sesuai dengan artinya secara langsung, dalam prinsip LIFO data yang terakhir kali dimasukkan akan menjadi yang pertama saat dikeluarkan.Stack adalah struktur data linear yang dapat diimplementasikan dengan menggunakan Array atau Linked List.
Stack dengan array
Stack memiliki 2 variable :- TOP : menyimpan alamat elemen paling atas dari stack
Catatan :- Jika TOP = NULL, maka stack kosong
- Jika TOP = MAX - 1, maka stack full
- Jika TOP = integer tertentu, maka insertion dan deletion akan berakhir pada posisi tersebut
- MAX : menyimpan jumlah maksimum elemen yang dapat ditumpuk oleh stack
Stack dengan linked
Pada Linked Stack, setiap node mempunyai 2 bagian:- satu menyimpan data
- satu menyimpan alamat node berikutnya
Operasi pada Stack
push() : menambah objek kedalam stackpop() : menghilangkan sebuah objek dalam stack
top() : mengembalikan TOP objek dari stack
Infix, Prefix, dan Postfix
Prefix : operator ditaruh sebelum operand- contoh : + 5 * 3 4 = 17
- contoh : 5 + 3 * 4 = 17
- contoh : 5 3 4 * + = 17
Evaluasi untuk postfix (secara manual)
Scan dari kiri ke kanan
7 6
5 x 3
2 ^ – + , scan sampai menemukan operator pertama
7 6
5 x
3 2 ^
– + , hitunglah 6 * 5
7 30
3 2 ^
– + , scan lagi hingga menemukan operator berikutnya
7 30
3 2 ^ – + , hitung 32
7 30
9 – + , scan lagi hingga menemukan operator berikutnya
7 30 9 –
+ , hitung 30 - 9
7 21 + , scan lagi
7
21
+ ,
hitung 7 + 21
28 , Jawaban akhir
Evaluasi untuk prefix (secara manual)
Scan dari kanan ke kiri
+ 7
– x 6
5 ^ 3 2 , Scan hingga menemukan operator pertama
+ 7
– x 6
5 ^
3 2 , hitung 32
+ 7
– x 6
5 9 , Scan lagi hingga menemukan operator berikutnya
+ 7
– x
6 5
9 , hitunglah 6 * 5
+ 7
– 30 9 , Scan hingga menemukan operator berikutnya
+ 7 – 30
9 , hitung 30 - 9
+ 7 21 , Scan hingga menemukan operator berikutnya
+
7 21 , hitung 7 + 21
28 , Jawaban akhirCara konversi infix ke postfix
- Cari operator dengan precedence (prioritas) tertinggi
- Taruh operator tersebut dibelakang operand
- Ulangi hingga selesai
Cara konversi infix ke prefix
- Cari operator dengan precedence (prioritas) tertinggi
- Taruh operator tersebut setelah operand
- Ulangi hingga selesai
Depth First Search
Depth First Search adalah algoritma yang dipakai untuk pencarian jalur pada tree atau graph. Pencarian mulai dari akar kemudian merambat sejauh mungkin sepanjang masing-masing cabang dari tree lalu barulah melakukan backtracking.Penggunaan DFS:
- menemukan titik artikulasi dan menjembatani pada grafik
- menemukan komponen yang terhubung
- Topological sorting
- dan lain-lain
Queue
Queue dapat diimplementasikan dengan array atau Linked List.Elemen-elemen pada queue disimpan dengan metode First in First out (FIFO), sehingga data yang pertama kali masuk akan dikeluarkan pertama kali juga. Data dimasukkan melalui salah satu ujung (rear) dan keluar pada ujung lainnya (front).
Queue memiliki 2 variabel yaitu front dan rear yang menunjuk posisi dimana deletion dan insertion dilakukan.
Queue dengan Linked
Dalam linked queue setiap elemen memiliki 2 bagian:- satu menyimpan data
- satu menyimpan alamat untuk elemen berikutnya
Operasi dalam queue
- push() : menambah data pada rear
- pop() : menghilangkan data pada front
- front() / peek : mengembalikan value data paling depan dari queue
Circular Queue
Definisi dari circular queue sama saja dengan queue hanya saja posisi terakhir dihubungkan kembali dengan posisi awal.Pengaplikasian Queue
- Deques
- Priority Queue
- Breadth First Search
Deques
Deques (double-ended queue) adalah list dimana elemen dapat ditambahkan atau dihapus melalui ujung manapun.Dikenal juga dengan nama head-tail Linked List karena elemen dapat ditambahkan atau dihapus dari front (head) atau back / rear (tail).
Dua macam Deques:
- Input Restricted Deque : dalam deque ini hanya deletion yang dapat dilakukan dari kedua ujung
- Output Restricted Deque : dalam deque ini hanya insertion yang dapat dilakukan dari kedua ujung
Priority Queue
Priority queue adalah tipe data abstrak yang mirip dengan queue biasa. Namun, tiap elemen memiliki prioritas sendiri.Elemen dengan prioritas lebih tinggi akan diproses terlebih dahulu sebelum elemen dengan prioritas lebih rendah.
Elemen dengan tingkat prioritas yang sama akan diproses sesuai dengan urutan data yang pertama kali muncul / first come first serve (FCFS).
Breadth First Search
BFS sama saja dengan DFS, bedanya data structure yang digunakan adalah queue bukan stack.