STACK

Topik

• Pengertian stack• Operasi pada stack• Implementasi stack dengan array• Implementasi stack dengan linked list

Stack (Tumpukan)

“Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack

Ilustrasi Stack

• Karena Compo ditumpuk di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya, karena Televisi ditumpuk pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika dilakukan pengambilan elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo.

TV TV

VCD

TV

VCD

Compo

TV

VCD

Compo

TV

VCD

Compo

TV

VCD

TV

penambahan pengambilan

Pengertian• Stack (tumpukan) adalah struktur data

dimana proses pengambilan dan penambahan element dilakukan pada satu ujung yang sama.

• Stack mengikuti konsep LIFO.• LIFO (Last In First Out) : elemen yang

terakhir kali masuk akan menjadi elemen yang pertama kali keluar.

• Stack dapat dibuat dengan menggunakan array maupun linked list.

PUSH, POP dan TOP• Operasi dasar pada stack adalah : pop dan push.

– Push : proses menambah item pada stack.– Pop : proses mengambil item pada stack.

• Pop dan push sama-sama dilakukan pada item yang terakhir kali ditambahkan pada stack.

• Sedangkan pointer TOP akan menunjuk pada element yang paling atas (yang paling akhir ditambahkan) pada stack.

Stack

push pop, top

Proses Operasi Stack• Contoh lain adalah ada sekumpulan perintah stack

yaitu push(5), push(7), pop, push(3), pop, pop. Jika dijalankan, maka yang akan terjadi adalah :

-1 -1

Pointer Top• Digunakan untuk menunjuk element

paling akhir yang dimasukkan kedalam stack.

• Jika top tidak menunjuk pada element manapun hal ini menunjukkan bahwa stack dalam kondisi kosong (empty).

• Pada array : top akan menyimpan index element paling akhir masuk.

Operasi pada Stack

1. Deklarasi2. Inisialisasi3. Cek kosong4. Cek penuh5. Penambahan6. Pengambilan7. Pengaksesan

(1) Deklarasi

• Proses yang harus dilakukan pertama kali adalah deklarasi/menyiapkan tempat.

• Langkah yang harus dilakukan adalah :– Deklarasi class– Deklarasi struktur data (menggunakan

array atau linked list)– Deklarasi pointer top

Deklarasi Stack dengan Array1. Pembuatan class

contoh :

2. Pembuatan variabel top :int top;

3. Pembuatan variabel untuk menampung panjang array :int array_size;

(mendeklarasikan variabel bernama array_size dengan tipe integer)

4. Pembuatan variabel Array :int tumpukan[];

(mendeklarasikan variabel array bernama tumpukan dengan tipe integer)

Program Deklarasi (Array)

(2) Inisialisasi

• Merupakan proses pemberian nilai awal.• Pada Array :

1. Pembentukan obyek array beserta ukurannya. tumpukan = new int[10]; (pembentukan obyek array yang memiliki 10 element, dan alamat obyek akan disimpan pada variabel bernama tumpukan)

2. Pemberian nilai awal pada variabel top=-1. int top=-1;

Program Inisialisasi (Array)

(3) Cek Kosong

• Operasi yang digunakan untuk mengecek kondisi stack dalam keadaan kosong.

• Caranya : melihat nilai top. Jika nilainya sama seperti ketika inisialisasi berarti stack dalam kondisi kosong (top =-1 atau top=null).

• Operasi ini harus dapat mengembalikan nilai true jika stack kosong dan false jika sebaliknya.

Program “isEmpty” (Array)

(4) Cek Penuh• Operasi yang hanya dapat diterapkan pada

stack yang menggunakan array.• Operasi ini digunakan untuk mengecek kondisi

stack dalam keadaan penuh.• Caranya : melihat nilai top. Jika nilai top sudah

menunjuk n-1 (dimana n adalah ukuran array) maka dapat diindikasikan stack sudah dalam kondisi penuh.

• Operasi ini harus dapat mengembalikan nilai true jika stack penuh dan false jika sebaliknya.

Program “isFull” (Array)

(5) Operasi POP• Pop adalah proses pengambilan data pada

stack.• Ketika pop terjadi, element pada stack akan

berkurang, yaitu element yang paling akhir ditambahkan.

• Sehingga posisi pointer top juga akan bergeser :– Pada array : top di-decrement

(5) Operasi POP...........(lanjutan)

• Langkah-langkah :1. Pengecekan stack dalam kondisi kosong dengan

memanggil method isEmpty(). Jika nilai yang dikembalikan true maka pop tidak bisa dilakukan (penangkapan error oleh exception handling). Jika nilai yang dikembalikan false maka akan dilakukan langkah berikutnya (langkah 2 dan 3).

2. Data dari element paling belakang akan menjadi return value (nilai yang dikembalikan).

3. Pergeseran posisi top.

Program Pop (Array)

• Untuk menggunakan StackException() harus disertakan import package dari java.util.*

(6) Operasi Push• Push adalah proses penambahan element

pada stack.• Ketika push terjadi, element pada stack

akan bertambah 1.• Posisi pointer top akan bergeser menunjuk

pada element baru yang ditambahkan.– Pada array : top akan di-increment.

(6) Operasi PUSH...........(lanjutan)

• Langkah-langkah :1. Penambahan element baru pada bagian

belakang stack.2. Pergeseran posisi top.

• Khusus untuk array, terlebih dahulu harus dicek kondisi stack penuh dengan memanggil method isFull(). Jika nilai yang dikembalikan true maka bisa ditampilkan pesan kesalahan atau dilakukan resizing array.

Program Push (Array)

Program Rezising()

(7) Operasi peek

• Peek adalah proses pengaksesan element yang ditunjuk oleh top(yaitu element yang terakhir kali ditambahkan).

• Operasi ini berbeda dengan pop karena tidak disertai dengan penghapusan data yang ada hanya pengaksesan (pengembalian data saja).

Program Peek (Array)

Contoh Penerapan Stack

• Konversi Desimal ke Biner• Notasi Polish• Menara Hanoi• Rat In a Maze

Implementasi Stack(Notasi Polish)

Notasi Polish (1)

• Menggubah notasi infix menjadi notasi postfix.

• Contoh :A+B (infix)AB+ (postfix)

Algoritma

• Misal :Q = ekspresi matematika yang ditulis dalam notasi infixP = penampung ekspresi matematika dalam notasi postfix

Algoritma1. Push tanda “(“ ke stack dan tambahkan tanda “)” di sentinel di

Q. 2. Scan Q dari kiri ke kanan, kemudian ulangi langkah c s.d f

untuk setiap elemen Q sampai stack Q kosong. 3. Jika yang discan adalah operand, maka tambahkan ke P 4. Jika yang discan adalah “(“ maka push ke stack 5. Jika yang discan adalah “)” maka pop isi stack sampai

ditemukan tanda “(“, kemudian tambahkan ke P sedangkan tanda “(“ tidak disertakanke P.

6. Jika yang discan adalah operator, maka : - Jika elemen paling atas dari stack adalah operator yang mempunyai tingkatan sama atau lebih tinggi dari operator yang discan, maka pop operator tsb dan tambahkan ke P. - Push operator tersebut ke stack.

7. Keluar

Contoh

Q = A + ( B * C - ( D / E ^ F ) * G ) * H

Penyelesaian

Q = A + ( B * C - ( D / E ^ F ) * G ) * H

>> setelah ditambahkan tanda “)” pada notasi sehingga terdapat 20 simbol sbb :

Penyelesaian

Penyelesaian

• Hasil akhir :Dari proses di atas didapatkan notasi postfix Q = ABC*DEF^/G*-H*+

Notasi Polish (2)

• Menghitung ekspresi matematika yang disusun dalam notasi postfix.

• Contoh :2,5,* (postfix)Hasil : 10

Algoritma• Misal :

P adalah ekspresi matematika yang ditulis dalam notasi postfix. variable value sebagai penampung hasil akhir.

Algoritma1.Tambahkan tanda “)” pada sentinel di P 2.Scan P dari kiri ke kanan, ulangi langkah c dan d

untuk setiap elemen P sampai ditemukan sentinel. 3.Jika yang discan adalah operand, maka push ke

stack. 4.Jika yang discan adalah operator (sebut opr1), maka

Pop 1 buah elemen teratas dari stack, simpan dalam variable var1. Pop 1 buah elemen teratas dari stack, simpan dalam variable var2. Hitung variable (var2 opr1 var1), simpan hasil di variable hitung. Push variable hitung ke stack.

5.Pop isi stack dan simpan di variable value. 6.Keluar.

Contoh Kasus

• P = 5, 2, 6, +, *, 12, 4, /, -

Penyelesaian• P = 5, 2, 6, +, *, 12, 4, /, -• Tambahkan tanda “)”pada sentinel P

sehingga P = 5, 2, 6, +, *, 12, 4, /, -, )

Didapatkan 10 simbol yaitu :

Penyelesaian

Hasil : Didapatkan Bilangan 37

Operator Priority

^ Pangkat, akar

/, * Pembagian, perkalian

+, - Penambahan, pengurangan

Latihan

1. Ubah notasi infix berikut ke dalam bentuk notasi postfix :A+((B*C/D)-(E^F))M*(N^O)/P-(Q+R)(R*S+T)^U/(V-W+X)

Latihan

2. Hitung ekspresi matematika berikut yang disusun dalam bentuk postfix :• 2,2,3,+,*,3,2,-,*• B,2,^, 4, –, a, *, c, *, 2, a, *, /, p, q, *, a, b,

+, /, +