Stack & Queue
Stack
Stack(tumpukan)
artinya data yang pertama kali masuk, maka data tersebut paling akhir keluar.
Contoh
: tumpukan piring.
Stack
dapat diimplementasikan menggunakan array (ada batasannya) dan linked
list(tidak ada batasan/ unlimited).
Elemen
– elemen yang ada di stack dapat ditambahkan dan dihapus hanya dari satu ujung
yaitu bagian atas.
Data
disimpan dengan cara Last In First Out (LIFO).
Macam
– macam stack operations :
- Push(x) : memasukkan data ke dalam stack.
- Pop() : menghapus elemen yang terletak pada posisi paling atas dati sebuah tumpukan.
- Top() : mengembalikan(return) data teratas dari tumpukan.
Infix,
Postfix, dan Prefix Notation
Prefix : Operator yang di tulis sebelum operan (
operator operand operand)
Contoh
: * 4 10
Infix : Operator yang ditulis antara operan (
operand operator operand)
Contoh:
4 * 10
Postfix : Operator yang ditulis setelah operan (operand
operand operator)
Contoh
: 4 10 *
Contoh
menyelesaikan persamaan infix notation
4
+ 6 * (5 -2) / 3
4
+ 6 * 3 / 3
4
+ 18 /3
4
+ 6
10
Contoh
menyelesaikan persamaan postfix notation
4
6 5 2 - * 3 / +
4
6 3 * 3 / +
4
18 3 / +
4
6 +
10
Contoh
menyelesaikan persamaan prefix notation
+
7 – x 6 5 ^ 3 2
+
7 – x 6 5 9
+
7 – 30 9
+
7 21
28
Konversi
notasi infix ke postfix
Cara
Manual:
- Tentukan operator yang memiliki prioritas tertinggi
- Letakkan operator di belakang operand
- Lakukan sampai selesai
Contoh:
5 + 4 – 4 x 4 ^ 2 / 2
5 + 4 – 4 x 4 2 ^ / 2
5 + 4 – 4 4 2 ^ x / 2
5 + 4 – 4 4 2 ^ x 2 /
5 4 + - 4 4 2 ^ x 2 /
5 4 + 4 4 2 ^ x 2 / -
Konversi
notasi Infix ke prefix
Cara
Manual:
- Tentukan operator yang memiliki prioritas tertinggi.
- Tempatkan operator sebelum operand
- Lakukan sampai selesai
Contoh:
5 + 4 – 4 x 4 ^ 2 / 2
5 + 4 – 4 x ^4 2 / 2
5 + 4 – x 4 ^ 4 2 /2
5 + 4 – / x 4 ^ 4 2 2
+ 5 4 – / x 4 ^ 4 2 2
– + 5 4 / x 4 ^ 4 2 2
Depth
First Search (DFC)
Depth
First Search (DFC) adalah suatu algoritma untuk melintasi atau mencari di pohon
atau grafik. DFD dapat diimplementasikan dengan fungsi rekursif atau iterative
produce menggunakan stack, hasilnya mungkin memiliki sedikit perbedaan pesanan
kunjungan tetapi keduanya benar. Proses pencarian pada algoritma DFC akan
dilakukan pada semua anaknya terlebih dahulu, sebelum dilakukan pencarian ke
node – node yang selevel.
Queue
Queue(urutan)
artinya data yang pertama kali masuk maka data tersebut akan pertama kali
keluar.
Queue
dapat diimplementasikan dengan menggunakan array atau linked list.
Elemen
– elemen dalam queue ditambahkan di satu ujung yang disebut bagian belakang dan
dihapus dari ujung lain yang disebut depan.
Data
yang disimpan dengan cara First in First Out (FIFO).
Macam
– macam queue operations:
·
Push(x) : menambahkan item x ke belakang antrian
·
Pop() : menghapus item dari depan antrian
·
Front() : mengungkapkan / mengembalikan item
paling depan dari antrian.
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
Ada
2 aturan umum untuk memproses priority queue adalah:
- Elemen dengan prioritas lebih tinggi adalah proses sebelum elemen dengan prioritas lebih rendah.
- Dua elemen dengan prioritas yang sama diproses berdasarkan FCFS.
Breadth
First Search(BFC)
Breadth
First Search adalah metode pencarian yang dilakukan dengan mengunjungi setiap
node secara sistematis pada tiap setiap level hingga keadaan tujuan ditemukan. Atau
algoritma untuk melintasi atau mencari di pohon atau grafik.
Sumber : materi binus
Tidak ada komentar:
Posting Komentar