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 :
1. Enqueue : proses penambahan elemen di posisi belakang
2. Dequeue : proses pengambilan elemen di posisi depan
Selain operasi dasar di atas, ada pula operasi-operasi lain yang dapat dilakukan terhadap sebuah queue yaitu :
1. Operasi pemeriksaan queue kosong (fungsi kosong)
2. Operasi pemeriksaan queue penuh (fungsi penuh).
3. Operasi inisialisasi queue (fungsi inisialisasi)
Adapun presentasi queue dapat dilakukan dengan 2 cara yaitu :
Dengan menggunakan array statis
Operasi-operasi yang dapat dilakukan dalam queue yang menggunakan representasi array statis adalah :
- Pendeklarasian sebuah queue
Setiap queue memiliki elemen-elemen (field) berupa posisi depan, posisi belakang, elemen antrian, dan maksimal elemennya.
Adapun pendeklarasian queue dalam bahasa C adalah :
#define maks 5
struct TQueue{
int depan,belakang;
int maks_queue;
int antrian[maks];
};
TQueue Q,Queue,Q2;//deklarasi variable bertipe TQueue
- Inisialisasi Queue
Inisialisasi
queue adalah proses pemberian nilai 0 untuk field depan dan belakang
dari queue dan juga pemberian nilai maks ke maks_queue yang menunjukan
banyaknya maksimal data dalam queue.
Karena dalam bahasa C elemen
sebuah array dimulai dengan 0 maka proses inisialisasi nilai depan dan
belakang bukan 0 tetapi -1 sehingga ketika ada proses penambahan elemen
(enqueue) akan bernilai 0 sehingga elemen tersebut akan disimpan dalam
elemen antrian pada posisi 0.
Implementasi fungsi inisialisasi queue dalam bahasa C adalah
void inisialisasi(TQueue *Q)
{
Q->maks_queue=maks;
Q->depan=-1;
Q->belakang=-1;
}
Cara pemanggilannya adalah :
Inisialisasi(&Q);
- Fungsi Kosong
Fungsi
kosong digunakan untuk memeriksa apakan keadaan queue tidak memiliki
elemen. Fungsi kosong didapatkan dengan memeriksa field belakang dari
queue. Jika field belakang bernilai 0 maka berarti queue kosong dan jika
tidak 0 maka berarti queue mempunyai elemen.
Implementasi dalam
bahasa C agak berbeda karena elemen array dimulai dari 0 sehingga
pemeriksaan nilai belakang dilakukan dengan membandingkannya dengan
nilai -1. Jika nilai belakang bernilai -1 maka queue kosong (true) dan
jika lebih dari -1 berarti queue tidak kosong (false). Sehingga
implementasinya dalam bahasa C adalah :
int kosong(TQueue Q)
{
if (Q.belakang==-1)
return 1;
else
return 0;
}
Cara pemanggilannya adalah :
if(kosong(Q))// jika queue Q kosong
……
- Fungsi Penuh
Fungsi
penuh berguna untuk memeriksa apakah suatu queue telah penuh. Fungsi
ini diperlukan ketika proses enqueue. Fungsi ini akan bernilai benar
(true) jika field belakang sama dengan nilai maks_queue jika tidak sama
dengan berarti queue belum penuh.
Dalam bahasa C perbandingan yang
dilakukan adalah bukan dengan maks_queue tetapi dengan nilai
maks_queue-1 karena elemen array dalam bahasa C dimulai dari posisi 0.
Implementasi dalam bahasa C adalah :
int penuh(TQueue Q)
{
if(Q.belakang==Q.maks_queue-1)
return 1;
else
return 0;
}
Cara pemanggilannya adalah :
If(!penuh(Q)) //if queue Q tidak(!) penuh
.....
- Operasi Enqueue
Proses
enqueue adalah proses untuk penambahan di posisi belakang. Penambahan
ini dilakukan jika kondisi queue tidak penuh. Jika keadaan masih kosong,
maka field depan dan belakang bernilai 1 tetapi jika sudah mempunyai
elemen maka yang nilai belakang harus bertambah 1. Kemudian data baru
disimpan di array pada posisi belakang.
Implementasi dalam C harus
melakukan penyesuaian karena elemen array C dimulai dari 0 sehingga
ketika queue masih kosong pemberian nilai depan dan belakang adalah 0
bukan 1. Untuk lebih jelasnya perhatikan potongan program di bawah ini :
void enqueue(TQueue *Q, int data)
{
if(!penuh(*Q))
{
if(empty(*Q)
{
Q->depan=0;
Q->belakang=0;
}
else
Q->belakang++;
Q->antrian[Q->belakang]=data;
}
else
printf("Queue Telah Penuh\n");
}
Cara penggunaannya :
int data=7
enqueue(&Q,data);
- Operasi Dequeue
Operasi
dequeue adalah proses pengambilan elemen queue. Tentunya elemen yang
diambil selalu dari elemen pertama (1). Setelah elemen pertama diambil,
maka akan diperlukan proses pergeseran elemen data setelah elemen data
yang diambil (dari posisi ke-2 sampai posisi paling belakang), dan
kemudian posisi belakang akan dikurangi 1 karena ada data yang diambil.
Implementasi dalam bahasa C dilakukan dengan pengambilan elemen pada posisi 0, sehingga fungsi dequeue-nya menjadi :
int dequeue(TQueue *Q)
{
int data,i;
if(!kosong(*Q))
{
data=Q->antrian[Q->depan];
for(i=0;i<=Q->belakang-1;i++)
Q->antrian[i]=Q->antrian[i+1];
Q->belakang--;
return data;
}
else
{
printf("Queue Kosong.\n");
return 0;
}
}
Cara penggunaan fungsi tersebut adalah :
int data;
data=dequeue(&Q); //ambil data dari dequeue pada queue Q
printf(“%d”,data);
2. Dengan menggunakan linked list.
Proses
penyimpanan elemen queue dalam linked list mirip dengan operasi pada
single linked list yang menggunakan penyimpanan tambah akhir dan hapus
awal.
Operasi Enqueue
Proses enqueue dalam queue linked list
adalah dengan menambahkan elemen baru ke posisi paling belakang
(sambungkan field berikutnya dari field belakang ke posisi pointer
baru). Setelah itu, pointer penunjuk belakang harus berpindah ke posisi
baru tersebut. Proses ini seperti proses penambahan di belakang pada
single linked list.
Operasi Dequeue
Proses dequeue untuk queue
linked list adalah dengan mengambil data yang ditunjuk pointer depan
dan kemudian pointer yang depan tersebut diambil dan kemudian dihapus.
Pointer depan harus berpindah ke elemen antrian berikutnya. Proses
tersebut dilakukan hanya jika linked list tidak kosong. Proses ini mirip
dengan proses penghapusan data awal pada single linked list.
QUEUE DENGAN CIRCULAR ARRAY
Jika
kita menggunakan array untuk queue seperti di atas, maka ketika ada
proses pengambilan (dequeue) ada proses pergeseran data. Proses
pergeseran data ini pasti memerlukan waktu apalagi jika elemen queue-nya
banyak. Oleh karena itu solusi agar proses pergeseran dihilangkan
adalah dengan metode circular array.Atau agar lebih jelas, array di atas
dapat dibayangkan ke dalam bentuk seperti lingkaran di bawah ini.
Aturan-aturan dalam queue yang menggunakan circular array adalah :
1. Proses penghapusan dilakukan dengan cara nilai depan (front) ditambah 1 : depan=depan + 1.
2. Proses penambahan elemen sama dengan linear array yaitu nilai belakang ditambah 1 : belakang=belakang + 1.
3. Jika depan = maks dan ada elemen yang akan dihapus, maka nilai depan = 1.
4. Jika belakang = maks dan depan tidak 1 maka jika ada elemen yang akan ditambahkan, nilai belakang=1
5.
Jika hanya tinggal 1 elemen di queue (depan = belakang), dan akan
dihapus maka depan diisi 0 dan belakang diisi dengan 0 (queue kosong).
Operasi-operasi yang dapat terjadi dalam queue yang menggunakan circular array adalah :
1. Pendeklarasian Queue
Setiap queue memiliki elemen-elemen (field) berupa posisi depan, posisi belakang, elemen antrian, dan maksimal elemennya.
2. Inisialisasi Queue
Inisialisasi
queue adalah proses pemberian nilai 0 untuk field depan dan belakang
dari queue dan juga pemberian nilai maks ke maks_queue yang menunjukan
banyaknya maksimal data dalam queue.
Karena dalam bahasa C elemen
sebuah array dimulai dengan 0 maka proses inisialisasi nilai depan dan
belakang bukan 0 tetapi -1 sehingga ketika ada proses penambahan elemen
(enqueue) akan bernilai
3. Fungsi Kosong
Suatu queue yang
menggunakan circular array dapat dikatakan kosong jika nilai yang
menunjuk posisi depan atau belakang mempunyai nilai 0.
Implementasi
dalam bahasa C, perbandingan posisi depan atau belakang dilakukan bukan
dengan angka 0 tetapi angka -1 karena angka 0 menunjukan elemen pertama
dari array.
4. Fungsi Penuh
Suatu queue akan disebut penuh jika
terjadi 2 hal yaitu jika nilai depan mempunyai nilai 1 dan posisi
belakang sama dengan maks_queue atau jika posisi depan sama dengan
posisi belakang +1. Jika salah satu dari 2 hal tersebut terjadi maka
fungsi penuh mempunyai nilai true dan jika tidak terjadi 2 hal tersebut
maka fungsi bernilai false.
Implementasi dalam bahasa C agar beda
karena posisi awal array bukan 1 tapi 0 dan posisi terakhir data adalah
maks_queue-1 bukan maks_queue.
5. Operasi Enqueue
Proses enqueue
data hanya bisa dilakukan jika queue tidak kosong. Ada beberapa hal yang
harus diperhatikan ketika akan melakukan enqueue pada circular array,
diantaranya adalah :
- Kondisi ketika queue masih kosong. Jika ini terjadi, maka posisi depan dan belakang bernilai 0.
-
Ketika ketika nilai belakang sama dengan maks_queue, maka posisi
belakang adalah 0. Ini terjadi ketika posisi depan lebih besar dari 0
(pernah ada dequeue).
- Ketika nilai belakang masih lebih kecil dari maks_queue maka posisi belakang ditambah 1 : belakang=belakang+1;
Dari
ketentuan-ketentuan di atas dapat diimplementasikan dalam bahasa C
dengan mengganti beberapa hal yaitu posisi perbandingan/pengisian dengan
nilai 0 diganti dengan perbandingan/pengisian dengan nilai -1 dan
perbandingan dengan nilai maks_queue diganti dengan maks_queue-1. Itu
disebabkan karena dalam bahasa C array dimulai dari 0.
6. Operasi Dequeue
Proses
dequeue hanya bisa dilakukan jika queue dalam keadaan tidak kosong. Ada
beberapa kondisi yang harus diperhatikan ketika dequeue elemen queue
yaitu :
- Kondisi ketika posisi depan sama dengan posisi belakang
(queue hanya memiliki 1 elemen) maka nilai depan dan belakang diisi
dengan 0 (queue kosong).
- Jika posisi depan sama dengan posisi maks_queue maka posisi depan berpindah ke 1.
- Selain itu, posisi depan ditambah dengan 1 : depan=depan+1
Ketika
kita mengimplementasikannya dalam bahasa C, maka ada beberapa hal yang
harus diganti adalah semua pengisian/perbandingan dengan angka 1 diganti
dengan 0 (karena elemen array dalam bahasa C adalah 0), serta ketika
ada perbandingan/pengisian dengan nilai 0 diganti dengan -1 dan
perbandingan/pengisian dengan nilai maks_queue diganti dengan
maks_queue-1.
