Senin, 21 November 2011

STACK


Definisi Stack  
Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First  Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.  



Pada gambar diatas, jika kita ingin mengambil sesuatu dari tumpukan maka kita harus 
mengambil benda paling atas dahulu, yakni compo.

Misalnya jika VCD langsung diambil, compo akan jatuh. Prinsip stack ini bias diterapkan dalam pemrograman. Di C++, ada dua cara penerapan prinsip stack, yakni dengan  array  dan  linked list. 
Setidaknya stack haruslah memiliki operasi-operasi sebagai berikut.  
Push          Untuk menambahkan item pada tumpukan paling atas  
Pop           Untuk mengambil item teratas 
Clear         Untuk mengosongkan stack  
IsEmpty     Untuk memeriksa apakah stack kosong  

IsFull         Untuk memeriksa apakah stack sudah penuh  

Dalam bab ini penjelasan mengenai stack akan menggunakan kelas stack. Kelima operasi stack diatas akan dideklarasikan secara abstrak dalam kelas ini, sedangkan kelas turunan dari stack akan mengimplementasikan operasi-operasi tersebut.  


Stack dengan Array  
Sesuai dengan sifat stack, pengambilan / penghapusan delemen dalam stack harus dimulai dari elemen teratas.


Operasi-operasi pada Stcak dengan Array :
Konstruktor  
Fungsi ini membuat sebuah stack baru yang masih kosong. Konsepnya adalah bahwa Top menunjukkan elemen stack teratas. Jika Top bernilai -1, berarti tumpukan kosong. 


IsFul 
Fungsi ini memeriksa apakah stack yang ada sudah penuh. Stack penuh jika stack penuh jika puncak stack terdapat tepat dibawah jumlah maksimum yang dapat ditampung stack atau dengan kata lain Top = MAX_STACK -1.  

Push  
Fungsi ini menambahkan sebuah elemen ke dalam stack dan tidak bias dilakukan lagi jika stack sudah penuh.  

IsEmpty  
Fungsi menentukan apakah stack kosong atau tidak. Tanda bahwa stack kosong adalah Top bernilai kurang dari nol.  mfachrz@gmail.com


Pop  
Fungsi ini mengambil elemen teratas dari stack dengan syarat stack tidak boleh kosong.  

Clear  
Fungsi ini mengosongkan stack dengan cara mengeset Top dengan -1. Jika Top bernilai 


Double Stack dengan Array  
Metode ini adalah teknik khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.  
Tampak jelas bahwa sebuah array dapat dibagi untuk dua stack, stack 1 bergerak ke atas dan stack 2 bergerak ke bawah. Jika Top1 (elemen teratas dari Stack 1) bertemu dengan Top 2 (elemen teratas dari Stack 2) maka double stack telah penuh.  
Implementasi double stack dengan array adalah dengan memanfaatkan operasi-operasi yang tidak berbeda jauh dengan operasi single stack dengan array. 

Operasi-operasi Double Stack Array :
Konstruktor   
Fungsi ini membuat stack baru yang masih kosong. Top[0] diset dengan -1 dan Top[1] diset dengan MAX_STACK.  

IsFull 
Fungsi ini memeriksa apakah double stack sudah penuh. Stack dianggap penuh jika Top[0] dan Top[1] bersentuhan sehingga stack tida memiliki ruang kosong. Dengan kata lain, (Top[0] + 1) > Top[1].  

kurang dari nol maka stack dianggap kosong


Push  
Fungsi ini memasukkan sebuah elemen ke salah satu stack.  

IsEmpty  
Fungsi memeriksa apakah stack pertama atau stack kedua kosong. Stack pertama dianggap kosong jika puncak stack bernilai kurang dari nol, sedangkan stack kedua dianggap kosong jika puncak stack sama atau melebihi MAX_STACK.  

Pop  
Fungsi ini mengeluarkan elemen teratas dari salah satu stack  

Clear  
Fungsi ini mengosongkan salah satu stack.  


Stack dengan Single Linked List  
Selain implementasi stack dengan array seperti telah dijelasnkan sebelumnya, ada cara  lain untuk mengimplementasi stack dalam C++, yakni dengan single linked list. 
Keunggulannya dibandingkan array tebtu saja adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori. Misalnya saja pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack. Oleh karena itu pula dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.

Operasi-operasi  untuk Stack dengan Linked List :  
Konstruktor  
Fungsi ini membuat stack baru yang kosong. Stack adalah kosong jika Top tidak menunjuk apa pun (bernilai NULL). 

IsEmpty  
Fungsi memeriksa apakah stack yang adamasih kosong.  

Push  
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.  

Pop  
Fungsi ini mengeluarkan elemen teratas dari stack.  

Clear  
Fungsi ini akan menghapus stack yang ada.    

0 komentar:

Posting Komentar

 

Dyah Sharaswati Copyright © 2009 Cosmetic Girl Designed by Ipietoon | In Collaboration with FIFA
and web hosting