Stack adalah
strukur yang bersifat LIFO yang mana mempunyai pengertian bahwa yang masuk
belakangan akan keluar duluan. Contohnya tumpukan batu bata, tumpukan buku di
perpustakaan, dan tumpukan tisu hasil produksi rumah tangga.
Stack dapat
diimplementasikan dengan menggunakan konsep Linked List. Bentuk dari
struct dari
head untuk stack dapat digambarkan sebagai berikut:
Perbedaan
mendasar antara stack dan Linked List adalah bahwa stack memiliki
operasi khusus
untuk memanipulasi elemen dalam stack tersebut. Operasi yang
dimaksud dalam
program C dapat diimplementasikan menjadi function. Operasi yang
dimaksud
adalah:
- push(s) : menambah elemen stack yang baru dibagian
atas stack.
- pop(s) : menghapus elemen dari stack yang berada
dibagian paling atas.
- get(s) : membaca nilai elemen dari stack yang berada
dibagian paling atas.
- isEmpty(s) : memeriksa apakah stack kosong atau tidak.
Kegunaan Stack
Stack biasa
digunakan dalam mengontrol operasi dalam sebuah sistem operasi. Selain
itu stack juga
merupakan algoritma yang baik yang dapat digunakan untuk membuat
phaser (membaca
urutan operasi dari sebuah persamaan matematika).
Aplikasi Stack
Salah satu
aplikasi stack adalah dalam mengevaluasi dan menghitung ekspresi
aritmatik.
Sebagai contoh, bila kita ingin mencari nilai dari suatu ekspresi aritmatik
sederhana yang
melibatkan perkalian, penjumlahan, pengurangan dan pembagian.
Eksepresi
aritmatik berikut ini dikenal dengan susunan ekspresi infix:
15 * ( ( ( 3 -
2 ) * ( 4 + 10 ) ) / 7 )
membutuhkan
penyimpanan hasil sebagian perhitungan. Misalnya, jika bagian 3 - 2
pada ekspresi
di atas dihitung, maka kita harus menyimpan hasil pengurangan itu
yaitu 1
terlebih dahulu, dan kemudian menghitung ekspresi 4 + 1-. Dalam hal ini
stack sangat
ideal untuk digunakan.
Sebelum kita
menyelesaikan permasalahan di atas, mari kita coba menyederhanakan
ekspresi infix
di atas menjadi dalam susunan ekspresi postfix. Ekspresi postfix adalah
ekspresi yang
menempatkan operator setelah kedua operannya. Berikut ilustrasi dari
ekspresi infix
4 + 10 yang diubah menjadi ekspresi postfix.
Algoritma
Mengubah Ekspresi Infix menjadi Postfix
Proses konversi
ekspresi infix menjadi bentuk postfix selalu dimulai dari sebelah kiri
ekspresi
aritmatik.
a) Jika yang ditemukan adalah operan, maka
cetak atau simpan
b) Jika yang ditemukan adalah kurung buka
maka abaikan.
c) Jika yang ditemukan adalah operator maka
push ke dalam stack.
d) Jika yang ditemukan adalah kurung tutup
maka pop stack, kemudian cetak atau
simpan nilainya.
e) Jika ekspresi telah diperiksa semua
tetapi ternyata stack belum kosong, pop semua
data dalam
stack dan cetak atau simpan nilai yang di pop.
Algoritma
Mengubah Ekspresi Infix menjadi Postfix
Proses konversi
ekspresi infix menjadi bentuk postfix selalu dimulai dari sebelah kiri
ekspresi
aritmatik.
1. Jika yang ditemukan adalah operan,
maka cetak atau simpan
2. Jika yang ditemukan adalah kurung buka
maka abaikan.
3. Jika yang ditemukan adalah operator
maka push ke dalam stack.
4. Jika yang ditemukan adalah kurung tutup
maka pop stack, kemudian cetak atau simpan nilainya.
5. Jika ekspresi telah diperiksa semua
tetapi ternyata stack belum kosong, pop semua data dalam stack dan cetak atau
simpan nilai yang di pop.
