Halo, semuanya! Kali ini penulis akan
membahas tentang stack dan queue.
source: https://anasihite.files.wordpress.com/2016/01/stack.png?w=523&h=228&crop=1
1. Stack
Secara
harafiah, stack berarti tumpukan. Dalam struktur data, stack merupakan salah
satu metode pengaturan data yang menggunakan sistem Last In First Out (LIFO).
Data yang terakhir masuk, akan lebih dulu keluar/digunakan. Sebalikanya, data
yang pertama masuk, akan keluar/digunakan terakhir. Sebagai gambaran, ketika anda
menumpuk piring, piring yang pertama kali akan terletak di bawah piring kedua,
dan seterusnya sampai piring yang terakhir berada di paling atas. Kemudian, saat
anda ingin mengambil sebuah piring, tentunya anda akan mengambil piring yang
paling atas. Piring pertama tadi akan terus berada di paling bawah sampai
akhirnya mendapat giliran diambil.
Operasi-operasi
yang digunakan pada stack:
·
Push() à Menambah data baru ke
paling atas
·
Pop() à Menghapus data dari
paling atas
·
Top() à Mengambil data paling atas
(disebut juga peek)
Dalam pengoperasiannya, ada 3 jenis operasi
perhitungan:
·
Infix à operasi
perhitungan dengan susunan operand dan operator yang berurutan
Contoh: 4 + 6 (5-2) / 3
·
Prefix à operasi
perhitungan dengan susunan operator berada di sebelah kiri dari operand,
komputer akan memprosesnya dari kanan ke kiri.
Contoh: mengubah 4 + 6 (5-2) / 3 ke
prefix kita perlu mengetahui masing-masing tingkatan operator dari yang tertinggi
4 + 6 * (5 – 2) /
3 Operator ( ) merupakan operator tertinggi
- 5 2
4
+ 6 * (5 – 2) / 3 Operator * merupakan operator tertinggi
* 6 - 5 2
4
+ 6 * (5 – 2) / 3 Operator / merupakan operator tertinggi
/ * 6 – 5 2 3
4
+ 6 * (5 – 2) / 3 Operator
+ adalah operator terakhir
+ 4 / * 6 - 5 2 3
·
Postfix à operasi
perhitungan dengan susunan operator di sebelah kanan dari operand, komputer akan
memprosesnya dari kiri ke kanan
Contoh: mengubah 4 + 6 (5-2) / 3 ke postfix
kita perlu mengetahui masing-masing tingkatan operator dari yang tertinggi.
4 + 6 * (5 – 2) /
3 Operator ( ) merupakan operator tertinggi
5 2 -
4
+ 6 * (5 – 2) / 3 Operator * merupakan operator tertinggi
6 5 2 - *
4
+ 6 * (5 – 2) / 3 Operator / merupakan operator tertinggi
6 5 2 - * 3 /
4
+ 6 * (5 – 2) / 3 Operator
+ adalah operator terakhir
4 6 5 2 - * 3 / +
Mengapa kita menggunakan notasi prefix/postfix? Karena dalam pengoperasiannya, kita tidak memerlukan tanda kurung apapun untuk menentukan Presedence ataupun Associativity. Komputer juga akan lebih mudah untuk mengevaluasi operasi aritmatik tersebut.
Dalam mencari data pada stack, digunakan algoritma DFS (Depth First Search) yakni algoritma penelusuran yang dilakukan dengan menelusuri bagian dalam (akar) pada tree / graf.
source: https://he-s3.s3.amazonaws.com/media/uploads/9fa1119.jpg
Dari gambar di atas, dapat kita jabarkan algoritma dari DFS tersebut. DFS melakukan pencarian data dari paling kiri terlebih dahulu pada graf, lalu menuju ke bagian lebih dalam terlebih dahulu setelah angka 1 (sub-tree , dalam kasus ini, angka 2), kemudian melaju lebih dalam lagi ke angka 4 dan 5. Setelah itu, menuju angka disebelah angka 2, yaitu 3, dan alurnya adalah 1-2-4-5-3.
2. Queue
Secara
harafiah, queue berarti antrian. Queue merupakan salah satu metode pengaturan
data yang menggunakan sistem First In First Out (FIFO). Data yang pertama
masuk, akan lebih dulu keluar/digunakan. Sebaliknya, data yang terakhir masuk,
akan keluar/digunakan terakhir juga. Sebagai gambaran, ketika anda mengantri di
sebuah loket untuk membeli karcis, maka anda akan mengantri terlebih dahulu, ke
bagian paling belakang. Orang yang berada di paling depan akan dilayani
terlebih dahulu, dan akan pergi saat itu juga. Lalu dilanjutkan orang kedua,
sampai giliran anda (ketika tidak ada orang lagi) di bagian terakhir. Begitu
juga dengan data. Data yang dimasukkan pertama akan berada di posisi paling
depan/atas/kiri. Lalu ketika ingin menghapus data (pop) atau mengambil data paling
atas (top), maka data pertama yang masuk duluan tadi akan diproses di awal.
Operasi-operasi yang digunakan pada queue:
· Push() à Menambah data baru ke paling belakang
· Pop() à Menghapus data dari paling atas/depan
· Top() à Mengambil data paling atas/depan
Dari gambar tersebut, jika kita melakukan pop terus-menerus, make posisi L dan R akan semakin mundur ke belakang/kanan. Jika hasil ini terus berlanjut, saat posisi L dan R berada di bagian paling belakang, maka komputer akan menginstruksikan kalau data sudah penuh, padahal data kosong. Untuk mengatasi hal itu, digunakanlah sistem circular queue (sistem lingkaran) dimana posisi R saat sudah diujung, akan dipindahkan ke bagian paling depan/kiri (R = 0).
Deque (Double Ended Queue) à queue yang bisa menghapus/menambah dari bagian depan maupun belakang.
Deque memiliki 2 varian:
· Input restricted deque
Penambahan data hanya bisa dilakukan pada 1 ujung deque, sementara penghapusan dapat dilakukan pada 2 ujung.
· Output restricted deque
Penghapusan data hanya bisa dilakukan pada 1 ujung deque, sementara penghapusan dapat dilakukan pada 2 ujung.
Priority Queue à Kita bisa mengatur prioritas pada queue, sehingga elemen/data yang lebih tinggi prioritasnya akan lebih dulu diproses.
Dalam mencari data pada queue, digunakan algoritma BFS (Breadth First Search) yakni algoritma penelusuran yang dilakukan dengan menelusuri bagian anak pada tree / graf.
source: https://pythoninwonderland.files.wordpress.com/2017/03/graphorder.png
Dari gambar tersebut, BFS akan menelusuri dulu bagian yang sejajar. Setelah itu, baru masuk ke bagian lebih dalam dan menelusuri lagi bagian yang sejajar, begitu seterusnya hingga data ditemukan.
Prosesnya A-B-E-C-D-F-G.
Itu dulu pembahasannya. Maaf jika ada kesalahan kata. Terima kasih. Salam penulis.
No comments:
Post a Comment