Chrystopher's Blog

Sesi 3 :

Konsep Stack
Stack adalah struktur data penting yang menyimpan elemennya secara berurut.
Konsepnya :
1. Stack adalah struktur data linear yang bisa diimplementasikan dengan array atau linked list.
2. Elemen di dalam stack ditambahkan dan dihapus hanya dari salah satu ujung yang disebut top.
3. Data disimpan dalam bentuk LIFO (Last In First Out) yaitu data yang masuk terakhir, keluar terlebih dahulu.

Representasi Array
Stack mempunyai 2 variabel yaitu :
1. TOP yang digunakan untuk menyimpan address dari elemen paling atas dari stack.
2. MAX yang digunakan untuk menyimpan elemen maksimum yang bisa ditahan stack.

Jika TOP = NULL, berarti stack-nya kosong.
Jika TOP = MAX – 1, berarti stack-nya penuh.

0       1      2      3      4       5      6       7      8
Jika TOP = 4, maka insertion (pemasukan) dan deletion (penghapusan) akan dilakukan pada posisi ini.

Representasi Linked List
1. Cara membuat stack dengan array lebih mudah, tapi kekurangannya adalah array harus dinyatakan dengan beberapa fixed size (ukuran tetap).
2. Dalam linked list, setiap node harus punya 2 bagian :
– Satu yang menyimpan data
– Satu yang menyimpan address dari node berikutnya
3. Pointer START pada linked list digunakan sebagai TOP.
4. Semua insertion dan deletion diselesaikan pada node yang ditunjuk oleh TOP.
5. Jika TOP = NULL, berarti stack-nya kosong.

Operasi Stack
1. push(x) : menambahkan item x ke bagian top stack.
2. pop() : menghapus item dari bagian top stack.
3. top() : menampilkan/mengembalikan item top dari stack.

Catatan : top dikenal juga dengan peek (puncak).
Contoh Operasi Stack :

Aplikasi Stack
1. Notasi Infix, Postfix, dan Prefix
Ada 3 notasi aritmetik yang diketahui, yaitu :
– Notasi prefix, dikenal juga dengan notasi Polandia terbalik.
– Notasi infix (sering digunakan).
– Notasi postfix, dikenal juga dengan notasi Polandia.

Prefix : operator ditulis sebelum operand
Infix : operator ditulis di antara operand
Postfix : operator ditulis setelah operand

Kenapa kita butuh notasi prefix/postfix?
– Notasi prefix dan postfix tidak memerlukan tanda kurung () untuk memprioritaskan urutan operator.
– Prefix dan postfix lebih mudah untuk dihitung oleh komputer.

2. Konversi Infix ke Postfix
Cara Manual :
Algoritma :
1. Cari operator yang memiliki prioritas tertinggi.
2. Letakkan operator itu di belakang (setelah) operand.
3. Ulangi sampai selesai.

Menggunakan Stack :
Algoritma :
Scan string dari kiri ke kanan, untuk setiap karakter dalam string :
1. Jika operand, tambahkan ke string postfix.
2. Jika tanda kurung pembuka “(“, push ke stack.
3. Jika tanda kurung penutup “)”, pop stack hingga ketemu tanda kurung pembuka. Tambahkan setiap elemen yang dipop ke string postfix.
4. Jika operator, pop ketika elemen top dari stack memiliki precedence (prioritas) yang lebih tinggi atau sama dari karakter yang discan. Tambahkan setiap elemen yang dipop ke string postfix. Push karakter yang discan ke dalam stack.

3. Konversi Infix ke Prefix
Cara Manual :
Algoritma :
1. Cari operator yang memiliki prioritas tertinggi.
2. Letakkan operator itu sebelum operand.
3. Ulangi sampai selesai.

Menggunakan Stack :
Caraya mirip dengan konversi dari infix ke postfix, tetapi di sini string-nya discan dari kanan ke kiri.

4. Depth First Search
Depth First Search (DFS) adalah algoritma untuk traversing (melintasi) atau searching (mencari) dalam tree atau graph (grafik).
DFS memiliki banyak aplikasi seperti :
– Menemukan titik artikulasi dan bridge (jembatan) dalam graph.
– Menemukan komponen yang terhubung.
– Penyortiran topologi, dan lain sebagainya.

DFS dapat diimplementasikan dengan fungsi rekursif atau iteratif prosedur menggunakan stack, hasil keduanya mungkin memiliki sedikit perbedaan pada visiting order (susunan kunjungan), tapi keduanya benar.

Queue
Queue adalah struktur data penting yang menyimpan elemennya secara berurut.
– Queue bisa diimplementasikan baik menggunakan array maupun linked list.
– Elemen dalam queue ditambahkan pada suatu ujung yang disebut rear dan dihapus dari ujung lainnya yang disebut front.
– Data disimpan dengan cara First In First Out (FIFO) yaitu data yang pertama masuk, keluar terlebih dahulu. Inilah perbedaan utama antara Stack dan Queue.

Representasi Array
Queue memiliki 2 variabel yaitu front dan rear yang menunjuk ke posisi dimana deletions dan insertions bisa dilakukan masing-masing.

Representasi Linked List
1. Mirip dengan Stack, cara membuat queue menggunakan array mudah, tapi kekurangannya adalah array harus dideklarasi dengan sejumlah fixed size (ukuran tetap).
2. Dalam linked queue, setiap elemen memiliki 2 bagian, yaitu :
– Satu yang menyimpan data
– Satu lagi yang menyimpan alamat dari elemen next (berikutnya).
3. Pointer START dari linked list digunakan sebagai FRONT.
4. Semua insertion akan dilakukan pada REAR, dan semua deletion akan dilakukan pada ujung FRONT.
5. Jika FRONT = REAR = NULL, berarti queue-nya kosong.

Operasi Queue
1. push(x) : menambahkan item x ke belakang queue.
2. pop() : menghapus item dari depan queue.
3. front() : menampilkan/mengembalikan banyak item front dari queue.

front dikenal juga sebagai peek (puncak).

Circular Queue
1. Kita bisa wrap-around index L dan R
2. Jika R mencapai MAXN, maka set R sebagai 0, lakukan hal yang sama dengan L.
3. Dikenal juga sebagai circular queue.

Aplikasi Queue
1. Deques
Deque adalah list (daftar) yang elemennya bisa dimasukkan atau dihapus pada end (ujung) manapun.
Dikenal juga dengan linked list head-tail, karena elemennya bisa ditambahkan atau dihapus dari front (head) atau back (tail).

2 varian dari double-ended queue :
1. Input restricted queue
Dalam dequeue ini, insertion hanya bisa dilakukan pada salah satu dequeue sedangkan deletion bisa dilakukan dari kedua end (ujung).

2. Output restricted queue
Dalam dequeue ini, deletion hanya bisa dilakukan pada salah satu dequeue sedangkan insertion bisa dilakukan dari kedua end (ujung).

2. Priority Queues
Priority Queue adalah tipe data abstrak di mana setiap elemennya diberi prioritas.
Aturan umum memproses elemen dari priority queue bisa dijabarkan :
– Sebuah elemen dengan prioritas yang lebih tinggi diproses sebelum elemen dengan prioritas yang lebih rendah.
– Dua elemen dengan prioritas yang sama diproses berdasarkan first come first served (FCFS) yang berarti yang datang terlebih dahulu, dilayani terlebih dahulu.

Priority queue setelah insertion dari node baru :

Angka prioritas yang lebih rendah berarti prioritas yang lebih tinggi.

Deletion adalah proses yang sangat sederhana dalam hal ini. Node pertama dari list akan dihapus dan data dari node tersebut akan diproses terlebih dahulu.

3. Breadth First Search
Breadth First Search (BFS) seperti DFS juga merupakan algoritma untuk traversing (melintasi) atau searching (mencari) dalam tree atau graph.

BFS memiliki banyak aplikasi seperti :
– Menemukan komponen yang terhubung dalam graph.
– Menemukan jalur terpendek dalam graph tanpa bobot.
– Metode Ford-Fulkerson untuk menghitung arus maksimum, dan lain sebagainya.

Perbedaan antara implementasi iteratif DFS dengan BFS hanya pada struktur data yang digunakan. DFS menggunakan stack, sedangkan BFS menggunakan queue.