Pertemuan 3 - Linked List Implementation II - 2101656553 - Laurensius Haryo R. P.

STACK

•  Last in first out: data yang terakhir masuk akan keluar pertama kali, dan sebaliknya.
•  Stack memiliki beberapa variabel:
•   TOP: tempat dimana data yang terakhir dinput berada.
•   MAX: jumlah maksimum yang bisa ditampung oleh sebuah stack.
•  TOP=NULL, berarti tidak ada data apapun di dalam stack.
•  TOP=MAX-1, berarti data yang ada distack sudah full.
•  Operasi dalam stack:
•   push(x): operasi ini berfungsi untuk menyetor x ke top dalam stack.
•   pop(): operasi ini berfungsi untuk menghapus data yang ada ditop.
•   top(): operasi ini berfungsi untuk return data yang ada ditop.

Infix, Postfix, Prefix Notation

• Prefix notation: operator ditulis sebelum operan, biasa disebut Reverse Polish notation
• Infix notation:  operator ditulis antara operan
• Prefix notation: operator ditulis setelah operan biasa disebut Polish notation
• Opertator: adalah symbol matematika untuk kali, bagi ,kurang tambah, dkk.
• Operand: ialah angka pada umumnya.

Contoh:

• Infix = 3 * 6
• Prefix = * 3 6
• Postfix = 3 6 *

• Infix     = 4 + 6 * (5 - 2) / 3
• Prefix   =+ 4 / *6 - 5 2 3
• Postfix =4 6 5 2 - * 3 / +

Depth First Search 

Depth First Search (DFS) adalah sebuah algoritma untuk melintasi dan mencari tree atau grafik struktur data. Satu dimulai pada akar (memilih beberapa simpul sewenang-wenang sebagai akar dalam kasus grafik) dan dieksplorasi sejauh mungkin sepanjang setiap cabang sebelum mundur.

DFS memiliki banyak aplikasi, seperti:

1. Menemukan titik artikulasi dan jembatan dalam grafik
2. Menemukan komponen yang terhubung
3. Topologi sorting
4. dll.

DFS dapat diimplementasikan dengan fungsi rekursif atau iteratif

prosedur menggunakan stack, hasil mereka mungkin memiliki sedikit perbedaan

perintah kunjungan tapi keduanya benar.

Breadth First Search

Breadth First Search (BFS) adalah sebuah algoritma untuk melintasi dan mencari tree atau grafik struktur data. Dimulai pada akar tree (atau beberapa simpul sewenang-wenang dari grafik, kadang-kadang disebut sebagai 'kunci pencarian') dan mengeksplorasi tetangga node pertama, sebelum pindah ke tetangga tingkat berikutnya.

Pelaksanaan non-rekursif ini mirip dengan pelaksanaan non-rekursif dari DFS, tetapi berbeda dari itu dalam dua cara:

1. menggunakan antrian bukannya stack,
2. cek apakah simpul telah ditemukan sebelum enqueueing vertex daripada menunda pemeriksaan ini sampai titik ini dequeued dari antrian.

Atribut jarak setiap titik (atau node) diperlukan misalnya ketika mencari jalur terpendek antara node dalam grafik. Pada awal algoritma, jarak dari setiap titik diatur ke INFINITY, yang hanya sebuah kata yang mewakili fakta bahwa node masih belum tercapai, dan karena itu tidak memiliki jarak dari titik awal. Kita bisa menggunakan simbol-simbol lain, seperti -1, untuk mewakili konsep ini.

Queue(Antrian) 

• Konsep queue yaitu FIFO. (First In First Out)
• Front: elemen yang terletak paling depan.
• Rear: elemen yang terletak paling belakang.
• Operasi dalam queue
• push(x) untuk mengisi item pada stack. (Enstack)
• pop() untuk membuang item pada stack. (Destack)
• front() data paling depan, biasa disebut peek.

Jenis Queue:

• Queue (First in first out)
• Circular Queue ( Kedua ujung antriannya terhubung)
• Queue yang melingkar dan akan balik ke data pertama setelah mencapai data terakhir.
• Priority Queue ( Antriannya berdasarkan prioritas)
• Data yang memiliki priority akan keluar terlebih dahulu.