Penjelasan tentang Queue & Contoh Program dalam
C++
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
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/ 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
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:
int IsEmpty()
{
if ((antrian.HEAD> antrian.TAIL) || (antrian.HEAD
== 0) &&
(antrian.TAIL == 0))
return 1;
else
return 0;
}
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:
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();
}
Sekian Pembahasan tentang Queue dari saya, semoga bermanfaat ^,^
Tidak ada komentar:
Posting Komentar