stack

Pengertian Stack/Tumpukan

       Stack/Tumpukan adalah bentuk khusus dari list linear. Pada stack, penghapusan serta pemasukan elemennya hanya dapat dilakukan pada 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 = [A, B, C, D, E], maka TOP(S) adalah E. banyaknya elemen pada stack S pada suatu saat tertentu biasa kita sebut sebagai NOEL(S). Jadi untuk stack diatas NOEL(S) = 5.

       Seperti halnya link list, pada stack juga terdapat operasi penghapusan dan pemasukkan elemen list. Operator penghapusan pada stack kita kenal dengan nama POP, sedangkan operator pemasukkan elemen disebut PUSH. Berikut ini merupakan ilustrasi dari penggunaan operator-operator diatas yang dimulai dari sebuah stack S kosong,

S = [ ].

 Pada dasarnya kita tidak membatasi berapa banyak elemen yang dapat masuk ke dalam stack apalagi jika kita menggunakan tipe data link list yang tidak mempunyai batas, tetapi jika kita menggunakan tipe data Array jumlah elemen yang dapat masuk ke dalam stack dibatasi tergantung dari batas atas array (upper bound). Hal ini akan menyebabkan adanya kondisi Overflow pada stack jika kita mencoba melakukan operasi PUSH pada stack yang sudah penuh. Atau juga akan terjadi kondisi Underflow pada stack jika kita mencoba unruk melakukan operasi POP pada stack yang kosong. Pada praktikum ini kita akan mencoba mengimplementasikan stack dari link list tapi yang mempunyai batasan agar kondisi overflow dan underflow dapat diterapkan.

Deklarasi Stack Dalam Link List

Pendeklarasian Stack di dalam link list sama seperti kita mendeklarasikan link list. Menggunakan pointer sebagai variabel yang menunjuk ke elemen Stack selanjutnya.

Deklarasi Stack menggunakan Linked List di dalam Pascal :

Type

Stack        =        ^Simpul

Simpul        =        Record

                               Info : Char;

                               Next : Stack;

                       End;

Var

Head, Tail : Stack;

Max : Byte;

Link list yang kita gunakan ialah jenis Header Single Link List. Kita menggunakan jenis link list ini karena pada bagian header dapat kita manfaatkan untuk menyimpan informasi mengenai banyaknya elemen dalam stack (NOEL(S)). Selain itu jika kita menggunakan posisi Head,  operasi POP yang akan dilakukan pada posisi Head akan menyebabkan timbul kondisi UNDERFLOW demikian juga jika kita melakukan operasi PUSH pada posisi Tail akan menyebabkan kondisi OVERFLOW.

Operasi Pada Stack

Terdapat empat operasi pada Stack, yakni CREATE(Stack), ISEMPTY(Stack), PUSH(Elemen,Stack) dan POP(Stack). 

CREATE(Stack)

       Operator ini menyebabkan Stack menjadi suatu Stack hampa. Jika terdapat operasi NOEL(CREATE(S)) hasilnya adalah 0 dan TOP(CREATE(S)) hasilnya adalah tidak terdefinisi.