Pertemuan 3 - Notasi pada stack, Queue, DFS, BFS - 2101711122 - Bela Kristianti

Stack adalah struktur data penting yang menyimpan unsur-unsurnya secara teratur. Stack adalah struktur data linier yang dapat diimplementasikan dengan menggunakan array atau linked list.
Elemen dalam stack ditambahkan dan dihapus hanya dari satu ujung, disebut dengan top.
Data disimpan dalam cara Last In First Out (LIFO) yang berarti Benda yang terakhir masuk ke dalam

stack akan menjadi yang pertama keluar dari stack.

Stack memiliki dua variabel:
TOP yang digunakan untuk menyimpan alamat elemen paling atas dari stack
MAX yang digunakan untuk menyimpan jumlah maksimum elemen yang dapat disimpan stack
Jika TOP = NULL, maka menunjukkan bahwa stack kosong
Jika TOP = MAX - 1, maka stack sudah penuh

TOP = 4, insertion dan deletion akan dilakukan pada posisi ini

Operasi Stack

·     push (x) : digunakan untuk menaambah item pada bagian atas tumpukan.

·     pop () : digunakan untuk mengambil item dari tumpukan paling atas.

·     top () : mengembalikan item teratas dari stack.

Infix, Postfix, dan Prefix

Ada tiga notasi aritmatika yang diketahui :

1.   Notasi prefix (dikenal sebagai notasi Reverse Polish) : operator ditulis sebelum operand

2.   Notasi infix : operator ditulis antara operand

3.   Notasi postfix : operator ditulis setelah operand

Notasi tersebut terbentuk dari indikator :

·     Operand : data/nilai yang membantu dalam proses.

·     Operasi : fungsi yang digunakan dalam proses

Contohnya  :

Operand : angka dan huruf (abc..,123…)

Operator : Penjumlahan, pengurangan, perkalian, pembagian, kurung, pangkat (+,-,*,/,(),^)

Contoh :

Depth First Search (DFS) adalah algoritma untuk mencari pada pohon atau grafik. DFS memiliki banyak aplikasi, seperti: Finding articulation point and bridge in a graph, finding connected component, topological sorting.

DFS dapat diimplementasikan dengan fungsi rekursif atau prosedur iteratif dengan menggunakan stack, hasilnya mungkin memiliki sedikit perbedaan pada urutannya namun keduanya benar. Contoh : Urutannya adalah A,C,B, E, D

Stacks banyak digunakan untuk :

·     Membalik urutan data

·     Convert infix ke postfix

·     Convert postfix menjadi infix,

·     Backtracking problem

·     Sistem stack digunakan pada setiap fungsi rekursif,

·     Mengkonversi angka desimal ke dalam padanan binernya.

Queue adalah struktur data penting yang menyimpan unsur-unsurnya secara terurut.

Contoh : Orang-orang bergerak di atas eskalator, Orang-orang yang naik eskalator pertama akan menjadi orang pertama yang melangkah keluar dari situ.

Queue dapat diimplementasikan dengan menggunakan array atau linked list. Elemen dalam antrian ditambahkan di satu ujung disebut belakang dan dihapus dari ujung yang lain disebut front. Data disimpan dalam cara First In First Out (FIFO), ini adalah perbedaan utama antara stack dan queue.

Queue memiliki dua variabel, depan dan belakang yang mengarah ke posisi dimana penghapusan dan penyisipan bisa dilakukan masing-masing.

Operasi Queue
push (x) : digunakan untuk menambah item pada bagian belakang antrian.
pop () : digunakan untuk mengambil item pada bagian depan antrian.
top () : mengembalikan item terdepan dari antrian.

Ada 3 aplikasi yang menggunakan struktur data queue :

1.   Deques

Deque adalah daftar di mana elemen dapat disisipkan atau dihapus di kedua ujungnya. Hal ini juga dikenal sebagai daftar terkait kepala ekor, karena elemen dapat ditambahkan ke atau dikeluarkan dari bagian depan (kepala) atau belakang (ekor).

Dua varian dari double-ended queue, meliputi:

Input restricted deque : Dalam sisipan dequeue ini bisa dilakukan hanya di salah satu dequeue sementara penghapusan bisa dilakukan dari kedua ujungnya.

Output restricted deque : Pada penghapusan dequeue ini bisa dilakukan hanya pada salah satu dequeue sementara sisipan bisa dilakukan pada kedua ujungnya.

2.   Priority Queues

Priority queue adalah tipe data abstrak dimana masing-masing elemen diberi prioritas.

Aturan umum elemen :

Elemen dengan prioritas lebih tinggi diproses sebelum elemen dengan prioritas lebih rendah.

Dua elemen dengan prioritas yang sama diproses pada saat pertama datang pertama dilayani, dasar (FCFS)

3.   Breadth First Search

Breadth First Search (BFS) sama seperti DFS juga merupakan algoritma untuk mencari menggunakan pohon atau grafik. Contoh : Urutannya A, B, C, D, E

 








BFS memiliki banyak aplikasi, seperti:

·     Menemukan komponen yang terhubung dalam grafik

·     Menjelajahi jalur terpendek dalam grafik yang tidak tertahan

·     Metode Fulton untuk komputasi maximum flow

·     Perbedaan antara implementasi DFS dan BFS hanyalah struktur data yang digunakan. DFS menggunakan stack sementara BFS menggunakan queue.