Algoritma Pemrograman [BS204] [1.3] Bag, Queue, Stack
Robert Sedgewick, Kevin Wayne, Algorithms 4 th Ed., Chapter 1, Addison-Wesley Professional, 2011
1
Tujuan Perkuliahan Menekankan gagasan cara kita mewakili objek dalam koleksi yang efisien untuk berbagai operasi. Memperkenalkan iterasi generics dan konstruksi dasar yang substansial untuk menyederhanakan kode klien. Memperkenalkan dan menunjukkan pentingnya struktur data linked. Secara khusus, struktur data klasik yang dikenal sebagai linked list memungkinkan pelaksanaan Bags, Queue, dan Stack yang efisien.
2
Items Collection Kumpulan data-data yang disimpan dalam satu buah atribut/variabel. Himpunan nilai-nilai adalah Items Collection, dan operasi yang mungkin terjadi yaitu: menambah, menghapus, atau memeriksa item dalam collections. 3 jenis collections : Bags, Queue, Stack. Perbedaan dari 3 jenis items collection ini adalah spesifikasi objek yang akan dihapus/diperiksa.
3
APIs pada buku Algorithms 4ed
4
Generics
Karakteristik penting dari ADT Collections adalah harus dapat digunakan untuk semua jenis data yang dinamakan Generics. Kelas generic: kelas yang masih “umum”, belum spesifik ketika didefinisikan Pada saat deklarasi objek, hal yang umum harus dibuat spesifik– Setelah dibuat spesifik, baru bisa dipakai Biasanya yang “umum” adalah “type”-nya, dipakai untuk membungkus “operasi” yang sama Kelas generic pada Java diimplementasikan sebagai tipe parameter. Hasil kompilasi kode kelas generic tetap hanya satu kelas, dengan type parameter yang diganti dengan type yang seharusnya pada saat runtime. Keuntungan generic: ◦ Meningkatkan expressiveness power ◦ Meningkatkan type safety
◦ Mengeksplisitkan parameter type dan mengimplisitkan type casting5
Sintaks Generic
Mendefinisikan kelas dan interface: ◦ class NamaKelas
{ ... }
◦ interface NamaInterface { ... } ◦ class NamaKelas { ... }
◦ interface NamaInterface { ... } Nama untuk type generic sebaiknya menggunakan karakter huruf besar, misalnya E dan T Kita dapat mendefinisikan type generic lebih dari Satu Kelas dapat digunakan untuk membuat kelas baru dengan menggunakan template kelas generic
6
Contoh Generic
7
Konvensi Penamaan Type
E –Element (digunakan pada Java Collections Framework) K –Key N –Number T –Type V –Value S, U, V, etc. –2nd, 3rd, 4th types
8
Autoboxing
Otomatis Konversi dari tipe data primitif ke tipe data Class/Wrapper. (byte : Byte; short : Short; int : Integer; long : Long; float : Float; double : Double; boolean : Boolean; char : Char) Secara otomatis konversi tipe primitif ke tipe wrapper dikenal sebagai autoboxing, Dan secara otomatis konversi tipe wrapper untuk tipe primitif dikenal sebagai auto-unboxing. Stack stack = new Stack(); stack.push(17);
// auto-boxing (int -> Integer)
int i = stack.pop(); // auto-unboxing (Integer -> int)
9
Iterabel Collections
Untuk banyak aplikasi, kebutuhan klien hanya untuk memproses setiap item dalam beberapa cara atau iterate melalui item dalam koleksi. For-each. Contoh : Queue collection = new Queue<>();
Cara untuk melakukan akses iterasi ke collection dapat menggunakan loop dan loop yang baik adalah for-each : for (Transaction t : collection) { StdOut.println(t); } 10
Bags
Tipe Collection yang tidak mendukung penghapusan item tujuannya adalah menyediakan kumpulan items dan kemudian di-iterate melalui items collection untuk klien(klien juga dapat menguji bag empty dan index item di bag).
Urutan iterasi tidak ditentukan.
11
FIFO Queues – Antrian First In First Out
Kebijakan melakukan tugas-tugas dalam urutan yang sama dimana item tiba adalah salah satu yang sering kita jumpai dalam kehidupan sehari-hari : orang-orang yang menunggu dalam antrean di teater, mobil yang menunggu dalam antrean di pintu tol, tugas-tugas yang menunggu untuk dilayani oleh aplikasi pada komputer Anda.
Salah satu prinsip dasar kebijakan layanan apapun adalah persepsi keadilan.
Ide pertama yang terlintas dalam pikiran ketika kebanyakan orang berpikir tentang keadilan adalah bahwa siapa pun telah menunggu paling lama harus dilayani pertama.
Alasan khas untuk menggunakan queue dalam aplikasi adalah untuk menyimpan item dalam koleksi sementara pada saat yang sama menjaga urutan relatif mereka(item) : item keluar dalam urutan yang sama di mana item ditempatkan.
12
Pushdown Stacks
Kumpulan item yang didasarkan pada kebijakan Last-In-First-Out(LIFO).
Item akan dimasukkan ke tumpukan teratas; Item akan dikeluarkan dari tumpukan yang teratas.
Keuntungan : item yang menarik sesegera mungkin didapat;
Kegurian : beberapa item lama mungkin tidak akan pernah diakses jika tidak pernah mengosongkan stack.
Contoh : Tumpukan surat, Session pada browser.
13
Arithmetic Expression Evaluation
14
Implementing collections
Untuk mengatasi masalah pelaksanaan Bag, Stack dan Queue, kita mulai dengan implementasi klasik yang sederhana : ◦ Fixed - capacity stack ◦ Generics ◦ Array resizing ◦ Loitering ◦ Iteration
15
Fixed – Capacity Stack
ADT untuk kapasitas tumpukan yang berukuran tetap. Fixed Stack API pada Algorithms 4ed: ◦ Bekerja hanya untuk nilai-nilai String, ◦ Memerlukan klien untuk menentukan kapasitas, ◦ Tidak mendukung iterasi. Operasi ini melestarikan sifat sebagai berikut: ◦ Array digunakan untuk menyisipkan item. ◦ Tumpukan kosong ketika N adalah 0. ◦ Bagian atas tumpukan (jika tidak kosong) adalah pada [N-1].
16
ADT Fixed-Capacity Stack of String
17
Generics
18
Array Resizing (1)
Memilih array untuk mewakili isi tumpukan mengharuskan klien memperkirakan ukuran maksimum tumpukan sebelumnya. Pada Java, kita tidak bisa mengubah ukuran array setelah diciptakan kecuali diciptakan kembali, sehingga ukuran stack menjadi fixed. Semakin besar ukuran stack yang diciptakan maka semakin besar juga penggunaan memori pada komputer.
Jadi pada saat sebelum push() item ke Stack, sebaiknya client mengecek kondisi Stack, jika sudah penuh maka item tidak dapat di push(). Pengecekan penuh atau tidak nya suatu Stack dinamakan isFull().
Pada buku Algorithms 4ed, kode isFull() dihilangkan, karena berkeinginan untuk meringankan klien untuk berurusan dengan konsep tumpukan penuh, sebagaimana yang diuraikan dalam Stack API yang dimiliki Java. Jadi sebaliknya, kita memodifikasi implementasi array dinamis menyesuaikan ukuran array sehingga keduanya cukup besar untuk menampung semua item dan tidak begitu besar untuk membuang memori.
19
Array Resizing (II)
Mencapai tujuan menyesuaikan ukuran array sangat mudah, yaitu: Pertama, menerapkan metode yang move stack ke array dari ukuran yang berbeda: private void resize(int max) { // Move stack of size N <= max to a new array of size max. Item[] temp = (Item[]) new Object[max]; for (int i = 0; i < N; i++) temp[i] = a[i]; a = temp; }
Kemudian dalam push(), kita cek apakah array terlalu kecil. Secara khusus, kita cek apakah ada ruang untuk item baru dalam array dengan memeriksa apakah ukuran stack N sama dengan ukuran array a.length. Jika tidak ada ruang, maka ukuran array digandakan. Kemudian kita hanya memasukkan item baru dengan kode [N++] = item, seperti sebelumnya: public void push(String item) { // Add item to top of stack.
if (N == a.length) resize(2*a.length); a[N++] = item; }
20
Array Resizing (III)
Kemudian dalam pop(), kita mulai dengan menghapus item, maka kita membagi dua ukuran array jika terlalu besar. Apakah ukuran stack kurang dari 1/4 dari ukuran array. Setelah array dibelah dua maka array menjadi sekitar setengah penuh dan dapat menampung sejumlah operasi push() dan pop() sebelum harus mengubah ukuran array lagi. public String pop() { // Remove item from top of stack.
String item = a[--N]; a[N] = null; // Avoid loitering (see text). if (N > 0 && N == a.length/4) resize(a.length/2); return item;
}
Dengan implementasi ini, tumpukan tidak pernah meluap dan tidak pernah kurang dari 1/4 (kecuali stack kosong, ketika ukuran array 1). 21
Loitering Java Garbage
Collector akan mencari objekobjek yang sudah tidak digunakan di memori dan akan menghancurkan objek-objek tersebut agar memori dapat digunakan oleh objek-objek lain yang akan digunakan.
22
Iteration (I)
Salah satu operasi mendasar pada koleksi adalah untuk memproses setiap item dengan iterasi melalui koleksi menggunakan pernyataan for-each. Paradigma ini adalah algoritma yang bersih dan kompak serta bebas dari ketergantungan pada implementasi koleksi. Contoh : Stack<String> collection = new Stack<String>(); ... for (String s : collection) StdOut.println(s); ...
Sekarang, for-each statement diganti dengan Iterator : Iterator<String> i = collection.iterator(); while (i.hasNext()) { String s = i.next(); StdOut.println(s); }
Kode ini menggambarkan operasi-operasi yang kita butuhkan untuk mengimplementasi setiap koleksi: ◦ Koleksi harus menerapkan metode iterator() yang mengembalikan sebuah Iterator Object. ◦ Class Iterator harus menyertakan dua metode: hasNext() --> mengembalikan nilai boolean next() --> yang mengembalikan item generik dari koleksi. 23
Iteration (II)
24
