Halo gaes..
Kali ini aku mau melanjutkan postinganku sebelumnya mengenai Stack dan Queue, buat kalian yang belum membaca postinganku mengenai stack dan queue, mungkin bisa coba kalian baca di link ini.
Ya, hari ini kita akan melanjutkan materi stack dan queue, namun kali ini materi yang akan kita pelajari tergolong sedikit dan mudah-mudahan bisa cepat selesai.
Oke, langsung saja kita mulai.
Implementasi Stack
Kalau kalian sudah baca postinganku sebelumnya mengenai stack dan queue, kalian tau kalau stack merupakan struktur data yang menggunakan paradigma LIFO, dimana elemen yang terakhir masuk adalah yang pertama keluar. Apa saja sih implementasi dari stack ini?
Ini dia…
- Mengecek apakah sebuah elemen merupakan palindrom
Untuk mengecek apakah sebuah elemen termasuk palindrom atau bukan, kita bisa memasukkan digit-digit pada elemen tersebut ke dalam stack, setelah itu kita mengeluarkan satu per satu elemen yang sudah dimasukkan tersebut sesuai dengan prinsip LIFO. Kalau sama, berarti palindrom, kalau beda, berarti bukan palindrom.
- Mengunjungi elemen-elemen pada graf dan tree dengan metode DFS (akan dibahas di lain kesempatan).
Pada DFS, child dari suatu tree/adjacent node pada suatu graf dikunjungi terlebih dahulu, sebelum kemudian parent dari vertex tersebut dikunjungi. Parent pada vertex tersebut di-push ke dalam sebuah stack, kemudian child juga di-push ke dalam sebuah stack hingga menemui vertex yang tidak memiliki edge ke vertex lain yang belum dikunjungi. Kemudian, vertex tersebut di-pop dan adjacent node lain dari parent yang sama pun dikunjungi dengan cara yang sama.
Pada tree, penerapan DFS antara lain preorder, inorder, dan postorder.
- Mengecek penggunaan tanda kurung yang benar
Untuk mengecek penggunaan tanda kurung yang benar, maka dilakukan operasi seperti pada gambar di bawah. Operasi ini merupakan salah satu operasi yang paling penting dalam mengembangkan sebuah compiler.
- Mengecek hasil operasi hitung baik secara prefix, infix, ataupun postfix.
Operasi Prefix, Infix, dan Postfix memiliki dasar yang sama dengan preorder, inorder, dan postorder pada binary tree. Istilah ini digunakan pada binary tree yang parent-nya adalah operasi hitung sedangkan child-nya adalah angka yang akan diproses, contohnya adalah sebagai berikut :
>> + 3 5 merupakan prefix
>> 3+5 merupakan infix
>> 3 5 + merupakan postfix
Bagaimana jika kita ingin mengkonversi prefix, infix, dan postfix? Kita membutuhkan stack untuk memprosesnya. Stack ini juga digunakan untuk mem-parse suatu operasi hitung yang sudah disusun dalam bentuk parse tree, di mana parse tree ini merupakan struktur data yang digunakan dalam aplikasi matematika yang saat ini populer digunakan untuk membantu mengerjakan soal.
- Stack Machine
Pada mata kuliah Organisasi dan Arsitektur Komputer, kita mengenal adanya Accumulator Machine, Register Machine, dan juga Stack Machine. Pada stack machine ini, terdapat operasi pushm, pushv, dan juga pop (sebenarnya ada beberapa operasi lain, tetapi yang akan dibahas di sini hanya 3 operasi tersebut). Pushm merupakan operasi untuk memasukkan suatu elemen dengan alamat memori tertentu, sedangkan pushv merupakan operasi untuk memasukkan suatu elemen dengan nilai tertentu.
- Disk Management dengan sistem LIFO
Implementasi Queue
Selain stack, queue juga punya beberapa implementasi nih, apa aja ya?
Ini dia
- Mengunjungi elemen-elemen pada graf dengan metode BFS, pada tree dengan metode level order.
Pada metode BFS, parent dikunjungi terlebih dahulu, kemudian child dikunjungi setelahnya. Dalam implementasinya, ketika suatu vertex dikunjungi, maka adjacent node/child dari vertex tersebut dimasukkan ke dalam queue, setelah itu vertex tersebut dikeluarkan dari queue.
- Proses scheduling pada sistem operasi dengan sistem FIFO
Pada proses scheduling dengan sistem ini, proses yang dijalankan adalah proses yang datang terlebih dahulu, walaupun proses tersebut bisa jadi memiliki waktu eksekusi yang lama. Dalam sistem FIFO, tidak dikenal istilah interruption karena yang datang terlebih dahulu akan dijalankan terlebih dahulu, berbeda dengan SJF yang mengenal istilah interruption, di mana proses yang sedang dijalankan dapat diinterupsi jika ada proses lain yang waktunya lebih singkat.
- Disk Management dengan sistem FIFO
Yah.. Sepertinya masih banyak implementasi lain dari Stack dan Queue dalam Ilmu Komputer, tapi ya karena keterbatasan waktu gak sempet lah kalau dibahas disini. Terima kasih telah membaca postingan ini, stay safe dan sampai jumpa.
Daftar Pustaka
https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/. Diakses tanggal 11 September 2020.
