Materi� Stack

� Implementasi Stack Menggunakan Array

� Operasi Stack

Push� Push

� Pop

� Is Empty

� Is Full

Stack� Merupakan pola struktur data yang susunannya seperti

suatu tumpukan.

� Data masuk pertama akan menempati tumpukan paling bawah

Ketika ada data baru masuk, data tsb akan ditumpuk di� Ketika ada data baru masuk, data tsb akan ditumpuk diatasnya, dst

� Ketika diambil suatu data, maka data yang masuk terakhirkali (yang berada pada tumpukan paling atas) yang akanterambil

� Dan data yang pertama masuk ke dalam tumpukan (yang berada pada posisi paling bawah tumpukan) yang akanterakhir terambil

Queue� Disebut juga LIFO (Last In First Out)

� Data yang terakhir masuk, maka akan pertama kali keluar

� Sebaliknya, data yang pertama masuk, maka akan� Sebaliknya, data yang pertama masuk, maka akanpaling akhir keluar

Ilustrasi Stack� Tumpukan CD

Contoh Aplikasi Stack� Stack-Based Memory Allocation

� Setiap proses yang jalan dalam komputer, memilikimemori yang teralokasi untuknya

� Alokasi memori tersebut disusun menggunakan model StackAlokasi memori tersebut disusun menggunakan model Stack

� Ketika suatu proses dieksekusi, mungkin ia membutuhkanalokasi memori untuk data yang dibutuhkan. Maka data tersebut akan ditempatkan di posisi paling atastumpukan/stack

� Ketika data tersebut sudah tidak diperlukan lagi, makaproses yang sedang dieksekusi tsb bertanggung jawabuntuk menghapusnya dari stack

Ilustrasi Operasi dalam Stack� Pada awal proses maka Stack masih dalam posisi

kosong atau belum ada data dalam Stack

Ilustrasi Operasi dalam Stack� Ketika ada data pertama masuk, maka data tersebut

akan berada pada posisi paling bawah tumpukan

� Karena data dalam tumpukan masih ada 1 data, makadata tersebut juga berada pada posisi atasdata tersebut juga berada pada posisi atas

Ilustrasi Operasi dalam Stack� Ketika ada data kedua masuk,

maka data tersebut akanberada pada posisi tumpukandi atasnya.

� Demikian juga ketika ada data masuk lagi ke dalamtumpukan, ia akan diposisikandi atas data yang masuksebelumnya

� Misal dimasukkan data 25 dan5

Ilustrasi Operasi dalam Stack� Ketika ada data yang hendak

diambil, maka data yang berada pada posisi tumpukanpaling atas yang akan terambilpaling atas yang akan terambil

� Dari gambar disamping, ketikadiambil, maka data 5 akanterambil dan keluar dari Stack

Operasi dalam Stack� Push : merupakan operasi memasukkan data baru ke

dalam stack/tumpukan

� Pop : merupakan operasi mengambil ataumengeluarkan data dari dalam tumpukanmengeluarkan data dari dalam tumpukan

� Is Empty : merupakan operasi pengecekan apakahstack dalam keadaan kosong

� Is Full ; merupakan operasi pengecekan apakah stack dalam keadaan full

Implementasi Stack dengan Array

� Stack bisa diimplementasikan menggunakan Array

� Misal dibuat Array dengan ukuran 5

SebuahSebuah Array dg Array dg [ 4 ][ 4 ]

SebuahSebuah Array dg Array dg tipetipe data data intint untukuntukmembuatmembuat stack stack dengandengan isiisi data data berupaberupa bilanganbilanganintint [ 0 ][ 0 ]

[ 1 ][ 1 ]

[ 2 ][ 2 ]

[ 3 ][ 3 ]

4

8

6

Implementasi Stack dengan Array

� Data 4 (BAWAH) masuk pertama kali ke dalam stack, kemudian diikuti dengan 8 dan 6 (ATAS)

[ 0 ][ 0 ]

[ 1 ][ 1 ]

[ 2 ][ 2 ]

[ 3 ][ 3 ]

[ 4 ][ 4 ]

4

8

6

BAWAH

ATAS

Implementasi Stack dengan Array

� Untuk memudahkan implementasi, dalamsuatu stack perlu disimpan banyak data yang adalam stack (variabel size) danindeks elemen array yang berposisi sebagaiATAS (var. last), dan indeks elemen array

sizesize3

firstfirst0ATAS (var. last), dan indeks elemen array yang berposisi sebagai BAWAH (var. first)

lastlast2

[ 0 ][ 0 ]

[ 1 ][ 1 ]

[ 2 ][ 2 ]

[ 3 ][ 3 ]

[ 4 ][ 4 ]

4

8

6

Operasi Pop� Ketika ada operasi pengambilan data dari

stack (pop), maka size berkurang satu

� Demikian juga dengan last juga akanberubah

Tetapi first tidak berubah

sizesize2

firstfirst0

� Tetapi first tidak berubah

lastlast1

[ 0 ][ 0 ]

[ 1 ][ 1 ]

[ 2 ][ 2 ]

[ 3 ][ 3 ]

[ 4 ][ 4 ]

4

8

6

Operasi Push� Ketika ada data baru masuk ke dalam

queue, nilai size akan bertambah satu.

� Nilai last akan berubah

� Tetapi nilai first tetap

sizesize3

firstfirst0

lastlast2

[ 0 ][ 0 ]

[ 1 ][ 1 ]

[ 2 ][ 2 ]

[ 3 ][ 3 ]

[ 4 ][ 4 ]

4

8

10

Misal data 10

dimasukkan ke

dalam stack

Kondisi Empty� Jika size = 0 sizesize0

firstfirst[ 4 ][ 4 ]

lastlast

[ 0 ][ 0 ]

[ 1 ][ 1 ]

[ 2 ][ 2 ]

[ 3 ][ 3 ]

Kondisi Full� Jika size = panjang array

sizesize5

firstfirst0[ 3 ][ 3 ]

[ 4 ][ 4 ]

100

35firstfirst0

lastlast4

[ 0 ][ 0 ]

[ 1 ][ 1 ]

[ 2 ][ 2 ]

[ 3 ][ 3 ]

4

8

10

100