Algoritma dan Struktur Data : Stack
Stack (tumpukan) adalah struktur data yang bersifat LIFO (last in first out), dengan kata lain, operasi penambahan elemen (push) dan penghapusan elemen (pop) hanya dapat dilakukan pada elemen yang teratas (top) dari stack. Stack dapat diimplementasikan menggunakan array atau menggunakan linked-list.
Implementasi Stack Menggunakan Array
Dengan cara ini, elemen-elemen dari stack disimpan dalam sebuah array. Jika diimplementasikan dengan array, indeks yang merupakan top dari stack harus disimpan dan diupdate tiap kali operasi push dan pop dilakukan. Jika dilakukan push, maka indeks dari elemen top harus diupdate dengan meng-increment indeks sebelumnya. Sebaliknya, jika dilakukan operasi pop, maka indeks dari elemen top harus di-decrement.
Atribut
- Array untuk menyimpan elemen-elemen di stack.
- Indeks yang menunjuk ke top dari stack.
Operasi-operasi dalam Stack
- push() : menambahkan elemen baru ke dalam stack sebagai top.
- pop() : menampilkan top dari stack, kemudian menghapusnya dari stack.
- peek() : menampilkan top dari stack tanpa menghapusnya.
- empty() : mengecek apakah stack kosong.
Implementasi Stack Menggunakan Linked-List
Berbeda dengan implementasi menggunakan array yang ukurannya bersifat statis, dengan menggunakan linked-list, ukuran dari stack dapat berubah-ubah secara dinamis. Selain itu, pada stack yang diimplementasian dengan linked-list, elemen top dari stack merupakan head dari list, sehingga tidak perlu atribut indeks dari elemen top tersebut.
Dengan menggunakan linked-list, operasi push sama dengan operasi addFirst pada linked list. Operasi pop pada stack, merupakan operasi removeFirst pada linked-list. Sedangkan operasi peek, sama dengan getFirst. Perhatikan Gambar 1 dan Gambar 2 sebagai ilustrasi dari operasi pop dan push untuk stack yang diimplementasikan dengan mengunakan linkedlist.
 |
Gambar 1 Ilustrasi Pop. Stack awal digambarkan di gambar teratas, dan hasil operasi pop ditunjukkan oleh gambar paling bawah. |
 |
| Gambar 2 Ilustrasi penambahan elemen C pada stack yang berisi elemen U dan elemen P. |
Stack Pada Java
Stack pada Java diimplementasikan oleh kelas bernama “Stack”. Untuk menggunakan kelas ini, terlebih dahulu harus dilakukan impor package yang dibutuhkan, seperti berikut ini:
import java.util.Stack; //atau java.util.*
Setelah itu, dilakukan instansiasi dari kelas Stack, seperti berikut ini:
Stack<Integer> newStack = new Stack<Integer>();
Kata kunci di dalam <> menandakan bahwa stack yang dibuat akan berisi nilai-nilai integer. Karena int merupakan primitif, maka harus direpresentasikan oleh kelasnya, yaitu Integer. Berikut ini adalah daftar representatif primitif dengan kelasnya:
- int => Integer
- double => Double
- char => Character
- boolean => Boolean
Setelah itu dapat dilakukan implementasi terhadap Stack. Misalnya seperti berikut ini.
Untuk membandingkan dua buah nilai hasil dari pop() atau peek() secara langsung, misalnya seperti:
akan lebih baik apabila operator == diganti dengan equals yang disediakan oleh Java seperti ini:
Hal ini dilatarbelakangi oleh kemampuan autoboxing ( lebih lanjut dapat dibaca di http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html ) dari java, yang memungkinkan penggunaan kelas Integer dan primitif int secara berdampingan. Namun demikian, pada kasus di atas, keduanya memiliki tipe kelas Integer sehingga tidak dapat menggunakan operator == seperti biasa.
Sumber
Modul ASD : Stack
Posting Komentar