Stack Stack adalah struktur data yang memiliki sifat last in first out. Struktur dari stack yang dapat kita lihat sehari-hari adalah : tumpukan (lihat gambar 1.1)
Gambar 1.1 Stack Terdapat 2 (dua) operasi yang dapat dikerjakan dalam stack : push dan pop (lihat gambar 2.2). Push adalah operasi menambahkan data ke tumpukkan, sedangkan pop adalah operasi mengambil data yang menempati posisi teratas dari stack.
Gambar 2.2a Operasi Push Pada Stack
Gambar 2.2b Operasi Pop Pada Stack
Gambar 2.2c Operasi Push dan Pop Pada Stack
Gambar 2.2d Contoh Lengkap Operasi Stack
Stack bisa dipakai untuk aplikasi delimiter check. Contoh delimiter {, [, (, ), ], }. Setiap pembuka delimiter harus mempunyai delimiter penutup. Contoh : a{bc[d]e}f(g) a{bc[d}e]f(g)
BENAR SALAH
Implementasi Stack Menggunakan Array Diandaikan jumlah tumpukan stack tidak akan melebihi K. Maka berikut ini adalah langkah-langkah implementasi stack menggunakan Array : 1. Buat array dengan nama S (array 1 dimensi) yang memiliki ukuran K S[K] 2. bagian top dari stack dinamakan h, diberi nilai awal = 0 3. Misal terjadi operasi push(x) : menambahkan elemen x ke dalam stack. maka terdapat dua proses yang terjadi : (3.1) S[h]=x (3.2) h++ 4. Jika terjadi operasi pop() : mengambil data teratas dari stack, maka terdapat dua proses yang terjadi : (4.1) h-(4.2) return S[h] 5. Top() : melihat data teratas dari stack, maka proses yang terjadi : (5.1) return S[h-1] 6. Empty() : Mengecek apakah stack dalam kondisi kosong ? (6.1) return (h==0) Setiap kali terjadi operasi, harus dilakukan pengujian terhadap batas dari array. Terdapat 2 (dua) kondisi yang terjadi : 1. Jika memasukkan data ke stack yang telah penuh, saat h=K maka terjadi Overflow 2. Jika mengambil data dari stack yang kosong, saat h<0 maka terjadi Underflow Penentuan Ukuran Stack Ukuran dari stack perlu diperhatikan. Ukuran yang ideal disesuaikan dengan kebutuhan pemakaian karena Jika ukuran stack yang disediakan sangat besar dibandingkan dengan stack yang terpakai maka terjadi kondisi wasting space (pemborosan tempat penyimpanan). Sedangkan jika ukuran stack yang disediakan lebih sedikit dibandingkan dengan yang dibutuhkan maka akan terjadi masalah kekurangan tempat penyimpanan.
Implementasi Stack Menggunakan Alokasi Memori Dinamis dan Pointer Ide dasar dari implementasi ini adalah mengalokasikan memori saat dibutuhkan. Ada beberapa hal yang perlu diperhatikan berkaitan dengan implementasi ini : 1. penunjuk (pointer) head akan menunjuk ke data pertama. 2. Setiap data dalam stack disimpan dalam node 3. Setiap node memiliki 2 (dua) informasi penting yaitu data dan berikut 4. Pada saat awal, head berikan nilai NULL yang berarti belum ada data di dalam stack 5. Pada saat operasi pengecekan kosong atau tidaknya sebuah stack, maka perintah yang diberikan adalah : return (head == NULL) 6. Pada saat operasi memperoleh nilai teratas dari stac, maka perintah yang diberikan adalah : jika (stack tidak kosong) maka kembalikan data pada posisi teratas di dalam potongan bahasa C/C++, pernyataan di atas dituliskan sebagai berikut : if (!empty()) { return (head.data) } Fungsi Push Pada Stack Menggunakan Pointer void push(int x) { //buat node baru T = new struct_dari_node T.data = x T.berikut = head head = T } Fungsi Pop Pada Stack Menggunakan Pointer tipe_dari_data pop() { if(empty()) { return NULL } X = head.data
T = head head = head.berikut delete T return X } Notasi Polish dan Stack Berikut ini adalah contoh mengubah bentuk infix menjadi postfix :
Gambar 2.3 Mengubah Infix ke Postfix
Dari Bentuk Postfix bisa dicari nilai dari sebuah pernyataan matematika, contoh :
Gambar 2.5 Menghitung Nilai Pernyataan Matematika Antrian Antrian adalah struktur data yang memiliki sifat first in first out. Di dalam struktur data ini terdapat informasi head / front dan tail / rear, karena informasi head dan tail bersifat flexible, maka umumnya implementasi dari antrian menggunakan jika menggunakan list maka akan dijelaskan menggunakan konsep double link list. Pada penjelasan berikut ini, dipaparkan implementasi antrian menggunakan Array. Gambaran dari antrian ditunjukkan pada gambar 2.6
Gambar 2.6 Contoh Antrian
Gambar 2.7 menunjukan contoh pengambahan data, proses Enqueue, ke dalam antrian.
Gambar 2.7 Proses Enqueue Gambar 2.8 menunjukan contoh mengurangi data, proses dequeue, dari antrian
Gambar 2.8 Proses Dequeue Operasi Pada Antrian Pada antrian terdapat beberapa operasi dasar yaitu : (1)empty : mengecek kosong tidaknya sebuah antrian (2)full : mengecek penuh tidaknya sebuah antrian (3)enqueue : menambahkan data ke dalam antrian (4)dequeue : mengambil data dari antrian Proses enqueue merupakan proses penulisan, proses write sedangkan proses dequeue merupakan proses pembacaan, proses read. kedua proses ini diharapkan bisa berjalan secara asynchronous.
Berikut ini adalah algoritma dari proses write : Selama terdapat data yang akan ditulis maka : jika (full) maka tunggu sebentar jika tidak enqueue(x) Berikut ini adalah algoritma dari proses read : Jika (empty) maka tunggu sebentar jika tidak maka x = dequeue() Implementasi dari Antrian Menggunakan Array Terdapat beberapa hal penting berkaitan dengan menggunakan array : 1. Asumsi array yang digunakan berukuran K. 2. Ada dua penunjuk yang diperhatikan : tail dan head
implementasi
antrian
K
head
tail
Gambar 2.9 Implementasi Antrian Dengan Array Kondisi Saat Antrian Kosong head = 0 tail = 0
head
tailGambar 2.10 Antrian Kosong
Kondisi Saat Terjadi Penambahan Data X Data X akan ditambahkan pada posisi tail setelah itu tail akan digeser
X
head
tail
Gambar 2.11 Penambahan Data X Kondisi Saat Terjadi Pengambilan Data Dari Antrian Terdapat dua proses yang terjadi : ● Ambil data pada posisi head
X
Y
Z
W
head ●
tail
perbaharui posisi head
X
Y
head
Z
W
tail
Kondisi Saat Menambahkan Data dan Tail Berada Pada Posisi Terakhir
X Y Z
head
tail
tail = (tail+1) % K
Y
head
Z
X
tail
Kondisi Saat Mengambil Data dan Head Berada Pada Posisi Terakhir
Y Z X
head head = (head+1) % K
tail
Y
Z
X
head
tail
Mendeteksi Kondisi Kosong dan Penuh Dari Antrian Kondisi Kosong dan Penuh dari antrian akan tercapai jika head == tail. Jadi Pertanyaannya adalah bagaimana mengetahui kondisi saat ini penuh atau kosong ? Teknik yang bisa ditempuh adalah sebagai berikut : Membuat sebuah variabel (misal num) sebagai indikator penuh atau kosong. Ketika terjadi proses enqueue, num = num + 1 Ketika terjadi proses dequeue, num = num – 1 Dengan cara yang demikian maka untuk mendeteksi penuh / kosong dilakukan sebagai berikut : kosong ? penuh ?
head==tail DAN num==0 head==tail DAN num==K
Implementasi Antrian Menggunakan Double Link List Konsep dari double link list adalah setiap data akan saling kait mengkait satu dengan yang lainnya. Dalam double link list terdapat juga dua penunjuk penting head dan tail. Gambaran dari double link list dapat dilihat pada gambar barikut : sebelumn ya
X
Head
data
Y
berikut
Z
Tail
Berikut ini adalah implementasi menggunakan double link list : (1)new head=NULL tail = NULL (2)empty return (head==NULL) (3)enqueue(x) buat node baru, misal T T.data = x T.sebelumnya = tail tail.berikut = T tail = T T.berikutnya = NULL (4)dequeue() if (head==NULL) { error (underflow) } X = head.data temp = head head = head.berikut delete temp return (X)
beberapa
fungsi
penting
dalam
antrian
