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.