Antrian (queue) adalah struktur data mirip dengan tumpukan, yaitu terdiri dari item dalam urutan tertentu. Antrian memiliki dua ujung, yang disebut ujung depan dan ujung belakang. Item selalu dimasukkan dari belakang antrian, dan selalu dikeluarkan dari depan antrian. Operasi memasukkan dan mengeluarkan item dari dalam antrian disebut "masuk" dan "keluar" (dalam bahasa Inggris disebut enqueue dan dequeue).
Suatu item yang ditambahkan di belakang antrian tidak bisa dihapus sebelum item di depannya dihapus. Mirip seperti antrian pada kasir atau pada customer service di bank misalnya. Customer akan dilayani dalam urutan ketika mereka datang.
Antrian bisa menampung item dengan jenis apa saja. Untuk antrian int, operasi masuk dan keluar dapat diimplementasikan sebagai metode instansi dalam kelas "AntrianInt". Kita juga membutuhkan metode instansi untuk menguji apakah antrian kosong atau tidak:
Antrian bisa diimplementasikan dalam bentuk list berantai atau array. Akan tetapi implementasi yang efisien dalam bentuk array sedikit lebih sulit, sehingga akan kita abaikan dalam diskusi kita.
Dalam implementas dalam bentuk list berantai, item bertama adalah item di depan antrian. Untuk mengeluarkan item dari depan antrian, kita dapat lakukan seperti mengambil item dari atas tumpukan.
Belakang antrian adalah akhir dari list. Unutk memasukkan item ke dalam antrian, kita harus mengeset pointer di akhir simpul untuk menunjuk ke simpul baru yang berisi item yang akan kita tambahkan. Kita bisa menggunakan perintah seperti "buntut.berikut = simpulBaru;", di mana buntut adalah pointer ke simpul terakhir dari list.
Jika kepala adalah pointer ke simpul pertama, maka kita bisa mendapat pointer ke simpul terakhir dengan menggunakan :
Akan tetapi, tentunya akan sangat tidak efisien jika kita harus melakukan perulangan terus menerus setiap kali kita memasukkan item baru ke dalam antrian. Dengan alasan efisiensi, kita akan menyimpan pointer ke akhir simpul sebagai variabel instansi. Kita harus selalu ingat untuk terus mengupdate isi variabel ini setiap kali simpul baru ditambahkan ke akhir list.
Dengan pengetahuan di atas, kita bisa membuat kelas "AntrianInt" dengan mudah sebagai berikut :
Antrian digunakan dalam komputer (dan juga dalam kehidupan nyata) ketika hanya satu item yang bisa diproses pada suatu saat, akan tetapi banyak item bisa menunggu untuk diproses, misalnya :
- Dalam Java program yang memiliki banyak threads, thread yang ingin diolah dalam CPU disimpan di dalam antrian. Ketika thread baru dimulai, thread ini ditambahkan ke dalam antrian. Thread akan dihapus dari depan antrian, diolah oleh CPU, dan kemudian -- jika belum selesai -- diletakkan kembali di belakang antrian untuk menunggu giliran berikutnya.
Suatu item yang ditambahkan di belakang antrian tidak bisa dihapus sebelum item di depannya dihapus. Mirip seperti antrian pada kasir atau pada customer service di bank misalnya. Customer akan dilayani dalam urutan ketika mereka datang.
void masul(int N) // Tambah N di belakang antrian int keluar() // Keluarkan antrian dari depan dan kembalikan isinya boolean isKosong() // Kembalikan true jika antrian kosong
Antrian bisa diimplementasikan dalam bentuk list berantai atau array. Akan tetapi implementasi yang efisien dalam bentuk array sedikit lebih sulit, sehingga akan kita abaikan dalam diskusi kita.
Dalam implementas dalam bentuk list berantai, item bertama adalah item di depan antrian. Untuk mengeluarkan item dari depan antrian, kita dapat lakukan seperti mengambil item dari atas tumpukan.
Belakang antrian adalah akhir dari list. Unutk memasukkan item ke dalam antrian, kita harus mengeset pointer di akhir simpul untuk menunjuk ke simpul baru yang berisi item yang akan kita tambahkan. Kita bisa menggunakan perintah seperti "buntut.berikut = simpulBaru;", di mana buntut adalah pointer ke simpul terakhir dari list.
Jika kepala adalah pointer ke simpul pertama, maka kita bisa mendapat pointer ke simpul terakhir dengan menggunakan :
Simpul buntut; // Pointer ini akan menunjuk ke simpul terakhir buntut = kepala; // Mulai dari simpul pertama while (buntut.berikut != null) { buntut = buntut.berikut; } // Di sini, buntut.berikut berisi null, artinya buntut adalah // simpul terakhir di dalam list
Akan tetapi, tentunya akan sangat tidak efisien jika kita harus melakukan perulangan terus menerus setiap kali kita memasukkan item baru ke dalam antrian. Dengan alasan efisiensi, kita akan menyimpan pointer ke akhir simpul sebagai variabel instansi. Kita harus selalu ingat untuk terus mengupdate isi variabel ini setiap kali simpul baru ditambahkan ke akhir list.
Dengan pengetahuan di atas, kita bisa membuat kelas "AntrianInt" dengan mudah sebagai berikut :
public class AntrianInt { private static class Simpul { // Objek bertipe Simpul berisi item dalam bentuk // list berantai int item; Simpul berikut; } // Menunjuk ke simpul pertama pada antrian // Jika antrian kosong, maka kepala berisi null private Simpul kepala = null; private Simpul buntut = null; // Menunjuk ke simpul akhir pada antrian void masuk( int N ) { // Menambahkan N ke akhir antrian Simpul buntutBaru = new Simpul(); // Simpul baru untuk menampung item baru buntutBaru.item = N; if (kepala == null) { // Antrian kosong, sehingga simpulBaru menjadi // satu-satunya simpul di dalam list. Sehingga // kepala dan buntut sama-sama menunjuk ke simpulBaru kepala = buntutBaru; buntut = buntutBaru; } else { // Simpul baru menjadi buntut antrian // (kepala tidak berpengaruh apa-apa) buntut.berikut = buntutBaru; buntut = buntutBaru; } } int keluar() { // Keluarkan item dari kepala antrian // Bisa melempar NullPointerException. int itemPertama = kepala.item; kepala = kepala.berikut; // Sekarang item kedua menjadi kepala if (kepala == null) { // Sekarang antrian kosong. Simpul yang telah dihapus adalah // kepala sekaligus buntut, karena simpul ini adalah satu-satunya // yang ada di dalam antrian. Isi buntut dengan null. buntut = null; } return itemPertama; } boolean isKosong() { // Kembalikan true jika antrian kosong return (kepala == null); } } // akhir kelas AntrianInt
- Dalam Java program yang memiliki banyak threads, thread yang ingin diolah dalam CPU disimpan di dalam antrian. Ketika thread baru dimulai, thread ini ditambahkan ke dalam antrian. Thread akan dihapus dari depan antrian, diolah oleh CPU, dan kemudian -- jika belum selesai -- diletakkan kembali di belakang antrian untuk menunggu giliran berikutnya.
- Event seperti ketikan tombol dan klik mouse disimpan dalam antrian yang disebut "antrian event". Program akan menghapus item dari antrian item dan mengolahnya satu per satu. Mungkin saja terjadi beberapa event diterima ketika satu event sedang diproses, akan tetapi event akan diolah berdasarkan urutan kedatangannya
- ServerSocket, memiliki antrian di dalamnya yang berisi permintaan sambungan yang diterima akan tetapi belum dilayani. Metode accept() pada kelas ServerSocket menerima permintaan sambungan berikutnya dari depan antrian ini.
Antrian disebut mengikuti kebijakan FIFO (First In First Out, atau Pertama Masuk Pertama Keluar). Atau dalam bahasa awam, pertama datang dan pertama dilayani. Di lain pihak, tumpukan mengikuti prinsip LIFO (Last In First Out, Terakhir Masuk Pertama Keluar). Item yang bisa keluar dari tumpukan adalah item terkakhir yang dimasukkan. Seperti antrian, tumpukan juga bisa digunakan untuk menampung item yang sedang menunggu untuk diproses (walaupun dalam aplikasi di mana antrian biasa digunakan, tumpukan adalah antrian yang tidak adil).
Antrian disebut mengikuti kebijakan FIFO (First In First Out, atau Pertama Masuk Pertama Keluar). Atau dalam bahasa awam, pertama datang dan pertama dilayani. Di lain pihak, tumpukan mengikuti prinsip LIFO (Last In First Out, Terakhir Masuk Pertama Keluar). Item yang bisa keluar dari tumpukan adalah item terkakhir yang dimasukkan. Seperti antrian, tumpukan juga bisa digunakan untuk menampung item yang sedang menunggu untuk diproses (walaupun dalam aplikasi di mana antrian biasa digunakan, tumpukan adalah antrian yang tidak adil).
Tidak ada komentar:
Posting Komentar