Stack (Tumpukan)

2. Stack (Tumpukan)

2.1. Definisi
STACK (Tumpukan) adalah list linier yang :
1. Dikenali elemen puncaknya (TOP)
2. Aturan penyisipan dan penghapusan
elemennya tertentu :
-Penyisipan selalu dilakukan “di atas “ TOP
-Penghapusan selalu dilakukan pada TOP

Karena aturan penyisipan dan penghapusan 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 akan tersusun secara LIFO (Last In First Out).
Maka secara lojik, sebuah STACK dapat digambarkan sebagai list linier yang setiap
elemennya adalah
Type ElmtS = record
Next : address >

dengan InfoType terdefinisi yang menentukan informasi yang disimpan pada setiap elemen stack, dan address adalah “alamat” dari elemen
Selain itu alamat elemen terbaru (TOP) dicatat, sedangkan alamat elemen yang paling “bawah”, yaitu yang paling lama biasanya diebut BOTTOM.
TOP adalah elemen pertama list, supaya penambahan dan penghapusan dengan mudah dan efisien dapat dilakukan.

Sehingga jika S adalah sebuah Stack, dan P adalah address maka
Top (S) adalah alamat elemen TOP, dimana operasi penyisipan/penghapusan dilakukan.
Info (P) adalah informasi yang disimpan pada alamat P
Next (P) adalah alamat suksesor P
ElmtS (P) adalah sebuah elemen stack yang beralamat P
Stack kosong adalah Stack dengan Top (S) = Nil ( tidak terdefinisi )
2.2. Traversal pada Stack
Pada stack, jarang sekali dilakukan traversal, karena keunikan Stack justru pada operasi yang hanya menyangkut elemen TOP. Namun dibutuhkan traversal misalnya untuk mencetak isi Stack.
2.3. Search pada Stack
Pada stack, elemen yang diproses hanyalah elemen pada TOP. Maka hampir tidak pernah dilakukan search.

2.4. Operasi dan fungsi dasar pada STACK.
a. Test STACK kosong
Mengetahui bahwa stack kosong atau tidak sangat penting, sebab semua operasi akan dilakukan berdasarkan kosong atau tidaknya suatu Stack. Realisasi algoritma dari definisi fungsional ini adalah sebuah fungsi yang melakukan test terhadap Stack sebagai berikut :

function StackEmpty (S : STACK) → Boolean
{ TEST stack kosong : Mengirim true, jika tumpukan kosong, false jika tumpukan tidak kosong}
Deklarasi

Deskripsi
return (Top (S) = Nil)

b. Pembuatan STACK kosong
Membuat Stack kosong diperlukan untuk memulai memakai stack. Realisasi algoritma dari definisi fungsional ini adalah sebuah prosedur yang melakukan inisialisasi stack sebagai berikut

Procedure CreateEmptyS (Output S : STACK)
{K. Awal : sembarang,
K. Akhir : sebuah stack S yang kosong siap dipakai
terdefinisi
Proses : Membuat stack kosong }

Deklarasi
Deskripsi
Top (S) ← Nil

c.Penambahan sebuah elemen pada STACK (Push)
Penambahan selalu dilakukan pada TOP, dan karena alamat TOP diketahui maka prosesnya sederhana. Berikut ini akan diberikan skema prosedur penyisipan tersebut. Realisasi algoritma dari definisi fungsional ini adalah salah satu dari dua buah prosedur yang melakukan penambahan elemen stack sebagai berikut. Prosedur pertama menambahkan suatu ElmtS yang diketahui alamatnya dan yang kedua menambahkan suatu nilai ElmtS yang diberikan.

procedure Push@ (Input/Output S : STACK Input P : address)
{Menambahkan sebuah elemen baru pada TOP sebuah stack, dengan elemen yang diketahui alamatnya}
{K.Awal : Stack mungkin kosong, P terdefinisi (berarti terdefinisi informasinya, Next (P) = Nil}
{K.Akhir : Top (S) adalah P}
Deklarasi
Deskripsi
{ insert sebagai elemen pertama }
Next (P) ← TOP (S)
TOP (S) ← P

procedure Push( Input / Output S:STACK Input E: InfoType )
{ Menambahkan sebuah elemen baru pada TOP sebuah stack, dengan elemen yang diketahui informasinya }
{ K. Awal : Stack mungkin kosong , E terdefenisi , alokasi alamat
selalu berhasil }
{ K. Akhir : TOP (S) berisi E )
Deklarasi
P : address
Deskripsi
Alokasi ( P ) { alokasi selau berhasil }
Info(P) ← E
{ insert sebagai elemen pertama }
Next(P) ← TOP(S)
TOP(S) ← P

d. Penghapusan sebuah elemen pada
STACK (Pop)
Penghapusan elemen Stack selalu dilakukan pada TOP , hanya saja harus diperhitungkan bahwa mugkin Stack akan menjadi kosong akibat terjadinya penghapusan. Jika Stack menjadi kosong , maka harga TOP harus diganti . Realisasi algoritma dari definisi funsional ini adalah salah satu dari dua buah prosedur yang melakukan pengambilan elemen stack sebagai berikut . Prosedur pertama mengambil suatu Elmts dengan menyimpan alamatnya dan yang kedua mengambil nilai , dan membebaskan alamat ( dealokasi ) yang tadinya dipakai



procedure PopStack@(Input/Output S : STACK Output P : address)
{K.Awal : Stack tidak kosong
K.Akhir : Alamat elemen Top (S) disimpan pada P, sehingga informasinya dapat diakses melalui P
Proses : Menghapus elemen stack, stack tidak boleh kosong dan mungkin menjadi kosong }
Deklarasi
Deskripsi
P ← TOP (S)
TOP (S) ← Next(TOP(S))


procedure PopStack(Input/Output S : STACK Output E : InfoType)
{K.Awal : Stack tidak kosong
K.Akhir : Alamat elemen Top (S) disimpan pada E, alamat TOP yang lama didealokasi
Proses : Menghapus elemen stack, stack tidak boleh kosong dan mungkin menjadi kosong }
Deklarasi
P : address
Deskripsi
P ← TOP (S)
E ← Info(P)
TOP (S) ← Next(TOP(S))
Dealokasi (P)

Catatan
Alokasi dan Dealokasi dalam bahasa Pascal :
1. Pengalokasian ruang memori dengan notasi
New (Pointer)
2. Pengalokasian ruang memori dengan notasi
Dispose(Pointer)

Bagian Deklarasi dari algoritma pada Stack :
Deklarasi
type InfoType = … {Sebuah type terdefinisi}
type Address pointer to ElmtS
type ElmtS = record
Next : Address >
type Stack = record
{Deklarasi Nama Peubah}
S : Stack
P : Address

{Maka penulisan untuk :
TOP(S) menjadi S^.TOP
Info(P) menjadi P^Info
Next(P) menjadi P^Next }

Catatan :
Agar notasi TOP(S), Info(P), Next(P) dapat ditulis sama seperti dalam algoritma dan tidak ditulis dengan notasi S^.TOP, P^Info, P^Next, maka dianjurkan untuk membuat fungsi TOP, fungsi Info dan Fungsi Next.


Function TOP(S : Stack) : Address;
{Mengembalikan alamat elemen pertama Stack S}

Deklarasi
Deskripsi
begin
TOP := S^.TOP;
end;

Function Info(P : Address) : InfoType;
{ Mengembalikan field Info dari elemen yang alamatnya P}

Deklarasi
Deskripsi
begin
Info := P^.Info;
end;


Function Next(P : Address) : Address;
{ Mengembalikan field Next dari elemen yang alamatnya P}

Deklarasi
Deskripsi
begin
Next := P^.Next;
end;

Soal-Soal Latihan
1. Mengapa cara penyusunan elemen pada Stack sering disebut tersusun secara LIFO?
2. Mengapa pada Stack Traversal dan Search jarang dilakukan?
3. Penghapusan elemen pada Stack selalu dilakukan pada elemen yang paling atas, bagaimana jika terpaksa harus menghapus elemen yang paling bawah?


4. Buatlah sebuah fungsi untuk menghitung jumlah elemen stack yang genap, jika diketahui sebuah stack dengan elemen bertype integer.
5. Buatlah fungsi/prosedur untuk mencetak elemen stack yang ganjil
6. Buatlah juga fungsi untuk menghitung rata-rata elemen Stack yang genap
7. Buatlah sebuah fungsi untuk mengirimkan elemen pertama Stack
8. Buatlah sebuah fungsi untuk mengirimkan elemen Stack yang maksimum jika diketahui elemen Stack terurut mengecil bertype integer.


untuk mendownloadnya silahkan klik di menu atas atau diSini..