STACK (Tumpukan)

STACK atau TUMPUKAN

Stack atau tumpukan adalah bentuk khusus dari linear list. Pada stack, penghapusan serta pemasukan elemennya hanya dapat dilakukan di satu posisi, yakni posisi akhir dari list. Posisi ini disebut puncak atau top dari stack. Elemen stack S pada posisi ini dinyatakan dengan TOP(S).

Jelasnya, bila stack S [S1, S2, …, ST], maka TOP(S) adalah ST. Banyaknya elemen stack S pada suatu saat tertentu biasa kita sebut sebagai NOEL(S). Jadi untuk stack kita di atas, NOEL(S) = T. Seperti halnya pada semua linear list, pada stack dikenal operasi penghapusan dan pemasukan. Operator penghapusan elemen pada stack disebut POP, sedangkan operator pemasukanelemen, disebut PUSH.

Pada stack adalah bersifat ‘terakhir masukpertama keluar’ atau ‘last in first out (LIFO)’. Pada hakekatnya kita tidak membatasi berapa banyak elemen dapat masuk ke dalam stack. Untuk suatu stack S[S1, S2,..., SNOEL], kita katakan bahwa elemen Si, berada di atas elemen Sj, jika i lebih besar dari j. Suatu elemen tidak dapat kita POP ke luar, sebelum semua elemen di atasnya dikeluarkan.

OPERASI PADA STACK

Terdapat empat operasi pada stack, yakni CREATE (stack), ISEMPTY(stack), PUSH(elemen, stack), dan POP (stack). CREATE(S) adalah operator yang menyebabkan stack S menjadi satu stack hampa. Jadi NOEL(CREATE(S)) adalah 0, dan TOP(CREATE(S)) tak terdefinisi.

Sedangkan operator ISEMPTY(S) bermaksud memeriksa apakah stack S hampa atau tidak. Operandnya adalah data bertipe stack, sedangkan hasilnya merupakan data bertipe boolean. ISEMPTY(S) adalah true, jika S hampa, yakni bila NOEL(S) = 0, dan false dalam hal lain. Jelas bahwa ISEMPTY(CREATE(S)) adalah true.

Operator PUSH (E,S) akan bekerja menambahkan elemen E pada stack S. E ditempatkan sebagai TOP(S). Operator POP(S) merupakan operator yang bekerja mengeluarkan elemen TOP(S) dari dalam stack. POP(S) akan mengurangi nilai NOEL(S) dengan 1. Suatu kesalahan akan terjadi apabila, kita mencoba melakukan POP(S) terhadap stack S yang hampa.

Kesalahan overflow akan terjadi jika kita melakukan operasi pemasukan data (PUSH) pada stack yang sudah penuh (dalam hal ini jika banyaknya elemen yang kita masukkan ke dalam sebuah stack sudah melampaui batas kemampuan memori atau telah didefinisikan sebelumnya).

Sebaliknya, kesalahan underflow akan terjadi jika stack sudah dalam keadaan hampa, kita lakukan operasi pengeluaran atau penghapusan (POP).