CIRCULAR QUEUE

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:

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

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