Queue / Antrian

Queue (antrian) adalah struktur data dimana data yang pertama kali dimasukkan adalah data yang pertama kali bisa dihapus. Atau bisa juga disebut dengan struktur data yang menggunakan mekanisme FIFO (First In First Out).
queue

queue

Queue dalam kehidupan sehari-hari seperti antrian pada penjualan tiket kereta api, dimana orang yang pertama datang adalah orang yang pertama kali dilayani untuk membeli tiket. Jika ada orang baru yang datang akan membali tiket, maka posisinya berada pada urutan paling belakang dalam antrian tersebut. Orang yang berada pada posisi terakhir dalam antrian adalah yang terakhir kali dapat dilayani dan memperoleh tiket kereta api (kalau kurang beruntung, maka akan kehabisan tiket). Contoh lain adalah nasabah yang antri di teller bank, paket data yang menunggu untuk ditransmisikan lewat internet, antrian printer dimana terdapat antrian print job yang menunggu giliran untuk menggunakan printer, dsb.

Istilah-istilah yang digunakan dalam queue (antrian)
Memasukkan data (insert) disebut juga dengan put, add, atau enqueue. Menghapus data (remove) biasa disebut dengan istilah delete, get, atau dequeue. Bagian belakang queue, dimana data bisa dimasukkan disebut dengan back, tail (ekor), atau end (akhir). Sedangkan bagian depan (front) queue dimana data bisa dihapus juga biasa disebut dengan istilah kepala (head).Circular Queue
Di dunia nyata apabila seseorang sedang mengantri (misalnya antri tiket kereta api), apabila telah dilayani dan memperoleh tiket, maka ia akan keluar dari antrian dan orang-orang yang berada di belakangnya akan bergerak maju ke dapan. Kita bisa saja menggerakkan setiap item data ke depan apabila kita menghapus data yang terdepan, tetapi hal ini kurang efektif. Sebaliknya kita tetap menjaga setiap item data di posisinya, yang kita lakukan hanyalah merubah posisi front dan rear saja.
Yang menjadi permasalahan adalah apabila posisi rear berada pada bagian akhir dari array (atau pada nomor indeks yang terbesar). Meskipun ada bagian yang kosong di awal-awal array – karena mungkin data telah dihapus, data baru tidak bisa dimasukkan lagi karena rear-nya sudah tidak bisa bergerak lagi. Atau mungkinkah posisi rear nya bisa berpindah? Situasi seperti itu bisa dilihat seperti gambar berikut:

circular queueUntuk menghindari permasalahan seperti itu (tidak bisa memasukkan data baru) – meskipun queue-nya belum penuh, maka front dan rear-nya berputar (kembali) ke bagian awal array. Kejadian seperti ini dinamakan dengan circular queue (atau kadang-kadang disebut juga dengan istilah ring buffer). Kejadian seperti ini seperti terlihat pada gambar berikut:
circular queue

circular queue

Perhatikan bahwa setelah rear berputar (kembali) ke bagian awal array, posisinya sekarang di bawah front, kebalikan dari posisi aslinya (front berada di bawah rear). Coba hapus beberapa data sehingga pada suatu saat front juga akan berputar (balik) ke bagian awal array, sehingga front dan rear akan ke susunan aslinya (front di bawah rear).

Queue.java

class Queue
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
private int nItems;
//————————————————————–
public Queue(int s) // konstruktor
{
maxSize = s;
queArray = new long[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//————————————————————–
public void insert(long j) // letakkan item (data) di posisi belakang dari queue
{
if(rear == maxSize-1) //
rear = -1;
queArray[++rear] = j; //naikkan rear dan masukkan item (data) pada posisi rear yang baru
nItems++; //tambah satu item lagi
}

//————————————————————–
public long remove() // hapus item (data) yang berada pada posisi front
{
long temp = queArray[front++]; //dapatkan nilainya dan naikkan front
if(front == maxSize) //
front = 0;
nItems–; // item (data) berkurang satu
return temp;
}
//————————————————————–
public long peekFront() //
{

return queArray[front];
}
//————————————————————–
public boolean isEmpty() //benar jika queue-nya kosong
{
return (nItems==0);
}
//————————————————————–
public boolean isFull() // benar jika queue-nya penuh
{
return (nItems==maxSize);
}
//————————————————————–
public int size() // jumlah ietm (data) dalam queue
{
return nItems;
}
//————————————————————–
} // end class Queue

QueueApp.java

class QueueApp
{
public static void main(String[] args)
{
Queue theQueue = new Queue(5); // queue menampung 5 item (data)
theQueue.insert(10); // masukkan 4 item (data)
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove(); // hapus 3 item (data)
theQueue.remove(); // (10, 20, 30)
theQueue.remove();
theQueue.insert(50); // masukkan 4 item (data) lagi
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while( !theQueue.isEmpty() ) // hapus dan tampilkan
{ // all items

long n = theQueue.remove(); // (
System.out.print(n);
System.out.print(“ “);
}
System.out.println(“”);
} // end main()
} // end class QueueApp

method insert()
Method insert() mengasumsikan bahwa queue tidak penuh (full). Kita tidak melihatnya dalam main(), tetapi kita bisa memanggil insert() hanya setelah memanggil isFull() dan memperoleh nilai kembalian yang salah. Pengisian data dengan cara menaikkan rear dan mengisikan data baru tersebut pada rear yang baru sekarang. Tetapi, jika rear berada di puncak array, pada maxSize-1, maka harus kembali ke posisi terbawah array sebelum penyisipan dilakukan. Caranya dengan memberi nilai rear=-1, sehingga jika terjadi kenaikan pada pada rear, maka rear akan menjadi 0, dasar dari array. Dan akhirnya, nItem bertambah.

Method remove()
method remove mengasumsikan queue-nya tidak kosong. Untuk meyakinkan bahwa queue-nya tidak kosong, anda harus memanggil method isEmpty(). Penghapusan selalu dimulai dengan memperoleh nilai pada front dan kemudian mengurangi front. Jika front-nya terletak pada akhir array, maka harus kembali ke 0. Kemudian nItems dikurangi.

Method peek()
untuk mendapatkan nilai pada front.

Method isEmpty(), isFull(), and size()
untuk mengecek nItems, apakah kosong atau penuh.