LIFO

Dalam dunia komputer, penggunaan stack atau tumpukan merupakan salah satu komponen penting untuk menjamin proses penanganan suatu data disamping hal lain seperti Queue (antrian), linked list, dan tree.

Stack adalah suatu koleksi atau kumpulan item data yang teroganisasi dalam bentuk urutan linear, yang operasi pemasukan dan penghapusan datanya dilakukan pada salah satu sisinya.

Diberikan suatu himpunan yang terurut himpunan sebagai S = {S₁, S₂, ......., S_T}, T pada anggota S merupakan linear order, sehingga stack dari himpunan tersebut memiliki informasi sebagai berikut [1] :

Elemen puncak dari stack dalam himpunan S dikatakan sebagai TOP, sehingga :

TOP[S} = S_{T ............................................................................}(1)

Banyaknya elemen stack dalam himpunan S dikatakan sebagai NOEL, sehingga NOEL = T, dimana himpunan dari S tersebut dapat disusun sebagai :

S = {S₁, S₂, .........., S_NOEL} .............................(2)

Dari dua definisi inilah maka suatu stack dapat digambarkan sebagai berikut :

uatu stack dalam keadaan kosong akan memiliki informasi NOEL(S) = 0 dan TOP(S)= undefined.

Untuk stack yang bukan kosong, maka akan memiliki informasi seperti yang digambarkan di bawah ini dimana informasi yang ada adalah NOEL(S) = 1 dan TOP(S) = Merah

ntuk stack yang berisi lebih dari n jumlah data maka informasi yang ada pada stack tersebut berisikan NOEL(S) = 2 (jika berisi 2 data) dan TOP(S) = Biru seperti ditunjukan pada gambar di bawah ini :

Elemen-elemen yang berada dalam stack tersebut di atas, memiliki prinsip dasar dalam pengoperasiannya yaitu prinsip LIFO (Last In First Out) atau yang masuk paling belakang akan memiliki prioritas untuk keluar paling depan.

Suatu stack dapat digambarkan sebagai suatu array (larik) berdimensi satu yang elemen-elemennya berkisar antara 1 sampai n elemen. Dengan demikian jika suatu stack didefinisikan dengan n elemen maka dapat dikatakan jumlah maksimum dari stack atau NOEL(S) nya adalah n, sehingga penambahan elemen stack yang ke n+1 tidak diperkenankan atau stack tersebut dalam kondisi overflow. Hal tersebut juga berlaku untuk stack dengan nilai minimum yaitu NOEL(S) dari stack dalam kondisi 0, jika dilakukan operasi pengambilan elemen atas stack tersebut akan mengakibatkan stack tersebut dalam kondisi underflow. Dua kondisi tersebut merupakan dasar dalam merancang suatu aplikasi pemrograman komputer.

Operasi-operasi Stack

Dalam penggunaannya suatu stack memiliki beberapa operasi yang dapat diterapkan seperti membuat stack, penambahan eleme ke dalam stack, menghapusan elemen dari dalam stack, dan operasi lain yang berhubungan dengan stack tersebut. Adapun operasi-operasi dasar dari suatu stack adalah :

Create(Stack)

Operasi Create(Stack) digunakan untuk membuat suatu stack baru dengan nama stack, yang nilai elemen saat stack tersebut dibuat adalah NOEL(S) = 0, TOP(S) = NULL (tidak terdefinisikan)

Is Empty(Stack)

Operasi ini merupakan operasi untuk mencek isi dari suatu stack dalam keadaan kosong atau berisi.

Operasi ini memiliki 2 (dua) kondisi boolean yaitu :

1. True jika stack tersebut kosong atau dapat dikatakan NOEL(S) = 0
2. False jika stack tersebut tidak dalam kondisi kosong atau dapat dikatakan   NOEL(S) > 0

Push (Stack, Elemen)

Operasi ini merupakan operasi untuk menambahkan satu elemen dengan nilai X pada puncak suatu stack, sehingga posisi TOP(S) akan bernilai X, penerapan operasi push pasa suatu stack S akan berakibat overflow jika NOEL(S) dari stack tersebut telah bernilai maksimum.

Pop (Stack)

Operasi ini berfungsi untuk menghapus satu elemen dari stack S, sehingga posisi NOEL(S) akan berkurang satu elemen, dan TOP(S) akan berubah. Operasi pop dapat menyebabkan kondisi underflow jika suatu stack S yang berada dalam kondisi minimum dikenakan operasi pop.

PEMBAHASAN

1. Jika TOP(S) dari stack tersebut kosong atau berisi simbol “(“ maka operasi push akan digunakan untuk memasukan operator tersebut pada posisi di TOP(S)
2. Jika operator yang berada dipuncak stack merupakan elemen yang memiliki tingkat yang sama atau lebih tinggi maka operasi pop digunakan untuk mengeluarkan operator tersebut diikuti operasi push untuk menyimpan operator hasil scanning untai.
3. Jika operator yang berada di puncak stack memiliki tingkat yang lebih rendah dari operator yang discan, maka operator baru akan langsung dimasukan ke dalam stack dengan operasi push.

Contoh Masalah

Tiga buah cakram yang masing-masing berdiameter berbeda mempunyai lubang di titik pusatnya. Ketiga cakram tersebut dimasukkan pada sebuah batang besi A sedemikian, sehingga cakram yang berdiameter lebih besar selalu terletak dibawah cakram yang berdiameter lebih kecil. Tulis algoritma untuk memindahkan seluruh cakram tersebut ke batang besi B; setiap kali hanya satu cakram yang boleh dipindahkan, tetapi pada setiap perpindahan tidak boleh ada cakram yang lebih besar berada di atas cakram kecil. Batang besi C dapat digunakan sebagai peralihan dengan tetap memegang peraturan yang telah disebutkan.

Penyelesaian Masalah

1. Mulai.
2. Pindahkan ban hijau ketiang B.
3. Pindahkan ban kuning ketiang C.
4. Pindahkan lagi ban hijau ketiang C di atas ban kuning.
5. Pindahkan ban ungu ketiang B.
6. Kembalikan ban hijau ke tiang A.
7. Ambil ban kuning letakan ke tiang B di atas ban ungu.
8. ambil lagi ban hijau letakkan ke tiang B di atas ban kuning.
9. Selesai