Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Algoritma dan Struktur Data : Queue dan Priority Queue

Queue 

Pada modul minggu ini kita akan mempelajari cara pengimplementasian Queue dan Priority Queue. Modul ini akan menunjukkan cara mengimplementasikan Queue dengan array dan dengan linked list. Linked list yang akan kita gunakan adalah kelas MyLinkedList yang telah kita buat di dua minggu yang lalu.

Queue Dengan Array 

Pada bagian ini kita akan mengimplementasikan Queue dengan sebuah array. Implementasi yang akan kita gunakan adalah implementasi non sirkuler. Oleh karena itu, pada implementasi kita kali ini operasi enqueue akan memiliki kompleksitas O(1) dan dequeue akan memiliki kompleksitas O(N). Dalam implementasi ini kita akan mengasumsikan bahwa elemen awal dari Queue adalah elemen pada posisi 1 dalam array, dan elemen terakhir dari queue adalah elemen pada posisi atribut tail-1. 

Pseudocode dari operasi Enqueue dan Dequeue pada implementasi kita kali ini dapat dilihat di bawah :

Kita akan mengimplementasikan queue kita sebagai sebuah kelas dengan nama QueueArray. Kelas ini akan memiliki sebuah konstruktor yang menerima parameter bertipe bilangan integer dengan nama Size. Size adalah jumlah maksimum elemen yang dapat disimpan dalam queue ini. Atributatribut dari kelas ini adalah :

• arrObject : sebuah array of Object yang berfungsi untuk menyimpan elemen-elemen queue ini. 
• tail : sebuah bilangan integer yang menunjukkan posisi kosong berikutnya dalam arrObject. 

Kelas ini akan memiliki method-method berikut: 

• public boolean isEmpty() 
• public boolean offer(Object newObj) : memasukkan newObj ke akhir dari queue. Method ini akan mengembalikan true bila newObj berhasil dimasukkan dan false bila gagal karena queue sudah penuh. 
• public Object poll() : mengeluarkan elemen paling depan dari queue. Method ini akan mengembalikan null bila queue dalam keadaan kosong. 
• public Object peek() : mengembalikan elemen yang ada pada posisi paling depan dari queue tanpa mengeluarkannya dari queue. Method ini akan mengembalikan null bila queue dalam keadaan kosong. 
• public int size() : mengembalikan jumlah elemen yang sudah ada dalam queue. 

Mengapa kita memilih untuk memberi nama operasi enqueue kita sebagai offer (bukan add) dan dequeue kita sebagai poll (bukan remove)? Alasannya adalah karena kita mengikuti cara penamaan method yang ada pada kelas Queue milik Java. 

Pada kelas Queue milik Java, perbedaan antara offer dan add adalah pada perilakunya bila terjadi error pada saat operasi tersebut dijalankan. Pada offer, bila terjadi error pada saat method ini dipanggil maka offer akan mengembalikan nilai false. Sedangkan pada add, bila terjadi error maka method ini akan men-throw sebuah Exception. 

Perbedaan tersebut merupakan alasan mengapa kelas QueueArray menggunakan “offer” sebagai nama method enqueue-nya. Alasan yang sama juga merupakan penyebab mengapa kelas ini menggunakan nama method “poll” dan bukan “remove” . 

Perhatikan bahwa method poll dan offer harus dapat menangani kasus dimana queue dalam keadaan penuh atau kosong. Oleh karena itu pada saat kita mengimplementasikannya ke Java kita harus memodifikasi pseudocode-pseudocode di atas. 

Potongan kode program dari kelas QueueArray dapat dilihat di bawah ini : 

Buatlah sebuah kelas tester untuk menguji kelas QueueArray ini. Pastikan bahwa queue yang anda buat bersifat FIFO dan anda sudah pernah menguji kasus-kasus berikut ini : 

• meng-enqueue ke queue yang sudah penuh 
• men-dequeue dan peek dari queue yang kosong 
• melakukan enqueue sampai penuh, men-dequeue-nya sampai kosong, lalu melakukan enqueue kembali. 

Cobalah untuk memodifikasi kelas ini agar array yang digunakan bersifat sirkuler (lihat slide kuliah). Tujuannya adalah agar operasi offer, poll, dan peek memiliki kompleksitas O(1). 

Queue Dengan Linked List 

Kelas QueueLL 

Pada bagian ini kita akan mengimplementasikan sebuah queue dengan menggunakan linked list. Sebenarnya kita dapat menggunakan linked list manapun untuk melakukan hal ini, termasuk kelas linked list dari library Java. Namun kali ini kita akan menggunakan kelas MyLinkedList yang (seharusnya:p) telah anda buat dua minggu yang lalu. Pastikan bahwa kelas MyLinkedList sudah berjalan dengan benar sebelum anda menggunakannya untuk membuat queue. 

Queue dengan linked list ini akan kita implementasikan sebagai sebuah kelas dengan nama QueueLL. Kelas ini akan memiliki semua method yang ada pada kelas QueueArray. Methodmethod tersebut juga akan memiliki spesifikasi yang sama dengan method pada kelas QueueArray. Kelas ini akan memiliki sebuah atribut bertipe MyLinkedList. 

Operasi-operasi dari kelas MyLinkedList (yang merupakan sebuah singly linked list) akan memiliki kompleksitas sebagai berikut : 

• removeFirst : O(1) 
• removeLast : O(N) 
• addFirst : O(1) 
• addLast (tanpa tail) : O(N) 
• addLast (bila sudah dimodifikasi dengan tail) : O(1) 

Berdasarkan kompleksitas operasi-operasi MyLinkedList di atas, kita akan mengasumsikan bahwa awal dari queue adalah elemen head dari linked list, dan elemen terakhir dari queue adalah elemen terakhir dari linked list. Dengan asumsi ini maka operasi enqueue akan sama dengan operasi addLast dan operasi dequeue akan sama dengan operasi removeFirst. 

Asumsi ini kita pilih karena operasi removeFirst pada singly linked list dapat dikerjakan dengan kompleksitas O(1). Dengan ini maka operasi dequeue dapat dikerjakan dengan kompleksitas O(1). 

Perhatikan bahwa kelas MyLinkedList kita pada saat ini belum memiliki tail. Oleh karena itu operasi addLast akan memiliki kompleksitas O(N). Namun kita dapat dengan mudah memodifikasi kelas MyLinkedList dengan menambahkan tail agar addLast memiliki kompleksitas O(1). Modifikasi ini akan kita kerjakan pada poin b). 

Potongan kode dari kelas QueueLL adalah sebagai berikut :

Buatlah sebuah kelas tester untuk menguji kelas QueueLL ini. Pastikan bahwa anda sudah menguji kasus-kasus berikut ini : 

• men-dequeue dan peek dari queue yang kosong 
• melakukan enqueue sampai penuh, men-dequeue-nya sampai kosong, lalu melakukan enqueue kembali.

Modifikasi Pada Kelas MyLinkedList 

Pada bagian ini kita akan memodifikasi kelas MyLinkedList dari singly linked list dengan head menjadi singly linked list dengan head dan tail. Tujuannya adalah agar operasi addLast juga dapat dikerjakan dengan kompleksitas O(1). Dengan begitu, maka operasi enqueue (offer) dari kelas QueueLL juga akan memiliki kompleksitas O(1). 

Potongan kode di bawah ini hanya menunjukan modifikasi yang dilakukan pada method removeFirst dan addLast. Ingat bahwa agar method-method lain (addFirst, removeLast, addAfter, removeAfter) pada kelas MyLinkedList masih dapat digunakan, anda juga perlu memodifikasi method-method lain tersebut .

Ujilah kembali kelas QueueLL setelah anda memodifikasi kelas MyLinkedList ini dan pastikan bahwa QueueLL masih berfungsi dengan benar. 

Priority Queue 

Pada bagian ini kita akan membuat sebuah priority queue dengan menggunakan sebuah array untuk menyimpan elemen-elemennya. Elemen pertama dari priority queue ini adalah elemen yang bernilai paling kecil. Bila ada lebih dari satu elemen dengan nilai yang sama maka elemen yang lebih depan adalah elemen yang lebih dahulu masuk ke priority queue. 

Pada implementasi kita kali ini, kita akan merancangnya agar operasi peek dan poll memiliki kompleksitas O(1) sedangkan offer memiliki kompleksitas O(N). Untuk mencapai hal tersebut maka priority queue kita akan menyimpan elemen-elemennya dalam array secara terurut menurun. Priority queue ini juga akan menyimpan index dari elemen dengan nilai terkecil (elemen paling kanan dari array). Index ini akan kita sebut “head”. 

Dengan dua hal di atas maka operasi remove hanya perlu mengembalikan elemen paling kanan (elemen pada posisi Head) dan mengubah Head menjadi Head-1. Proses ini dapat dikerjakan dengan kompleksitas O(1). 

Cara kerja offer akan mirip dengan bagian penyisipan pada insertion sort. Operasi offer akan memiliki kompleksitas O(N).

Priority queue ini akan kita implementasikan sebagai sebuah kelas dengan nama PriorityQueueArray. Kelas ini akan memiliki konstruktor yang menerima sebuah integer dengan nama size. Size adalah jumlah maksimum elemen yang dapat disimpan oleh priority queue ini. kelas ini akan memiliki atribut-atribut di bawah ini : 

• arrObject : sebuah array of Object yang berfungsi untuk menyimpan elemen-elemen dari priority queue ini. Objek-objek dalam array ini akan disimpan secara terurut menurun. 
• head : sebuah bilangan integer yang menunjukkan elemen paling kanan (paling kecil) yang ada dalam arrObject. 

Kelas ini akan memiliki method-method berikut: 

• public boolean isEmpty() 
• public boolean offer(Object newObj) : memasukkan newObj ke dalam priority queue. Method ini akan mengembalikan true bila newObj berhasil dimasukkan dan false bila gagal karena priority queue sudah penuh. 
• public Object poll() : mengeluarkan elemen paling depan dari queue. Elemen paling depan dari priority queue ini adalah elemen yang paling kecil. Method ini akan mengembalikan null bila priority queue dalam keadaan kosong. 
• public Object peek() : mengembalikan elemen yang ada pada posisi paling depan dari priority queue tanpa mengeluarkannya. Method ini akan mengembalikan null bila priority queue dalam keadaan kosong. 
• public int size() : mengembalikan jumlah elemen yang sudah ada dalam priority queue. 

Sama seperti pada implementasi kelas QueueArray, pada implementasi kelas ini kita harus melakukan modifikasi untuk memastikan bahwa offer,peek, dan poll dapat berjalan dengan baik walaupun priority queue dalam keadaan penuh/kosong. Selain modifikasi tersebut kita juga harus memikirkan cara untuk dapat membandingkan objek-objek dari kelas Object yang ada dalam array. Kita harus dapat menentukan apakah sebuah objek lebih besar/lebih kecil dibandingkan objek lain. Untuk memudahkan pekerjaan anda, kita akan memberi batasan bahwa objek yang dimasukkan ke dalam priority queue harus mengimplementasikan interface Comparable dan semua objeknya merupakan anggota kelas yang sama. Dengan ini maka kita dapat melakukan casting ke Comparable dan memanggil method compareTo untuk melakukan perbandingan. 

Potongan kode dari kelas ini dapat dilihat di bawah :

Seperti biasa, buatlah sebuah kelas tester untuk menguji kelas ini dan pastikan bahwa anda sudah menguji kasus-kasus berikut ini : 

• meng-enqueue ke priority queue yang sudah penuh 
• men-dequeue dan peek dari priority queue yang kosong 
• melakukan enqueue sampai penuh, men-dequeue-nya sampai kosong, lalu melakukan enqueue kembali. 

Perhatikan bahwa priority queue ini hanya dapat menyimpan objek-objek dari kelas-kelas yang meng-implement interface Comparable! Oleh karena itu, untuk mengujinya anda dapat menggunakan kelas dari Java yang telah meng-implement Comparable (contoh : Integer, String, dan lain-lain) atau dengan membuat kelas baru yang juga meng-implement Comparable. Anda dapat melihat contoh kode kelas baru yang meng-implement Comparable pada soal latihan “Pengukur Baju”.

Sumber

Modul ASD : Queue