Kamis, 05 Maret 2020

Stack & Queue


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