Rabu, 14 Desember 2011

Antrian (Struktur Data Berantai-Java)

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:
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
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.

- 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).

Tidak ada komentar:

Posting Komentar