1. DEFINISI STACK
Stack merupakan suatu kumpulan data yang seolah-olah ada data yang diletakkan di atas data yang lain. Dimana kita dapat menambah (menyisip) data, dan mengambil (menghapus) data lewat ujung yang sama, yang disebut sebagai ujung atas tumpukan (top of stack).
Stack bersifat LIFO (Last In First Out), yang berarti data yang terakhir masuk ke dalam stack akan menjadi data pertama yang dikeluarkan dari stack. Secara sederhana sebuah stack dapat kita ilustrasikan seperti gambar dibawah ini. Kita bisa mengatakan bahwa kotak B ada diatas kotak A dan ada dibawah kota C. Dari gambar tersebut kita dapat melihat bahwa kita hanya bisa menambah atau mengambil sebuah kota lewat satu ujung. Yaitu ujung bagian atas. Nampak pula bahwa stack merupakan kumpulan data yang sifatnya dinamis. Artinya kita bisa menambah atau mengambil dari dirinya.
Top
Contoh gambar
2. OPERASI ATAU FUNGSI STACK
Ada enam jenis operasi atau fungsi pada stack, yaitu:
a. Create, digunakan untuk membuat stack baru.
b. Push, digunakan untuk menambahkan elemen pada urutan terakhir.
c. Pop, digunakan untuk mengambil elemen stack pada tumpukan paling atas.
d. Clear, digunakan untuk mengosongkan stack.
e. Print, digunakan untuk menampilkan semua elemen-elemen stack.
f. IsEmpety, digunakan untuk mengecek apakah stack dalam keadaan kosong.
g. IsFull, digunakan untuk memeriksa apakah stack sudah penuh.
3. PENDEKLARASIAN STACK
Proses pendeklarasian stack adalah proses pembuatan struktur stack dalam memori. Karena stack dapat direpresentasikan menggunakan array maka suatu stack memiliki beberapa bagian yaitu:
a. Top yang menunjuk posisi data terakhir.
b. Elemen yang berisi data yang ada dalam stack. Bagian inilah yang berbentuk array.
c. Maks_elemen yaitu variabel yang menunjuk maksimal banyaknya elemen dalam stack.
4. INISIALISASI STACK
Inisialisasi stack adalah proses pembuatan suatu stack kosong. Adapun langkah-langkah proses inisialisasi stack yang menggunakan array adalah:
1. dengan mengisi nilai field top dengan 0 (nol) jika elemen pertama diawali dengan nomor 1. Kalau elemen pertama array dimulai dengan 0, maka top diisi dengan nilai -1.
2. Top adalah suatu variabel penanda dalam stack yang menunjukkan elemen teratas stack sekarang. Top of Stack akan selalu bergerak hingga mencapai Max of Stack sehingga menyebabkan stack penuh.
1. dengan mengisi nilai field top dengan 0 (nol) jika elemen pertama diawali dengan nomor 1. Kalau elemen pertama array dimulai dengan 0, maka top diisi dengan nilai -1.
2. Top adalah suatu variabel penanda dalam stack yang menunjukkan elemen teratas stack sekarang. Top of Stack akan selalu bergerak hingga mencapai Max of Stack sehingga menyebabkan stack penuh.
5. OPERASI-OPERASI STACK SECARA LENGKAP
a. Operasi Push
Operasi push adalah operasi dasar dari stack. Operasi ini berguna untuk menambah suatu elemen data baru pada stack dan disimpan pada posisi top yang akan mengakibatkan posisi top akan berubah. Langkah operasi ini adalah:
Ø Periksa apakah stack penuh (isfull). Jika bernilai false/0 (tidak penuh) maka proses push dilaksanakan dan jika pemeriksaan ini bernilai true/1 (stack penuh), maka proses push digagalkan.
Ø Proses push-nya sendiri adalah dengan menambah field top dengan 1, kemudian elemen pada posisi top diisi dengan elemen data baru.
Operasi push adalah operasi dasar dari stack. Operasi ini berguna untuk menambah suatu elemen data baru pada stack dan disimpan pada posisi top yang akan mengakibatkan posisi top akan berubah. Langkah operasi ini adalah:
Ø Periksa apakah stack penuh (isfull). Jika bernilai false/0 (tidak penuh) maka proses push dilaksanakan dan jika pemeriksaan ini bernilai true/1 (stack penuh), maka proses push digagalkan.
Ø Proses push-nya sendiri adalah dengan menambah field top dengan 1, kemudian elemen pada posisi top diisi dengan elemen data baru.
b. Operasi Pop
Operasi pop adalah salah satu operasi paling dasar dari stack. Operasi ini berguna untuk mengambil elemen terakhir (top) dan kemudian menghapus elemen tersebut sehingga posisi top akan berpindah. Operasi ini biasanya dibuat dalam bentuk function yang me-return-kan nilai sesuai data yang ada di top.
Langkah operasi pop pada stack yang menggunakan array adalah terlebih dahulu memeriksa apakah stack sedang keadaan kosong, jika tidak kosong maka data diambil pada posisi yang ditunjuk oleh posisi top, kemudian simpan dalam variable baru dengan nama data, kemudian posisi top -1, kemudian nilai pada variable data di-return-kan ke function.
Operasi pop adalah salah satu operasi paling dasar dari stack. Operasi ini berguna untuk mengambil elemen terakhir (top) dan kemudian menghapus elemen tersebut sehingga posisi top akan berpindah. Operasi ini biasanya dibuat dalam bentuk function yang me-return-kan nilai sesuai data yang ada di top.
Langkah operasi pop pada stack yang menggunakan array adalah terlebih dahulu memeriksa apakah stack sedang keadaan kosong, jika tidak kosong maka data diambil pada posisi yang ditunjuk oleh posisi top, kemudian simpan dalam variable baru dengan nama data, kemudian posisi top -1, kemudian nilai pada variable data di-return-kan ke function.
c. Operasi Isempty
Operasi ini digunakan untuk memeriksa apakah stack dalam keadaan kosong. Operasi ini penting dilakukan dalam proses pop. Ketika suatu stack dalam keadaan kosong, maka proses pop tidak bisa dilakukan.
Operasi ini dilakukan hanya dengan memeriksa field top. Jika top bernilai 0 (untuk elemen yang dimulai dengan index 1) atau top bernilai -1 (untuk elemen yang dimulai dengan index 0), maka berarti stack dalam keadaan empty (kosong) yang akan me-return-kan true (1) dan jika tidak berarti stack mempunyai isi dan me-return-kan nilai false (0).
Operasi ini digunakan untuk memeriksa apakah stack dalam keadaan kosong. Operasi ini penting dilakukan dalam proses pop. Ketika suatu stack dalam keadaan kosong, maka proses pop tidak bisa dilakukan.
Operasi ini dilakukan hanya dengan memeriksa field top. Jika top bernilai 0 (untuk elemen yang dimulai dengan index 1) atau top bernilai -1 (untuk elemen yang dimulai dengan index 0), maka berarti stack dalam keadaan empty (kosong) yang akan me-return-kan true (1) dan jika tidak berarti stack mempunyai isi dan me-return-kan nilai false (0).
d. Operasi Isfull
Operasi ini berguna untuk memeriksa keadaan stack apakah sudah penuh atau belum. Operasi ini akan menghasilkan nilai true (1) jika stack telah penuh dan akan menghasilkan nilai false (0) jika stack masih bisa ditambah.
Operasi ini akan memberikan nilai true (1) jika field top sama dengan field maks_elemen (untuk array yang elemennya dimulai dari posisi 1) atau top sama dengan maks_elemen-1 (unauk array yang elemennya dimulai dari posisi 0).
Operasi ini berguna untuk memeriksa keadaan stack apakah sudah penuh atau belum. Operasi ini akan menghasilkan nilai true (1) jika stack telah penuh dan akan menghasilkan nilai false (0) jika stack masih bisa ditambah.
Operasi ini akan memberikan nilai true (1) jika field top sama dengan field maks_elemen (untuk array yang elemennya dimulai dari posisi 1) atau top sama dengan maks_elemen-1 (unauk array yang elemennya dimulai dari posisi 0).
e. Aplikasi Stack
Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan operator. Operand merupakan suatu karakter atau elemen yang nilainya dioperasikan dengan bantuan suatu operator untuik menghasilkan suatu solusi.
Misalkan jika diberikan suatu ekspresi aritmatika 2*3, maka elemen ‘dua’ dan elemen ‘tiga’ merupakan operand dari ekspresi tersebut dan elemen ‘*’ merupakan operator perkalian atas dua operand yang menghasilkan suatu solusi. Suatu ekspresi aritmatika dapat dibedakan dalam tiga bentuk notasi perhitungan yaitu :
1) Notasi prefix, jika operator ditempatkan sebelum dua operand
2) Notasi infix, jika operator ditempatkan diantara dua operand
3) Notasi postfix, jika operator ditempatkan setelah dua operand
Dalam penggunaannya di kehidupan sehari-hari, notasi infix merupakan notasi aritmatika yang paling banyak digunakan untuk mengekspresikan suatu perhitungan artimatik dibanding dengan dua notasi yang lain, akan tetapi notasi postfix merupakan notasi yang digunakan oleh mesin kompilasi pada komputer dengan maksud untuk mempermudah proses pengkodean, sehingga mesin kompilasi membutuhkan stack untuk proses translasi ekspresi tersebut.
Berdasarkan teori yang diterangkan tersebut di atas, proses konversi infix menjadi notasi postfix dalam implementasinya membutuhkan stack pada proses konversinya, adapun proses tersebut memiliki 4 (empat) aturan yang digunakan, yaitu :
1) Jika ditemukan simbol kurung buka “(“, maka operasi push pada stack akan digunakan untuk menyimpan simbol tersebut ke dalam stack.
2) Jika ditemukan simbol kurung buka “)”, operasi pop digunakan untuk mengeluarkan operator-operator yang berada di dalam stack.
3) Jika terdapat simbol operator, maka operasi yang dilakukan pada stack terbagi atas:
a. Jika TOP(S) dari stack tersebut kosong atau berisi simbol “(“ maka operasi push akan digunakan untuk memasukan operator tersebut pada posisi di TOP(S).
b. Jika operator yang berada dipuncak stack merupakan elemen yang memiliki tingkat yang sama atau lebih tinggi maka operasi pop digunakan untuk mengeluarkan operator tersebut diikuti operasi push untuk menyimpan operator hasil scanning untai.
c. Jika operator yang berada di puncak stack memiliki tingkat yang lebih rendah dari operator yang discan, maka operator baru akan langsung dimasukan ke dalam stack dengan operasi push.
Adapun tingkatan operator yang dilacak menurut urutan tingkat adalah:
Tabel 1. Level Operator dalam Stack
Operator Level Operator
** Tinggi
* atau / Menengah
+ atau - Rendah
1. Notasi Prefix
Seorang ahli matematika “Jan Lukasiewicz“ mengembangkan satu cara penulisan ungkapan numeris yang selanjutnya disebut “Notasi Polish“ atau “Notasi Prefix” yang artinya: operator ditulis sebelum kedua operand yang akan disajikan.
Contoh notasi prefix dari notasi infix:
Infix Prefix
A + B + A B
A + B – C - + A B C
( A + B ) * ( C – D ) * + A B – C D
A – B / ( C * D $ E ) - - -
Secara sederhana, proses konversi dari infix menjadi prefix sebagai berikut:
1. Ungkapan yang akan dikonversikan adalah ( A + B ) * ( C – D ).
2. Dengan menggunakan tanda kurung bantuan, ungkapan diatas kita ubah menjadi: [ + A B ] * [ - C D ]
3. Jika [ + A B ] kita misalkan P, dan [ - C D ] kita misalkan Q maka ungkapan di atas bisa ditulis sebagai berikut: P * Q
4. Selanjutnya notasi infix dirubah menjadi prefix: * P Q
5. Dengan mengembalikan P dan Q pada notasinya semula dan menghapus tanda kurung bantuan, kita peroleh notasi prefix dari persamaan ( A + B ) * ( C – D ) yaitu: * + A B – C D
Contoh:
1. A + B * C
B * C = * B C ..... P
C * P = * C P ..... Q
Algoritma Infix Ke Prefix:
Langkah 0:- Baca ungkapan dalam notasi infix, misalnya S;
- Tentukan panjang ungkapan tersebut, misalnya N;
- Siapkan sebuah tumpukan kosong dan siapkan derajat masing-masing operator. Misalnya: $ berderajat 3, * dan / berderajat 2, + dan – berderajat 1 dan (berderajat 0).
Langkah 1:
Dimulai dari I : N sampai 1, kerjakan langkah-langkah berikut :
a. R = S ( I )
b. Test nilai R. Jika R adalah:
- Operand : Langsung ditulis
- Kurung buka : Pop dan tulis semua isi tumpukan sampai ujung tumpukan = ‘)‘, pop juga tanda ini tetapi tidak perlu ditulis.
- Kurung tutup : Push kedalam tumpukan
- Operator : Jika tumpukan kosong, atau derajat R lebih tinggi
dibanding derajat ujung tumpukan, push operator
ke dalam tumpukan. Jika tidak pop ujung tumpukan dan tulis, kemudian ulangi perbandingan R dengan ujung tumpukan, lalu R di push.
Catatan: Kurung tutup di dalam tumpukan dianggap mempunyai derajat yang lebih rendah dibanding R.
Langkah 2: Jika akhir notasi infix telah tercapai dan tumpukan masih belum kosong, pop semua isi tumpukan dan tulis hasilnya.
4. Selanjutnya notasi infix dirubah menjadi prefix: * P Q
5. Dengan mengembalikan P dan Q pada notasinya semula dan menghapus tanda kurung bantuan, kita peroleh notasi prefix dari persamaan ( A + B ) * ( C – D ) yaitu: * + A B – C D
Contoh:
1. A + B * C
B * C = * B C ..... P
C * P = * C P ..... Q
Algoritma Infix Ke Prefix:
Langkah 0:- Baca ungkapan dalam notasi infix, misalnya S;
- Tentukan panjang ungkapan tersebut, misalnya N;
- Siapkan sebuah tumpukan kosong dan siapkan derajat masing-masing operator. Misalnya: $ berderajat 3, * dan / berderajat 2, + dan – berderajat 1 dan (berderajat 0).
Langkah 1:
Dimulai dari I : N sampai 1, kerjakan langkah-langkah berikut :
a. R = S ( I )
b. Test nilai R. Jika R adalah:
- Operand : Langsung ditulis
- Kurung buka : Pop dan tulis semua isi tumpukan sampai ujung tumpukan = ‘)‘, pop juga tanda ini tetapi tidak perlu ditulis.
- Kurung tutup : Push kedalam tumpukan
- Operator : Jika tumpukan kosong, atau derajat R lebih tinggi
dibanding derajat ujung tumpukan, push operator
ke dalam tumpukan. Jika tidak pop ujung tumpukan dan tulis, kemudian ulangi perbandingan R dengan ujung tumpukan, lalu R di push.
Catatan: Kurung tutup di dalam tumpukan dianggap mempunyai derajat yang lebih rendah dibanding R.
Langkah 2: Jika akhir notasi infix telah tercapai dan tumpukan masih belum kosong, pop semua isi tumpukan dan tulis hasilnya.
Contoh:
1. A + B * C
Proses Ke- Karakter Dibaca Isi Stack Karakter Tercetak Notasi Prefix Terbentuk
1. C C C
2. * *
3. B * B BC
4. + + * *BC
5. A + A A*BC
6. + +A*BC
2. Notasi Infix
Salah satu pemanfaatan tumpukan adalah untuk menulis ungkapan menggunakan notasi tertentu. Dalam penulisan ungkapan khususnya ungkapan numeris, kita selalu menggunakan tanda kurung untuk mengelompokkan bagian mana yang harus dikerjakan lebih dahulu.
Contoh :
1. ( A + B ) * ( C – D )
Suku ( A + B ) akan dikerjakan lebih dahulu, kemudian suku ( C – D ) dan terakhir mengalikan hasil yang diperoleh dari 2 suku ini.
2. A + B * C – D
Maka B * C akan dikerjakan lebih dahulu diikuti yang lain.
Dalam hal ini pemakaian tanda kurung akan sangat mempengaruhi hasil akhir. Cara penulisan ungkapan sering disebut dengan “Notasi Infix” artinya operator ditulis diantara 2 operand.
3. Notasi Postfix
Notasi lain yang merupakan kebalikan notasi prefix adalah “Notasi Postfix” atau lebih dikenal dengan Notasi Polish Terbalik (Reverse Polish Notation atau RPN). Dalam hal ini operator ditulis sesudah operand. Sama halnya dengan notasi prefix disini juga diperlukan tanda kurung pengelompokan.
Proses notasi dari infix ke postfix adalah :
1. Ungkapan yang akan dikonversikan adalah: (A + B ) * ( C – D ).
2. Dengan menggunakan tanda kurung bantuan, ungkapan diatas diubah menjadi: [ A B + ] * [ C D - ]
3. Jika [ A B + ] kita misalkan P, dan [ C D - ] kita misalkan Q, maka ungkapan diatas dapat ditulis: P * Q
4. Selanjutnya notasi infix dirubah menjadi postfix yaitu: P Q *
5. Dengan mengembalikan P dan Q paada notasinya semula dan menghapus tanda kurung bantuan kita peroleh notasi postfix dari persamaan:
( A + B ) * ( C - D ) yaitu A B + C D - *
Contoh notasi infix ke postfix:
Infix Postfix
A + B – C A B + C –
( A + B ) * ( C – D ) A B + C D - *
A – B / ( C * D $ E ) - - -
Contoh soal:
1. A – B / ( C * D $ E )
D $ E = D E $ .... P
C * P = C P * .... Q
B / Q = B Q / .... R
A – R = A R –
= A B Q / -
= A B C P * / -
= A B C D E $ * / -
Algoritma Infix Ke Postfix:
Langkah 0:- Baca ungkapan dalam notasi infix, misalnya S;
- Tentukan panjang ungkapan tersebut, misalnya N;
- Siapkan sebuah tumpukan kosong dan siapkan derajat masing-masing operator. Misalnya: $ berderajat 3, * dan / berderajat 2, + dan – berderajat 1 dan (berderajat 0).
Langkah 1:
Dimulai dari I : 1 sampai N, kerjakan langkah-langkah berikut:
a. R = S ( I )
b. Test nilai R . Jika R adalah:
- Operand : Langsung ditulis
- Kurung buka : Push kedalam tumpukan
- Kurung tutup : Pop dan tulis semua isi tumpukan sampai ‘(‘, pop juga tanda ini tetapi tidak perlu ditulis
- Operator : Jika tumpukan kosong, atau derajat R lebih tinggi
dibanding derajat ujung tumpukan, push operator ke dalam tumpukan. Jika tidak pop ujung tumpukan dan tulis, kemudian ulangi perbandingan R dengan ujung tumpukan, lalu R di push.
Catatan: Kurung buka di dalam tumpukan dianggap mempunyai derajat yang lebih rendah dibanding R.
Langkah 2: Jika akhir notasi infix telah tercapai dan tumpukan masih belum kosong, pop semua isi tumpukan dan tulis hasilnya.
Contoh:
1. A + B * C
Proses ke- Karakter Dibaca Isi Stack Karakter Tercetak Notasi Postfix Terbentuk
1. A A A
2. + +
3. B + B AB
4. * *+
5. C *+ C ABC
6. + * ABC*
7. + ABC*+
1. A + B * C
Proses Ke- Karakter Dibaca Isi Stack Karakter Tercetak Notasi Prefix Terbentuk
1. C C C
2. * *
3. B * B BC
4. + + * *BC
5. A + A A*BC
6. + +A*BC
2. Notasi Infix
Salah satu pemanfaatan tumpukan adalah untuk menulis ungkapan menggunakan notasi tertentu. Dalam penulisan ungkapan khususnya ungkapan numeris, kita selalu menggunakan tanda kurung untuk mengelompokkan bagian mana yang harus dikerjakan lebih dahulu.
Contoh :
1. ( A + B ) * ( C – D )
Suku ( A + B ) akan dikerjakan lebih dahulu, kemudian suku ( C – D ) dan terakhir mengalikan hasil yang diperoleh dari 2 suku ini.
2. A + B * C – D
Maka B * C akan dikerjakan lebih dahulu diikuti yang lain.
Dalam hal ini pemakaian tanda kurung akan sangat mempengaruhi hasil akhir. Cara penulisan ungkapan sering disebut dengan “Notasi Infix” artinya operator ditulis diantara 2 operand.
3. Notasi Postfix
Notasi lain yang merupakan kebalikan notasi prefix adalah “Notasi Postfix” atau lebih dikenal dengan Notasi Polish Terbalik (Reverse Polish Notation atau RPN). Dalam hal ini operator ditulis sesudah operand. Sama halnya dengan notasi prefix disini juga diperlukan tanda kurung pengelompokan.
Proses notasi dari infix ke postfix adalah :
1. Ungkapan yang akan dikonversikan adalah: (A + B ) * ( C – D ).
2. Dengan menggunakan tanda kurung bantuan, ungkapan diatas diubah menjadi: [ A B + ] * [ C D - ]
3. Jika [ A B + ] kita misalkan P, dan [ C D - ] kita misalkan Q, maka ungkapan diatas dapat ditulis: P * Q
4. Selanjutnya notasi infix dirubah menjadi postfix yaitu: P Q *
5. Dengan mengembalikan P dan Q paada notasinya semula dan menghapus tanda kurung bantuan kita peroleh notasi postfix dari persamaan:
( A + B ) * ( C - D ) yaitu A B + C D - *
Contoh notasi infix ke postfix:
Infix Postfix
A + B – C A B + C –
( A + B ) * ( C – D ) A B + C D - *
A – B / ( C * D $ E ) - - -
Contoh soal:
1. A – B / ( C * D $ E )
D $ E = D E $ .... P
C * P = C P * .... Q
B / Q = B Q / .... R
A – R = A R –
= A B Q / -
= A B C P * / -
= A B C D E $ * / -
Algoritma Infix Ke Postfix:
Langkah 0:- Baca ungkapan dalam notasi infix, misalnya S;
- Tentukan panjang ungkapan tersebut, misalnya N;
- Siapkan sebuah tumpukan kosong dan siapkan derajat masing-masing operator. Misalnya: $ berderajat 3, * dan / berderajat 2, + dan – berderajat 1 dan (berderajat 0).
Langkah 1:
Dimulai dari I : 1 sampai N, kerjakan langkah-langkah berikut:
a. R = S ( I )
b. Test nilai R . Jika R adalah:
- Operand : Langsung ditulis
- Kurung buka : Push kedalam tumpukan
- Kurung tutup : Pop dan tulis semua isi tumpukan sampai ‘(‘, pop juga tanda ini tetapi tidak perlu ditulis
- Operator : Jika tumpukan kosong, atau derajat R lebih tinggi
dibanding derajat ujung tumpukan, push operator ke dalam tumpukan. Jika tidak pop ujung tumpukan dan tulis, kemudian ulangi perbandingan R dengan ujung tumpukan, lalu R di push.
Catatan: Kurung buka di dalam tumpukan dianggap mempunyai derajat yang lebih rendah dibanding R.
Langkah 2: Jika akhir notasi infix telah tercapai dan tumpukan masih belum kosong, pop semua isi tumpukan dan tulis hasilnya.
Contoh:
1. A + B * C
Proses ke- Karakter Dibaca Isi Stack Karakter Tercetak Notasi Postfix Terbentuk
1. A A A
2. + +
3. B + B AB
4. * *+
5. C *+ C ABC
6. + * ABC*
7. + ABC*+
Tidak ada komentar:
Posting Komentar