1

3. Stack (Tumpukan)

3.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

2

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

<Info : InfoType,

Next : address >

3

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.

4

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 )

5

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.

3.3. Search pada Stack Pada stack, elemen yang diproses hanyalah elemen

pada TOP. Maka hampir tidak pernah dilakukan search.

3.2. Traversal pada Stack

6

3.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 :

7

function StackEmpty (S : STACK) → Boolean

{ TEST stack kosong : Mengirim true, jika

tumpukan kosong, false jika tumpukan tidak

kosong}

{Deklarasi}

{Deskripsi}

return (Top (S) = Nil)

8

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

9

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.

10

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

11

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

12

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

13

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))

14

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)

15

Catatan

Alokasi dan Dealokasi dalam bahasa Pascal :

1. Pengalokasian ruang memori dengan notasi

New (Pointer)

2. Pengalokasian ruang memori dengan notasi

Dispose(Pointer)

16

Bagian Deklarasi dari algoritma pada Stack :

{Deklarasi}

type InfoType = … {Sebuah type terdefinisi}

type Address pointer to ElmtS

type ElmtS = record

<Info : InfoType,

Next : Address >

type Stack = record <TOP : Address>

{Deklarasi Nama Peubah}

S : Stack

P : Address

17

{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.

18

Function TOP(S : Stack) : Address;

{Mengembalikan alamat elemen pertama Stack S}

{Deklarasi}

{Deskripsi}

begin

TOP := S^.TOP;

end;

19

Function Info(P : Address) : InfoType;

{ Mengembalikan field Info dari elemen yang

alamatnya P}

{Deklarasi}

{Deskripsi}

begin

Info := P^.Info;

end;

20

Function Next(P : Address) : Address;

{ Mengembalikan field Next dari elemen yang

alamatnya P}

{Deklarasi}

{Deskripsi}

begin

Next := P^.Next;

end;

21

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?

22

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