Queue
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:
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 strukutr 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;
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 = 6:
6 5 4 3 2 1 0
HEAD
TAIL
Operasi Queue
o
Create : suatu operator yang digunakan untuk membentuk dan
menunjukkan suatu antrian
hampa.
o
IsEmpty : menentukan apakah antrian tersebut dalam keadaan kosong.
o
IsFull : menentukan apakah antrian tersebut sudah penuh.
o
Enqueue : untuk menginputkan suatu nilai ke elemen array.
o
Dequeue : untuk mengeluarkan nilai pada suatu array.
o
Clear : untuk menghapus semua elemen yang terdapat pada array.
o
Print : digunakan untuk mencetak semua elemen pada array
1.
Deklarasi Awal Queue
(Create)
Variabel yang akan digunakan adalah data (array sebagai tempat
queue), head, tail. Sama seperti Stack, Nilai dari head dan tail dimulai
dari -1 yang menandakan queue kosong. Sebagai contoh kita akan membuat
queue dengan data maksimal sebanyak 7 data.
Deklarasi awal variabel yang akan digunakan dalam queue
#define
max 7
Int data[max];
Int head = -1,
tail = -1;
1.
IsEmpty
Sama seperti di Stack, IsEmpty berguna untuk mengecek apakah
queue kosong atau tidak. Indikator bahwa queue kosong adalah nilai dari
head dan tail bernilai -1. Sehingga kita tinggal buat fungsi nya sebagai
berikut :
bool IsEmpty()
{
if(head
== -1 && tail == -1)
{
return true;
}
else
{
return false;
}
}
2.
IsFull
Operasi IsFull digunakan untuk mengecek apakah queue sudah
penuh atau belum. Indikator kalau queue penuh adalah nilai tail = max –
1. Mengapa? karena nilai maksimal pada array yang mempunyai index 7 pada
saat diakses akan mempunyai nilai maksimal 6. Sehingga fungsi yang
terbentuk seperti ini :
bool IsFull()
{
if(tail
== max-1)
{
return true;
}
else
{
return false;
}
}
3.
Enqueue
Enqueue digunakan untuk memasukkan data kedalam queue.
Sama seperti push dalam stack. Sebelum memasukkan data kedalam antrian,
kita harus mengecek terlebih dahulu apakah queue / antrian sudah penuh atau
belum. Kalau belum maka kita harus mengecek apakah head sudah berada pada
nilai 0 atau belum. Ini sangat penting karena nilai head tidak akan lebih
dari 0. PERLU DIPERHATIKAN ! Yang akan bergerak terus adalah tail,
sedangkan head hanya penunjuk urutan paling depan, sehingga nilainya tidak
pernah lebih dari 0. Kecuali antrian kosong, maka posisi head dan tail
akan kembali menjadi -1.
Saat memasukkan data
pertama kali, maka nilai head dan tail berubah menjadi 0. Tetapi saat data yang
dimasukkan sudah lebih dari 1 kali, maka yang akan terus berubah adalah tail,
sedangkan nilai head tetap.
void Enqueue()
{
if(IsFull())
{
cout<<"Antrian
sudah penuh.";
}
else
{
if (IsEmpty())
{
head=tail=0;
cout<<"Masukkan
data : ";cin>>data[tail];
}
else
{
tail++;
cout<<"Masukkan data :
";cin>>data[tail];
}
}
}
5. Dequeue
Kebalikan dari fungsi enqueue, dequeue digunakan untuk
mengambil data yang sudah masuk di urutan pertama. Sehingga kita tinggal
membaca data yang ada di posisi head. Nah inilah fungsi dari head.
Jangan lupa kita cek dulu apakah queue kosong atau tidak. Tapi jika ada
isinya, setelah data diambil, data dibelakangnya digeser ke depan.
void Dequeue()
{
if(IsEmpty())
{
cout<<"Antrian kosong !
";
}
else
{
cout<<"Data
yang diambil : "<<data[head];
for(a=head;a<=tail-1;a++)
data[a]=data[a+1];
tail--;
}
}
Operasi clear digunakan untuk menghapus data yang ada di dalam
queue. Caranya cukup merubah nilai pada head dan tail menjadi -1.
Tidak perlu diperhatikan data yang ada di dalam array. Nantinya data data
tersebut juga akan ditimpa.
void Clear()
{
head=tail=-1;
cout<<"Antrian
sudah dikosongkan ! ";
getch();
}
7.View
Operasi ini digunakan untuk melihat data yang ada didalam
queue. Caranya adalah dengan membaca data pada index yang terdapat
diantara head sampai tail
void View()
{
if(IsEmpty())
{
cout<<"Antrian
kosong ! ";
getch();
}
else
{
for(a=head;a<=tail;a++)
cout<<"Data pada antrian ke
"<<a<<" = "<<data[a]<<endl;
getch();
}
}
Contoh Program Queue
#include <conio.h>
#include <iostream.h>
int nilai[5];
int head, tail, max, menu;
void create()
{
head=0;
tail=-1;
max=4;
}
bool isfull()
{
if(tail==max)
{
return true;
}
else
{
return false;
}
}
bool isempty()
{
if(tail<head)
{
return true;
}
else
{
return false;
}
}
void main()
{
create();
home:
clrscr();
cout<<"Pilih Salah Satu Menu di Bawah ini : "<<endl;
cout<<"1. Enqueue"<<endl;
cout<<"2. Dequeue"<<endl;
cout<<"3. Print"<<endl;
cout<<"4. Clear"<<endl;
cout<<"Masukkan
Pilihan anda (1-4) : ";
cin>>menu;
switch(menu)
{
case 1:
if(isfull()==true)
{
cout<<"STOP.. Atrian
Penuh..";
}
else
{
tail++;
cout<<"Masukkan data ke Antrian : ";
cin>>nilai[tail];
}
getch();
goto home;
break;
case 2:
if(isempty()==true)
{
cout<<"Atrian Kosong";
}
else
{
cout<<"Data Atrian yang
keluar :
"<<nilai[head];
tail--;
for(int i=0;i<=tail;i++)
{
nilai[i]=nilai[i+1];
}
}
getch();
goto
home;
break;
case 3:
if(isempty()==true)
{
cout<<"Data Tidak
Ada";
}
else
{
cout<<"Data pada Antrian :"<<endl;
for(int i=0;i<=tail;i++)
{
cout<<nilai[i]<<"
";
}
}
getch();
goto home;
break;
case 4:
tail=-1;
cout<<"Antrian Sekarang kosong";
getch();
goto
home;
break;
}
getch();
}
Tidak ada komentar:
Posting Komentar