Secara sederhana stack atau tumpukan bisa diartikan sebagai kumpulan data yang seolah olah diletakkan di atas data yang lain. Satu hal yang perlu diingat bahwa kita bisa menambah (menyisipkan) data dan mengambil (menghapus) data melalui ujung yang sama, yang disebut sebagai ujung atas stack.
Untuk menjelaskan pengertian diatas kita ambil contoh sebagai berikut. Misalkan kita mempunyai 2 buah kotak yang ditumpuk, sehingga kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian 2 kotak tadi ditambah kotak ketiga, keempat, kelima dan seterusnya, maka akan diperoleh sebuah tumpukan kotak yang terdiri dari N kotak.
Secara sederhana sebuah stack dapat diilustrasikan seperti gambar 1.1
Dari gambar diatas bisa dilihat bahwa kotak B terletak diatas kotak A dan ada di bawah kotak C. Kotak D berada di atas kotak C, kotak E berada di atas kotak D dan seterusnya sampai kotak terakhir. Dari gambar di atas menunjukkan bahwa dalam stack hanya bisa menambah atau mengabil sebuah kotak lewat satu ujung, yaitu bagian atas.
| F |
| E |
| D |
| C |
| B |
| A |
Gambar 1.1 Tumpukan yang terdiri dari 6 kotak
Dari gambar diatas bisa dilihat bahwa yang menjadi ujung atas stack adalah F. Jadi jika ada kotak lain yang akan disisipkan maka kotak tersebut akan diletakkan diatas kotak F, dan jika ada kotak yang akan diambil maka kotak F yang pertama akan diambil.
XII.1 OPERASI PADA STACK
Ada 2 operasi dasar yang bisa dilaksanakan pada sebuah stack yaitu operasi menyisipkan data (push) dan operasi menghapus data (pop).
XII.1.1 Operasi push
Perintah push digunakan untuk memasukkan data kedalam stack. Untuk lebih jelasnya perhatikan ilustrasi berikut ini. Misalkan kita mempunyai data-data 3, 25 dan 9 dalam stack dengan posisi 3 paling bawah dan 9 paling atas dan kita dapat memasukkan data 34 dalam stack tersebut. Tentu saja data 34 akan diletakkan diatas data 9.
Prosesnya dari operasi push dapat diihat pada penggalan program berikut ini:
Void Push (NOD **T, char item)
{
NOD *n;
n=NODbaru (item);
n->next = *T;
*T = n;
Algoritma dari operasi push sesuai dengan penggalan program diatas adalah sebagai berikut:
1. Tentukan kondisi tumpukan, dimana kondisi tumpukan masih kosong
2. Deklarasikan node baru atau data yang akan dimasukkan kedalam tumpukan (dalam hal ini variable n)
3. n adalah data pertama yang ada didalam stack atau tumpukan tersebut
4. Masukkan data baru (missal T)
5. Posisi n tidak akan terakhir lagi, tetapi digantikan oleh T, begitu seterusnya kalau ada data atau node baru yang dimasukkan.
XII.1.2 Operasi Pop
Operasi pop adalah operasi untuk menghapus elemen yang terletak pada posisi paling atas dari sebuah stack. Sama halnya dengan operasi push, maka deklarasi untuk operasi pop dapat dilihat pada penggalan program berikut ini:
Char pop (NOD **T)
{
NOD *P; char item;
If( ! stack kosong (*T)) {
P = *T;
*T = (*T)->next;
Item = P->data;
Free(P);
}
Return item;
}
Algoritma dari operasi pop sesuai dengan penggalan program diatas adalah sebagai berikut:
1. Tentukan kondisi tumpukan, dimana kondisi tumpukan sudah ada isinya
2. Jika stack kosong dan jawaban ya, maka kerjakan langkah 5, kalau jawabannya tidak kerjakan langkag 3
3. Ambil node yang paling atas
4. Missal data atau node ada 2, maka posisi terakhir bukan lagi node ke 2 tetapi node pertama
5. Selesai
Pertanyaannya sekarang adalah bagaimana kalau stack itu kosong. Cara untuk melihat kosong tidaknya suatu stack adalah dengan membuat suatu fungsi yang menghasilkan suatu data yang bertipe Boolean. Cara ini lebih disarankan karena dengan mengetahui nilai fungsi tersebut kita bisa tahu kosong tidaknya suatu stack.
Fungsi untuk mengetahui kosong tidaknya suatu stack dapat dilihat dari penggalan program berikut:
// uji stack kosong
BOOL StackKosong (NOD *T)
{
Return (BOOL) (T == NULL));
}
XII.2 PEMANFAATAN STACK
Salah satu pemanfaatan stack adalah untuk menulis ungkapan dengan menggunakan notasi tertentu. Seperti kita ketahui, dalam penulisan ungkapan numeris kita selalu menggunakan tanda kurung untuk mengelompokkan bagian mana yang akan dikerjakan terlebih dahulu.
Sebagai contoh, perhatikan ungkapan berikut: (C+D)*(E-F)
Dari contoh diatas (C+D) akan dikerjakan lebih dahulu, kemudian baru (E-F) dan hasilnya akan dikalikan.
Lain halnya dengan contoh berikut ini: C+D*E-F, D*E akan dikerjakan terlebih dahulu diikuti yang lain. Dalam hal ini pemakaian tanda kurung sangat penting karena akan mempengaruhi hasil akhir.
Cara penulisan ungkapan sering disebut dengan notasi infix, yang artinya bahwa operator ditulis diantara 2 operand.
Seorang ahli matematika yang bernama Jan Lukasiewiccz kemudian mengembangkan suatu cara penuisan ungkapan numeris yang kemudian dikenal dengan nama notasi prefix, yang artinya adalah bahwa operator ditulis sebelum kedua operand yang akan disajikan.
Perhatikan contoh dari notasi infix dan prefix berikut ini:
Infix prefix
A+B +AB
A+B-C -+ABC
(A+B) * (C-D) *+AB-CD
Secara sederhana proses konfersi dari infix dapat dijelaskan sebagai berikut:
Misalkan ungkapan yang akan dikonversikan adalah sebagai berikut: (A+B)*(C-D) Dengan menggunakan tanda kurung bantuan ungkapan diatas dapat diubah menjadi: [+AB]*[-CD]
Jika [+AB] kita umpamakan P dan [-CD] sebagai Q, maka ungkapan diatas dapat ditulis P*Q Selanjutnya notasi infix diatas diubah menjadi notasi prefix: *PQ. Dengan mengembalikan P dan Q pada notasinya semula dan menghapus tanda kurung bantuan kita dapat memperoleh notasi prefix dari persamaan (A+B) * (C-D), Yaitu: *+AB-CD.
Notasi lain yang merupakan kebalikan dari notasi prefix adalah notasi postfix. Dalam hal ini operator ditulis sesudah operand, sama halnya dengan notasi prefix, maka notasi postfix dapat menggunakan tanda kurung bantuan.
Perhatikan contoh dari notasi infix dan postfix berikt ini:
Infix postfix
16/2 16 2 /
(2+14)*5 2 14 + 5 *
2 + 14 * 5 2 14 5 * +
(6 – 2) * (15 + 4) 6 2 – 5 4 + *
Perhatikan ilustrasi yang menggambarkan penggunaan notasi postfix dalam stack. Contohnya adalah 2 14+5*=80
Tidak ada komentar:
Posting Komentar