MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA)
PRAKTIKUM PRAKTIKUM 5 IMPLEMENTASI QUEUE
TUJUAN PEMBELAJARAN: 1. Mengimplementasikan struktur data Queue menggunakan array. 2. Mampu mengimplementasikan struktur data Queue dengan Linked List 3. Mampu memanfaatkan struktur data Queue untuk menyelesaikan permasalahan.
PENGANTAR: Queue Queue (antrian) adalah barisan elemen yang apabila elemen ditambah maka penambahannya berada di posisi belakang (rear) dan jika dilakukan pengambilan elemen dilakukan di elemen paling depan (front). Oleh karena itu, queue bersifat FIFO (first in first out).Operasi-operasi dasar dari sebuah queue adalah : • •
Enqueue : proses penambahan elemen di posisi belakang Dequeue : proses pengambilan elemen di posisi depan
Selain operasi dasar di atas, ada pula operasi-operasi lain yang dapat dilakukan terhadap sebuah queue yaitu : • • •
Operasi pemeriksaan queue kosong (fungsi kosong) Operasi pemeriksaan queue penuh (fungsi penuh). Operasi inisialisasi queue (fungsi inisialisasi)
Representasi antrian secara sekuen relatif lebih sulit dibanding stack. Seperti dijelaskan di atas bahwa antrian juga merupakan satu kumpulan data. Dengan demikian tipe data yang sesuai untuk menyajikan antrian adalah menggunakan array atau linked list. Implementasi Queue dengan Array Struktur data queue dapat diimplementasikan dengan menggunakan sebuah array. Pada praktikum kali ini anda diminta untuk mencoba 3 versi implementasi queue, yakni: •
•
Versi 1: Implementasi queue dengan 1 variabel index, yani back untuk memantain jumlah elemen queue. Setiap ada proses dequeu harus dilakukan penggeseran elemen sebanyak jumlah elemen array-1. Versi 2: Implementasi queue dengan 2 variabel index, yakni back untuk memaintain elemen paling belakang dan front untuk memantain elemen paling depan. Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
1
MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA) •
Versi 3: Implementasi queue dengan circular array dengan mengorbankan 1 field array yang digunakan untuk definisi queue kosong atau queue penuh.
Berikut penjelasan implementasi queue versi 1: • • • •
•
Elemen Queue disimpan dalam array A Variabel back digunakan untuk memantain index setelah elemen queue paling belakangA[back] Elemen paling depan dari queue berada pada index 0 A[0] Proses enqueue (penambahan elemen) dilakukan dengan cara memasukkan data kedalam elemen array index back A[back]=data, dan kemudian menaikkan nilai back back++; Proses dequeue (pengambilan elemen) dilakukan dengan cara mengambil elemen paling depanA[0], kemudian jika ada elemen yang lain lakukan penggeseran kekiri satu langkah dari A[1] sampai dengan A[back].
Terdapat setidaknya 6 method/operasi dalam implementasi versi 1, yakni isEmpty, isFull, makeEmpty, dequeue, enqueue, dan doubleArray. LANGKAH PERCOBAAN 1: Langkah 1 : Definisikan langkah-langkah yang harus dikerjakan dalam setiap operasi yang tersebut diatas. Langkah 2: Mengkonversi kedalam coding untuk setiap operasinya pada kerangka class di bawah ini. public class queue_array1
{ private T[] A;// tipe elemen queue private int back;//untuk memaintain index setelah elemen paling blk. private static final int DEFAULT_CAPACITY = 10;//length daripada queue public queue_array1() {...}//konstruktor untuk menciptakan queue kosong public boolean isEmpty() {...}//memeriksa apakah queue kosong public boolean isFull() {...}//memeriksa apakah queue penuh public void makeEmpty() {...}//mengosongkan queue //mengambil 1 elemen dari queue, dan mengembalikan nilai yang diambil public T dequeue() {...} public void enqueue(T x) {...}//menambah 1 elemen ke dalam queue //mendobel-kan array dan melakukan copy, jika queue penuh private void doubleArray() {...} }
Anda diminta untuk mengisi kode java untuk setiap konstruktor dan method yang diimplementasikan (kurung yang kosong). Langkah 3: Simpan implementasi queue yang anda buat dengan nama queue_array1.java Langkah 4: Buat class test untuk menguji implementasi queue yang anda buat. Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
2
MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA) Berikut penjelasan implementasi queue versi 2: • • • •
•
Elemen Queue disimpan dalam array A Variabel back digunakan untuk memantain index setelah elemen queue paling belakangA[back] Variabel front digunakan untuk memantain index elemen queue paling depanA[front] Proses enqueue (penambahan elemen) dilakukan dengan cara memasukkan data kedalam elemen array index back A[back]=data, dan kemudian menaikkan nilai back back++; Proses dequeue (pengambilan elemen) dilakukan dengan cara mengambil elemen paling depanA[front], kemudian naikkan nilai variabel front.
Terdapat setidaknya 6 method/operasi dalam implementasi versi 2, yakni isEmpty, isFull, makeEmpty, dequeue, enqueue, dan doubleArray. LANGKAH PERCOBAAN 2: Langkah 1 : Definisikan langkah-langkah yang harus dikerjakan dalam setiap operasi yang tersebut diatas. Langkah 2: Mengkonversi kedalam coding untuk setiap operasinya pada kerangka class di bawah ini. public class queue_array2 { private T[] A;// tipe elemen queue private int back;//untuk memaintain index setelah elemen paling blk. private static final int DEFAULT_CAPACITY = 10;//length daripada queue public queue_array2() {...}//konstruktor untuk menciptakan queue kosong public boolean isEmpty() {...}//memeriksa apakah queue kosong public boolean isFull() {...}//memeriksa apakah queue penuh public void makeEmpty() {...}//mengosongkan queue //mengambil 1 elemen dari queue, dan mengembalikan nilai yang diambil public T dequeue() {...} public void enqueue(T x) {...}//menambah 1 elemen ke dalam queue //mendobel-kan array dan melakukan copy, jika queue penuh private void doubleArray() {...} }
Anda diminta untuk mengisi kode java untuk setiap konstruktor dan method yang diimplementasikan (kurung yang kosong). Langkah 3: Simpan implementasi queue yang anda buat dengan nama queue_array2.java Langkah 4: Buat class test untuk menguji implementasi queue yang anda buat.
Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
3
MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA) Berikut penjelasan implementasi queue versi 3:
•
Elemen Queue disimpan dalam array A Variabel back digunakan untuk memantain index setelah elemen queue paling belakangA[back] Variabel front digunakan untuk memantain index elemen queue paling depanA[front] Proses enqueue (penambahan elemen) dilakukan dengan cara memasukkan data kedalam elemen array index back A[back]=data, dan kemudian menaikkan nilai back back++, apabila nilai back berada diluar panjang array (>=A.length) dan queue tidak penuh, reset nilai back menjadi 0. Proses dequeue (pengambilan elemen) dilakukan dengan cara mengambil elemen paling depanA[front], kemudian naikkan nilai variabel front, apabila nilai front berada diluar panjang array (>=A.length), reset nilai front menjadi 0. Queue dikatakan penuh apabila front=back-1.
•
Queue dikatakan kosong apabila front=back.
• • • •
•
Terdapat setidaknya 6 method/operasi dalam implementasi versi 3, yakni isEmpty, isFull, makeEmpty, dequeue, enqueue, dan doubleArray. LANGKAH PERCOBAAN 3: Langkah 1 : Definisikan langkah-langkah yang harus dikerjakan dalam setiap operasi yang tersebut diatas. Langkah 2: Mengkonversi kedalam coding untuk setiap operasinya pada kerangka class di bawah ini. public class queue_array3 { private T[] A;// tipe elemen queue private int back;//untuk memaintain index setelah elemen paling blk. private static final int DEFAULT_CAPACITY = 10;//length daripada queue public queue_array3() {...}//konstruktor untuk menciptakan queue kosong public boolean isEmpty() {...}//memeriksa apakah queue kosong public boolean isFull() {...}//memeriksa apakah queue penuh public void makeEmpty() {...}//mengosongkan queue //mengambil 1 elemen dari queue, dan mengembalikan nilai yang diambil public T dequeue() {...} public void enqueue(T x) {...}//menambah 1 elemen ke dalam queue //mendobel-kan array dan melakukan copy, jika queue penuh private void doubleArray() {...} }
Anda diminta untuk mengisi kode java untuk setiap konstruktor dan method yang diimplementasikan (kurung yang kosong). Langkah 3: Simpan implementasi queue yang anda buat dengan nama queue_array3.java Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
4
MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA) Langkah 4: Buat class test untuk menguji implementasi queue yang anda buat.
Implementasi Queue dengan Linked List Struktur data queue dapat juga diimplementasikan dengan menggunakan linked list. Berikut penjelasan detail mengenai implementasi implementasi queue dengan linked list: • • •
•
Menggunakan 2 variabel reference objek yakni front dan back.. Queue dikatakan kosong apabila front=back=null. Proses enqueue dilakukan dengan cara: o Buat uat node baru N, kemudian masukkan data baru X ke dalam alam N. o Jika queue dalam keadaan kosong, atur nilai front=back=N. front=back= o Jika queue tidak kosong, tambahkan N dan update nilai back. Prosess dequeue dilakukan dengan cara menghapus elemen pertama (yang diacu oleh variabel front). ).
Gambar 1. Ilustrasi Implementasi Queue dengan Linked List Dalam gambar1 di atas, terlihat bahwa ada 4 buah buah data. Setiap data mempunyai anggota yang menunjuk ke data berikutnya, kecuali elemen ele yang paling belakang menunjuk ke NULL. NULL berarti bahwa elemen tersebut tidak menunjuk ke posisi po apapun. Elemen lemen paling depan ditunjuk oleh variabel front, ront, sedangkan elemen paling belakang ditunjuk oleh variabel back. Setiap elemen dari queue mempunyai memp 2 bagian yaitu bagian data yang bernilai dengan data,, dan sebagian lagi adalah penunjuk penu ke data berikutnya (next). Terdapat setidaknya 4 method/operasi method/op dalam implementasi queue dengan linked list, list yakni isEmpty, makeEmpty, ty, dequeue, enqueue.
LANGKAH PERCOBAAN 4: Langkah 1 : Definisikan langkah-langkah langkah langkah yang harus dikerjakan dalam setiap operasi yang tersebut diatas. Langkah 2: Mengkonversi kedalam coding untuk setiap operasinya pada pada kerangka kelas di bawah ini.
Abdul Aziz, Jurusan rusan Informatika FMIPA UNS 2012 201
5
MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA) class ListNode { // Data member private Object data; //menyimpan data queue private ListNode next; // Reference ke node berikutnya // Konstruktor, nextNode di set null ListNode(Object d, ListNode nextNode) {... } }
public class queue_linkedlist { private ListNode front;//menunjuk node paling depan private ListNode back;//menunjuk node paling belakang public public public public public
queue_linkedlist() {...}//konstruktor boolean isEmpty() {...}//memeriksa apakah queue kosong void makeEmpty() {...}//mengosongkan isi queue T dequeue() {...}//mengambil 1 elemen dari queue void enqueue(T x) {...}//menambah 1 elemen ke dalam queue
}
Anda diminta untuk mengisi kode java untuk setiap konstruktor dan method yang diimplementasikan (kurung yang kosong) sesuai dengan definisi sebelumnya. Langkah 3: Simpan implementasi queue yang anda buat dengan nama queue_linkedlist.java Langkah 4: Buat class test untuk menguji implementasi queue yang anda buat.
LAPORAN PRAKTIKUM BERISI PEMBAHASAN LATIHAN PERCOBAAN DAN SOAL. DIKUMPULKAN MINGGU DEPAN.
Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
6
