Stack

q  DEFINISI STACK

STACK adalah suatu bentuk khusus dari linear list di mana operasi  penyisipan dan penghapusan atas elemen-elemennya hanya dapat dilakukan pada satu sisi saja yaitu posisi akhir dari list. Posisi ini disebut puncak atau disebut sebagai “TOP(S)”.

¨       Prinsip Stack adalah LIFO ( Last In First Out ) atau Terakhir masuk pertama keluar.

Setiap elemen tidak dapat dikeluarkan (POP keluar) sebelum semua elemen diatasnya dikeluarkan.

¨       Elemen teratas (puncak) dari stack dinotasikan sebagai TOP(S)

Misal diberikan stack S sebagai berikut :

S= [ S2,S2,………, ST ] è maka TOP(S) = ST

¨       Untuk menunjukkan  jumlah elemen suatu stack digunakan notasi NOEL(S).

Dari stack diatas  maka NOEL(S) = T.

NOEL(S) menghasilkan nilai integer.

q  OPERASI PADA STACK

1.   CREATE (STACK)

2.   ISEMPTY (STACK)

3.   PUSH (ELEMEN, STACK)

4.   POP (STACK)

Ø  CREATE(S)

Operator ini berfungsi untuk membuat sebuah stack kosong (menjadi hampa) dan didefinisikan bahwa

NOEL (CREATE (S)) = 0 dan

TOP (CREATE(S)) = null / tidak terdefinisi

Ø  ISEMPTY(S)

Operator ini berfungsi  untuk menentukan apakah suatu stack adalah stack kosong (hampa) atau tidak . Operasinya akan bernilai boolean dengan definisi sebagai berikut :

ISEMPTY(S) = true, jika S adalah stack kosong atau NOEL(S) = 0

                      False, jika S bukan stack kosong atau NOEL(S) ¹ 0

Catatan : ISEMPTY(CREATE(S)) = true

Ø  PUSH(E,S)

¨       Operator ini berfungsi untuk menambahkan satu elemen ke dalam stack . Notasi yang digunakan adalah  PUSH(E,S)

Artinya : menambahkan elemen E ke dalam stack S

¨       Elemen yang baru masuk ini akan menempati posisi TOP jadi TOP(PUSH(E,S)) = E

¨       Akibat dari operasi ini jumlah elemen dalam stack akan bertambah, artinya NOEL (S) menjadi lebih besar atau stack menjadi tidak kosong (ISEMPTY(PUSH(E,S)) = false )

Ø  POP(S)

¨ Operator ini berfungsi untuk mengeluarkan satu elemen dari dalam stack, notasinya POP(S)

¨       Elemen yang keluar dari dalam stack adalah elemen yang berada pada posisi TOP.

¨       Akibat dari operasi ini jumlah elemen stack akan berkurang atau NOEL(S) berkurang 1 dan elemen pada posisi TOP akan berubah.

¨       Operator ini tidak dapat digunakan pada stack kosong, artinya POP(CREATE(S)) = error condition dan

POP(PUSH(E,S)) = S

Catatan : TOP(PUSH(E,S)) = E