1. Pengertian Queue
Kaidah utama dalam konsep queue adalah
FIFO yang merupakan singkatan dari First In First Out, artinya adalah
data yang pertama kali dimasukkan atau disimpan, maka data tersebut adalah yang
pertama kali akan diakses atau dikeluarkan. Analoginya sama dengan antrian di
sebuah loket pembelian tiket kereta, orang yang datang lebih dahulu, maka akan
dilayani terlbih dahulu, dan akan selesai lebih dulu dari orang-orang yang
datang setelahnya. Gambar di bawah ini mengilustrasikan kerja sebuah queue:
2. Deklarasi queue dalam program
Sebuah queue di dalam program komputer dideklarasikan sebagai sebuah
tipe bentukan baru, di dalam Bahasa C, biasa disebut struct. Sebuah
struktur data dari sebuah queue setidaknya harus mengandung dua tiga
variabel, yakni variabel HEAD yang
akan berguna sebagai penanda bagian depan antrian, variabel TAIL yang akan berguna sebagai penanda
bagian belakang antrian dan ARRAY DATA
dari yang akan menyimpan data-data yang dimasukkan ke dalam queue
tersebut. Berikut adalah syntax untuk mendeklarasikan struktur data
dari sebuah queue menggunakan Bahasa C:
|
typedef
struct
{
int HEAD,
TAIL;
int
data[max+1];
}Queue;
|
dimana, nilai
MAX didefinisikan sebagai jumlah tumpukan maksimum yang dapat disimpan dalam queue.
Setelah struktur data dari queue didefinisikan dengan syntax di
atas, maka setelah itu dapat dibuat variabel-variabel baru yang mengacu pada
tipe data Queue di atas,
misalkan membuat sebuah variabel bernama antrian yang bertipe Queue: Queue
antrian; 8
Dalam tulisan ini,
sebuah queue didefinisikan dengan array berukuran MAX + 1,
maksudnya adalah agar elemen array ke-0 tidak digunakan untuk menyimpan
data, melainkan hanya sebagai tempat „singgah‟ sementara
untuk variabel HEAD dan TAIL. Sehingga, jika HEAD dan TAIL berada pada elemen array
ke-0, berarti queue tersebut dalam kondisi kosong (tidak ada data
yang disimpan). Berikut adalah ilustrasi dari sebuah queue kosong dengan
ukuran nilai MAX = 8:
3.
Operasi-operasi dasar dalam queue
Pada dasarnya, operasi-operasi dasar pada queue mirip dengan
operasi-operasi dasar pada stack. Perbedaannya hanya pada prosedur push
dan pop saja. Pada queue, prosedur yang berfungsi untuk memasukkan data/
nilai ke dalam antrian adalah enqueue, sedangkan prosedur untuk
mengeluarkan data/ nilai dari antrian adalah dequeue.
a. Prosedur
create Empty
Sama pada stack,
prosedur ini berfungsi untuk mengosongkan queue dengan cara meletakkan
HEAD dan TAIL pada indeks array ke-0. Berikut deklarasi prosedur
createEmpty pada queue dalam Bahasa C:
|
void
createEmpty()
{
antrian.HEAD
= 0;
antrian.TAIL
= 0;
}
|
b. Prosedur
enqueue
Prosedur ini
digunakan untuk memasukkan sebuah data/ nilai ke dalam queue.
Sebelum sebuah data/ nilai dimasukkan ke dalam queue, maka prosedur ini
terlebih dahulu melakukan pengecekan terhadap posisi HEAD dan TAIL. Jika posisi
HEAD dan TAIL masih berada pada indeks ke-0 (artinya queue masih kosong),
maka prosedur ini akan menempatkan HEAD dan TAIL pada indeks ke-1 terlebih
dahulu, baru setelah itu memasukkan data/ nilai ke dalam array data queue.
Namun, jika posisi HEAD dan TAIL tidak berada pada posisi ke-0, maka posisi
TAIL yang akan dinaikkan satu level. Jadi, pada proses enqueue, TAIL-lah yang
berjalan seiring masuknya data baru ke dalam antrian, sedangkan HEAD akan tetap
pada posisi ke-1. Berikut deklarasi prosedur enqueue dalam Bahasa C:
|
void enqueue(int x)
{
if ((antrian.HEAD ==
0) && (antrian.TAIL == 0))
{
antrian.HEAD = 1;
antrian.TAIL = 1;
}
else
{
antrian.TAIL =
antrian.TAIL + 1;
}
antrian.data[antrian.TAIL]
= x;
}
|
Pada
deklarasi prosedur enqueue di atas, prosedur memiliki sebuah parameter formal
yang bernama „x‟
yang bertipe integer. Parameter formal „x‟ ini berguna untuk menerima kiriman nilai
dari program utama (void main()) yakni berupa sebuah bilangan integer yang
akan dimasukkan ke dalam queue.
c. Prosedur
dequeue
Prosedur ini
digunakan untuk mengeluarkan atau membuang sebuah data/ nilai yang
paling awal masuk (yang berada pada posisi HEAD, yakni yang paling depan dari
antrian) ke dalam queue. Pekerjaan yang dilakukan oleh prosedur ini
adalah menaikkan nilai HEAD satu level. Jadi, setiap satu kali data dikeluarkan,
maka posisi HEAD naik bertambah satu level. Misalkan HEAD berada pada indeks
ke-1, maka ketika akan mengeluarkan/ menghapus data pada posisi paling depan
(pada posisi HEAD), prosedur ini akan menaikkan posisi HEAD ke indeks array ke-2.
Berikut deklarasi
prosedur pop dalam Bahasa C:
|
void
Dequeue(){
if (q.head
> q.tail) {
q.head =
0;
q.tail =
0;
}
q.head =
q.head + 1;
}
|
Ketika
posisi HEAD sudah melewati posisi TAIL (HEAD > TAIL), berarti sudah tidak
ada lagi data/ nilai di dalam queue tersebut, maka saat itu terjadi,
HEAD dan TAIL dikembalikan ke posisi ke-0.
d. Fungsi Is Empty
Sama seperti
fungsinya pada stack, fungsi ini berfungsi untuk melakukan pengecekan
terhadap queue, apakah queue tersebut kosong atau tidak.
Jika queue tersebut kosong (artinya, HEAD dan TAIL berada pada posisi 0,
atau bisa juga ketika HEAD > TAIL), maka fungsi akan mengembalikan nilai 1 (true),
tetapi jika queue tersebut tidak kosong/ berisi (artinya, HEAD dan TAIL
tidak berada pada posisi 0), maka fungsi akan mengembalikan nilai 0 (false).
Berikut deklarasi fungsi IsEmpty dalam Bahasa C:
|
int
IsEmpty()
{
if
((antrian.HEAD> antrian.TAIL) || (antrian.HEAD == 0) &&
(antrian.TAIL
== 0))
return 1;
else
return 0;
}
|
e. Fungsi Is Full
Fungsi ini
berfungsi untuk melakukan pengecekan terhadap queue, apakah queue tersebut
penuh atau tidak. Jika queue tersebut penuh (artinya, TAIL berada
pada posisi MAX), maka fungsi akan mengembalikan nilai 1 (true), tetapi
jika queue tersebut tidak penuh (artinya, TAIL tidak berada pada posisi
MAX), maka fungsi akan mengembalikan nilai 0 (false). Berikut deklarasi
fungsi IsFull dalam Bahasa C:
|
int
IsFull()
{
if
(antrian.TAIL == max)
return 1;
else
return 0;
}
|
4. Contoh
program implementasi queue
Berikut adalah
contoh kode program dalam Bahasa C yang mengimplementasikan konsep queue.
Pada program ini, user akan menginputkan data satu per satu, kemudian
setelah selesai menginputkan data ke dalam queue, maka program akan
menampilkan semua isi queue.
|
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
#define n
20
int q[n],
f, r, x;
void
awal()
{
f=0;
r=-1;
}
void
insert()
{
if (r<n-1)
{
r=r+1;
q[r]=x;
}
else
{
cout<<"ANTRIAN
PENUH";
}
}
void
deleteq()
//hanya
menampilkan satu data terdepan
//pakai
while kalau mau menampilkan semua data antrian
{
if(f<r+1)
{
x=q[f];
f=f+1;
cout<<x;
if((f==r+1) && (r==n-1))
{
awal();
}
}
else
{
cout<<"ANTRIAN
KOSONG";
}
}
void
main()
{
int pilih;
awal();
atas:
cout<<endl<<"1.
INSERT DATA"<<endl;
cout<<"2. DELETE
DATA"<<endl;
cout<<"3. EXIT
DATA"<<endl;
cout<<"MASUKKAN PILIHAN ANDA :
";
cin>>pilih;
switch(pilih)
{
case
1 :
if(r<n-1)
{
cout<<"MASUKKAN
BILANGAN : ";
cin>>x;
insert();
}
else
{
cout<<"ANTRIAN
PENUH";
}
goto atas;
break;
case 2 :
deleteq();
break;
case
3 :
exit;
break;
default
:
cout<<"MASUKKAN
ANGKA ANTARA 1 SAMPAI 3";
goto
atas;
break;
}
getch();
}
|
REFERENSI :
http://suputradwipratama274.blogspot.com/2015/06/penjelasan-tentang-queue-contoh-program.html
ALGORITMA DAN PEMROGRAMAN DENGAN C++
(edisi II) Oleh : Andri Kristanto,S.Kom
http://webcache.googleusercontent.com/search?q=cache:_a1KkQw1NOIJ:elearning.amikom.ac.id/index.php/download/materi/555161-ST015-19/2012/06/20120620_STACK%2520DAN%2520QUEUE.pdf+&cd=1&hl=id&ct=clnk&gl=id
