Praktikum 5 Queue
MODUL PRAKTIKUM STRUKTUR DATA DAN ALGORITMA QUEUE Deskripsi Singkat Queue merupakan bentuk struktur data seperti antrian yang memiliki konsep First In First Out (FIFO). Bermakna data yang pertama masuk merupakan data yang paling pertama dikeluarkan. Queue memiliki dua pintu. Ada pintu untuk masuk dan ada pintu untuk keluar. Bayangkan seperti anda mengantri membayar di supermarket maka orang yang paling pertama masuk adalah orang yang pertama keluar. Konsep queue tersebut disebut linear queue, namun pemanfaatannya pada struktur array kurang efisien (boros) karena posisi/index data yang dihapus tidak dapat dipakai kembali. Oleh karena itu, konsep tersebut diperbaiki dengan adanya circular queue (antrian melingkar). Circular queue akan kembali memanfaatkan tempat yang ditinggalkan oleh pengantri yang keluar.
Tujuan 1. Memahami konsep queue 2. Menggunakan konsep queue pada program sederhana
Materi 1 : Membuat Queue Berikut kode program class QueueX yang menggunakan konsep FIFO. Class QueueX ini sudah mengadopsi konsep circular queue bermakna tempat yang kosong sesudah proses hapus dapat dimanfaatkan kembali. Jadi bila antrian sudah sampai pada lokasi terakhir (n-1), antrian akan dilanjutkan ke lokasi 0. Gambar di bawah merupakan ilustrasi circular queue.
Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 5 Queue
public class QueueX { private int maxSize; private int[] queArray; private int front; private int rear; private int nItems; public QueueX(int s) // constructor { maxSize = s; queArray = new int[maxSize]; front = 0; rear = -1; nItems = 0; } // put item at rear of queue public void insert(int j) { // deal with wraparound (circular) if(rear == maxSize-1) rear = -1; // increment rear and insert queArray[++rear] = j; nItems++; // one more item } // take item from front of queue public int remove() { // get value and increment front int temp = queArray[front++]; // deal with wraparound (circular) if(front == maxSize) front = 0; nItems--; // one less item return temp; } // peek at front of queue public int peekFront() { return queArray[front]; } // true if queue is empty public boolean isEmpty() { Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 5 Queue
return (nItems==0); } // true if queue is full public boolean isFull() { return (nItems==maxSize); } // number of items in queue public int size() { return nItems; } } Operasi utama pada queue adalah insert() dan remove(). Method insert() digunakan untuk memasukkan data ke dalam queue. Sedangkan method remove() digunakan untuk mengeluarkan data yang paling pertama dimasukkan. Selain itu terdapat method tambahan lain yaitu peekFront(), isEmpty(), isFull(). Method peekFront() digunakan untuk melihat data pada antrian paling depan. Method isEmpty() digunakan untuk menguji apakah queue kosong atau tidak. Method isFull() digunakan untuk menguji apakah queue sudah penuh atau belum. Implementasi konsep queue pada program di atas menggunakan array. Sehingga pada method constructor melibatkan pemberian nilai awal pada ukuran queue (array), mencipta array dan nilai front serta rear. Nilai front merupakan indeks data yang paling awal masuk. Nilai rear merupakan indeks data yang paling terakhir masuk.
Materi 2 : Menggunakan class QueueX Berikutnya kita membuat class sederhana yang akan menggunakan class QueueX yang telah dibuat di atas. public class QueueApp { public static void main(String[] args) { Queue theQueue = new Queue(5); // queue holds 5 items theQueue.insert(10); // insert 4 items theQueue.insert(20); theQueue.insert(30); theQueue.insert(40); theQueue.remove(); // remove 3 items Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 5 Queue
theQueue.remove(); // (10, 20, 30) theQueue.remove(); theQueue.insert(50); // insert 4 more items theQueue.insert(60); // (wraps/circular around) theQueue.insert(70); theQueue.insert(80); while( !theQueue.isEmpty() ) // remove and display { // all items int n = theQueue.remove(); // (40, 50, 60, 70, 80) System.out.print(n); System.out.print(" "); } System.out.println(""); } // end main() } // end class QueueApp
Apakah output dari program di atas? Bagaimana tampilan hasilnya jika dibandingkan dengan urutan data yang dimasukkan?
Materi 3 : Class QueueX Menggunakan Generic Program queue yang sebelumnya menggunakan array bertipe int. Jika kita ingin menyimpan data char, tinggal mengubah tipe data yang disimpan menjadi char. Namun proses seperti ini sangat membuang waktu karena untuk setiap tipe data memerlukan class tersendiri. Seperti yang telah kita pelajari pada praktikum 3, untuk menyimpan data yang umum, kita dapat memanfaatkan class Object yang dibuat dalam format generic. Berikut ini merupakan contoh program QueueXGeneric yang merupakan queue dalam format generic. public class QueueXGeneric <E> { private int maxSize; private E [] queArray; private int front; private int rear; private int nItems; public QueueXGeneric(int s) // constructor { // set array size // menggunakan conditional operator // jika true, ukuran queue s, jika tidak diubah menjadi 10 maxSize = s > 0 ? s : 10; queArray = (E[]) new Object[maxSize]; // create array Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 5 Queue
front = 0; rear = -1; nItems = 0; } // put item at rear of queue public void insert(E j) { // deal with wraparound (circular) if(rear == maxSize-1) rear = -1; // increment rear and insert queArray[++rear] = j; nItems++; // one more item } // take item from front of queue public E remove() { // get value and increment front E temp = queArray[front++]; // deal with wraparound (circular) if(front == maxSize) front = 0; nItems--; // one less item return temp; } // peek at front of queue public E peekFront() { return queArray[front]; } // true if queue is empty public boolean isEmpty() { return (nItems==0); } // true if queue is full public boolean isFull() { return (nItems==maxSize); } // number of items in queue public int size() Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 5 Queue
{ return nItems; } }
Berikutnya kita coba gunakan class StackXGeneric seperti contoh berikut. public class TesQueueGeneric { public static void main(String[] args) { QueueXGeneric
theQueue = new QueueXGeneric (10); // make new queue QueueXGeneric queueChar = new QueueXGeneric (10); // make new queue theQueue.insert(20); // insert items into queue theQueue.insert(40); theQueue.insert(60); theQueue.insert(80); while( !theQueue.isEmpty() ) // until it's empty, { // delete item from queue Integer value = theQueue.remove(); System.out.print(value); // display it System.out.print(" "); } // end while System.out.println(""); queueChar.insert('<'); // push items onto stack queueChar.insert('a'); queueChar.insert('2'); queueChar.insert('>'); while( !queueChar.isEmpty() ) // until it's empty, { // delete item from queue Character value = queueChar.remove(); System.out.print(value); // display it System.out.print(" "); } // end while System.out.println(""); } // end main() }
Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 5 Queue
Materi 4 : Queue yang Menggunakan Prioritas, PriorityQ Priority queue adalah bentuk struktur data yang mirip seperti queue, yaitu ada front dan rear, and item dikeluarkan dari front. Namun pada priority queue, item disusun berdasarkan nilai kunci. Nilai kunci yang paling kecil (atau bisa juga sebaliknya) selalu berada di depan/front. Item dimasukkan dalam priority queue sehingga tetap dengan urutan yang benar. Pada contoh yang digunakan disini menggunakan array sehingga lebih sederhana. Namun proses insertion menjadi lebih lambat sehingga sesuai untuk jumlah item yang tidak terlalu banyak dan kecepatan proses insert tidak terlalu penting. Ada 2 pilihan implementasi priority queue dengan array, yaitu: 1. Item disusun dalam queue sesuai dengan priority order key nya (kecil ke besar atau besar ke kecil). Bermakna proses insert akan memastikan order yang betul. Sehingga akan melibatkan proses penggeseran. 2. Item disusun seperti queue biasa, yaitu bagian belakang/rear. Proses delete harus sesuai urutan order yang betul. Sehingga akan melibatkan proses pencarian dan penggeseran. Contoh PriorityQ berikut ini menggunakan cara yang pertama. Class berikut ini sudah langsung memasukkan method main untuk testing.
public class PriorityQ { // array in sorted order, from max at 0 to min at size-1 private int maxSize; private double[] queArray; private int nItems; //------------------------------------------------------------public PriorityQ(int s) // constructor { maxSize = s; queArray = new double[maxSize]; nItems = 0; } public void insert(double item) // insert item { int j; if(nItems==0) queArray[nItems++] = item; else { for(j=nItems-1; j>=0; j--) { Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
// if no items, // insert at 0 // if any items, // start at end,
Praktikum 5 Queue
if( item > queArray[j] ) // if new item larger, queArray[j+1] = queArray[j]; // shift upward else // if smaller, break; // done shifting } // end for queArray[j+1] = item; // insert it nItems++; } // end else (nItems > 0) } // end insert() public double remove() // remove minimum item { return queArray[--nItems]; } public double peekMin() // peek at minimum item { return queArray[nItems-1]; } public boolean isEmpty() // true if queue is empty { return (nItems==0); } public boolean isFull() // true if queue is full { return (nItems == maxSize); } public static void main(String[] args) throws IOException { PriorityQ thePQ = new PriorityQ(5); thePQ.insert(30); thePQ.insert(50); thePQ.insert(10); thePQ.insert(40); thePQ.insert(20); while( !thePQ.isEmpty() ) { double item = thePQ.remove(); System.out.print(item + " "); // 10, 20, 30, 40, 50 } // end while System.out.println(""); } // end main() } Perhatikan output yang dihasilkan pada program di atas. Apa yang dapat anda simpulkan?
Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
Praktikum 5 Queue
LATIHAN 1 Buat semua class-class yang ada dalam praktikum ini. Apakah yang dapat anda simpulkan?
SOAL-SOAL 1.
Viska Mutiawani, M.IT, Irvanizam, M.Sc, Dr. Taufik Fuadi Abidin Jurusan Informatika Universitas Syiah Kuala
