Konsep 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 terlebih dahulu, dan akan selesai lebih dulu dari orang-orang yang datang
setelahnya. Gambar di bawah ini mengilustrasikan kerja sebuah queue:
Queue pada Struktur Data atau antrian adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung disebut dengan sisibelakang(rear), dan penghapusan(pengambilan elemen) dilakukan lewat ujung lain (disebut dengan sisi depan atau front) Queue atau antrian prinsip yang digunakan adalah“Masuk Pertama Keluar Pertama” atau FIFO (First In First Out). Queue atau antrian banyak kita jumpai dalam kehidupan sehari-hari, ex: antrian Mobil diloket Tol, Antrian mahasiswa Mendaftar, dll. Contoh lain dalam bidang komputer adalah pemakaian sistem komputer berbagi waktu(time-sharing computer system) dimana ada sejumlah pemakai yang akan menggunakan sistem tersebut secara serempak.
Pada Queue atau antrian Terdapat satu buah pintu masuk di suatu ujung dan satubuah pintu keluar di ujung satunya dimana membutuhkan variabel Head dan Tail ( depan/front, belakang/rear).
Karakteristik Queue atau antrian :
1. elemen antrian
2. front (elemen terdepan antrian)
3. tail (elemen terakhir)
4. jumlah elemen pada antrian
5. status antrian Operasi pada Queue atau antrian
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 atau nilai ke dalam antrian adalah enqueue,
sedangkan prosedur untuk mengeluarkan data atau nilai dari antrian adalah dequeue.
a. Prosedur createEmpty
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 atau 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:
Pada deklarasi prosedur enqueue di atas, prosedur memiliki sebuah parameter formal yang
bernama X yang bertipe integer. Ini berguna untuk menerima kiriman nilai dari program
utama ( void main () ) yakni berupa sebuah bilangan integer yang akan dimasukkan ke
dalam queue. Gambar di bawah ini mengilustrasikan proses enqueue ke dalam sebuah
queue yang masih kosong.
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 atau 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. Gambar di bawah ini mengilustrasikan cara kerja prosedur dequeue:
Ketika nilai terakhir (yakni nilai 3) dikeluarkan, maka posisi HEAD dan TAIL akan menjadi
seperti ini:
Maka, ketika kondisi HEAD > TAIL terjadi seperti ilustrasi di atas, maka HEAD dan TAIL
dikembalikan ke indeks array ke-0.
d. Fungsi IsEmpty
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++:
e. Fungsi IsFull
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 ++ :
Contoh Code QUEUE :
#include<iostream.h>
#include<conio.h>
#include<studio.h
#define max 10
typedefstruct
{ int data[max];
int head;
int tail;
}Queue;
Queue antrian;
void create()
{
void create() antrian.head=antrian.tail=-1;
}
intIsEmpty()
{
if(antrian.tail==-1)
return 1;
else
return 0;
}
if(antrian.tail==max-1)
return 1;
else
return 0;
}
void Enqueue(int data)
{
if(IsEmpty()==1)
{
antrian.head=antrian.tail=0;
antrian.data[antrian.tail]=data;
cout<<"Data "<<antrian.data[antrian.tail]<<"Masuk !!!";
}
else if(IsFull()==0)
{
antrian.tail++;
antrian.data[antrian.tail]=data; cout<<"Data "<<antrian.data[antrian.tail]<<"Masuk !!!";
}
else if(IsFull==1)
{
cout<<"Ruangan Penuh<<”Masuk;
cout<<data<<"GaBisaMasuk!
}
}void Dequeue()
{inti;
{inti;
int e = antrian.data[antrian.head];
if(antrian.taill==-1)
{
cout<<"Ga ada antrian... Data Kosong"<<endI;
}
else
{
for(i=antrian.head.i <antrian.tail-1;i++)
{
antrian.data[i]=antrian.data [i+1];
}
antrian.tail--;
cout<<"Data yang keluarterlebih dulu= "<<e<<endI;
}
}
void clear()
{
{antrian.head=antrian.tail =-1;
cout<<"Duh Lega,Ruangajagasumpek... "<<endI;
cout<<"Data Clear";
}
void tampil()
{
if(IsEmpty ()==0)
{
cout<<"Data DalamAntrian"<<endl;
cout<<"=====================================";
cout<<endl;
for(inti=antrian.head;i<=antrian.tail;i++)
{
cout<<"| " <<antrian.data[i]<<" |";
}
}
else
{
cout<< Gaadaantrian ...Data kosong
";
}
}
void main()
{
intpil;
int data;
create();
do
{
cout<<"ImplementasiAntriandenganStruct"<<endl;
cout<<"==========================================";
cout<<endl;
cout<<"1. Enqueue"<<endl;
cout<<"2.Dqueue "<<endl;
cout<<"3. Print "<<endl;
cout<<"4. Clear "<<endl;
cout<<"5. Exit "<<endl;
cout<<"Masukkanpilihananda : ";
cin>>pil;
switch(pil)
{
case 1:
{
cout<<endl;
cout<<"Data = ";
cin>>data;
Enqueue(data);
break;
}
case 2:
{
cout<<endl;
Dequeue();
break;
}
case 3:
{
cout<<endl;
tampil();
break;
}
case 4:
{
cout<<endl;
clear();
break;
}
}
getch();
}
while(pil!=5);
}
{
cout<<endl;
Dequeue();
break;
}
case 3:
{
cout<<endl;
tampil();
break;
}
case 4:
{
cout<<endl;
clear();
break;
}
}
getch();
}
while(pil!=5);
CONTOH QUEUE DALAM KEHIDUPAN SEHARI – HARI
Dalam kehidupan sehari-hari kita bisa dapati melalui penerapan pembelian tiket kereta api, tiket pesawat, tiket kapal laut, pembayaran tiket tol, pembayaran listrik, pembayaran air, dan lain sebagainya. Walaupun berbeda implementasi, Konsep struktur data queue adalah First In First Out(FIFO). Queue setidaknya harus memiliki operasi-operasi sebagai berikut:
1. EnQueue : Masukkan data ke dalam antrian
2. DeQueue : Mengeluarkan data terdepan dari antrian
3. Clear : Menghapus seluruh antrian.
4. IsEmpty : Memeriksa apakah antrian kosong
5. IsFull : Memeriksa apakah antrian penuh
Dalam pembelian tiket kereta api:
Enqueue : Seseorang membeli tiket melalui tempat pembayaran tiket yang disediakan.
Dequeue : Setelah membeli tiket, langsung menuju tempat penungguan kereta, dengan sebelumnya petugas memeriksa cek tiket tersebut.
Clear : Pembeli tiket tersebut telah terhapus dari antrian karena sudah melewati pembayaran administrasi tersebut.
IsEmpty : Petugas tiket Kereta melihat tidak ada lagi yang ingin membeli tiket kereta.
IsFull : Petugas Tiket Kereta melihat masih ada pembeli tiket kereta.
Contohnya yaitu antrian pada kasir pada sebuah bank. Ketika seorang pelanggan datang, akan akan maju. Jika kita ada di antrian kedua, maka kita akan menunggu antrian pertama melakukan prosesnya. Nah, ketika selesai proses dari antrian pertama dia akan pergi, dan menuju ke belakang dari antrian. Setiap pelanggan dilayani, antrian yang berada di depan giliran kita untuk maju untuk melakukan proses. Begitu juga arti dari antrian dalam bahasan kali ini, jika pengantri pertama datang maka dia juga yang akan keluar pertama kali atau bahasa kerennya tu FIFO ( First In First Out ).
Kondisi antrian yang menjadi perhatian :
`1, PENUH
Bila elemen pada antrian mencapai kapasitas maksimum antrian, maka tidak mungkin dilakukan penambahan ke antrian. Penambahan elemen menyebabkan kondisi kesalahan overfl
2. KOSONG
Bila tidak ada elemen pada antrian, maka tidak mungkin dilakukan pengambilan elemen dari antrian. Pengambilan elemen menyebabkan kondisi kesalahan overflow.
KARAKTER QUEUE ATAU ANTRIAN
1. Adanya elemen antrian yaitu item – item data yang terdapat pada element antrian.
2. Adanya front ( elemen antrian )
3. Adanya tail ( elemen terhkir )
4. Status antrian
5. Adanya jumlah elemen pada antrian
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 strukutur 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 paper 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:
