STACK

PENDAHULUAN

Pada pokok bahasan ini akan dibahas mengenai struktur data tumpukan atau stack, dimana stack merupakan suatu kumpulan data yang seolah-olah ada data yang diletakkan di atas data yang lain. Setelah mempelajari materi ini diharapkan mahasiswa mampu untuk :

a.    Mengetahui dan memahami definisi stack.

b.    Memahami operasi-operasi dasar stack.

c.    Memahami representasi statis dan dinamis stack.

PENYAJIAN (TUTORIAL)

Stack adalah kumpulan elemen-elemen yang tersimpan dalam suatu tumpukan. Aturan penyisipan dan penghapusan elemennya tertentu:

-Penyisipan selalu dilakukan “di atas” TOP

-Penghapusan  selalu dilakukan pada TOP

Karena aturan penyisipan dan penhapus semacam itu, TOP adalah satu-satunya alamat tempat terjadi operasi, elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus. Dikatakan bahwa elemen stack terususun secara LIFO (Last In First Out).

Seperti halnya jika kita mempunyai sebuah tumpukan buku, agar tumpukan buku itu tidak ambruk ketika kita mengambil sebuah buku di dalam tumpukan itu maka harus di ambil satu per satu dari tumpukan yang paling atas dari tumpukan.

Perhatikan bahwa dengan definisi semacam ini, representasi tabel sangat tepat untuk mewakili stack, karena operasi penambahan dan pengurangan hanya dilakukan disalah satu ujung tabel.

Beberapa contoh penggunaan stack adalah pemanggilan prosedur, perhitungan ekspresi arimatika, rekursifitas, backtracking, penanganan interupsi, dan lain-lain.

Karakteristik penting stack sebagai berikut:

1.    Elemen stack yaitu item-item data di elemen stack

2.    TOP (elemen puncak dari stack)

3.    Jumlah elemen pada stack

4.    Status/kondisi stack, yaitu:

-       Penuh

Bila elemen di tumpukan mencapai kapasitas maksimum tumpukan. Pada kondisi ini, tidak mungkin dilakukan penambahan ketumpukan. Penambahan di elemen menyebabkan kondisi kesalahan Overflow

-       Kososng

Bila tidak ada elemen tumpukan. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen tumpukan. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.

Representasi Stack:

-       Representasi statis

Stack dengan representasi statis biasanya diimplementasikan dengan menggunakan array.Sebuah array memliki tempat yang diaokasikan diawal sehingga sebuah elemen yang dimasukkan dalam sebuah array terbatas pada tempat yang ada pada array. Karena menggunakan array maka stack dengan representasi statis dalam mengalami kondisi elemen penuh.

-          Representasi dinamis

Stack dengan representasidinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori.

Karena semua operasi pada sebuah stack diawali dengan elemen yang paling atas maka jika menggunakan representasi dinamis saat elemen ditambahkan akan menggunakan penambahan elemen pada awal stack (addfirst) dan saat pengambilan atau penghapus elemen menggunakan penghapus di awal stack (delfirst).