MADE YOGA PRATAMA: QUEUE

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.

Contoh yang paling populer untuk membayangkan sebuah queue adalah antrian pada kasir sebuah bank. Ketika seorang pelanggan datang, akan menuju ke belakang dari antrian. Setelah pelanggan dilayani, antrian yang berada di depan akan maju. Pada saat menempatkan elemen pada ujung (tail) dari queue disebut dengan enqueue, pada saat memindahkan elemen dari kepala (head) sebuah queue disebut dengan dequeue.

Pada Queue atau antrian Terdapat satu buah pintu masuk di suatu ujung dan satu buah 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

6. tambah(menambah item pada belakang antrian)

7. hapus (menghapus elemen depan dari antrian)

8. kosong( mendeteksi apakah pada antrian mengandung elemen atau tidak)

Operasi-operasi Queue :

1. Create() Untuk menciptakan dan menginisialisasi Queue Dengan cara membuat Head dan Tail = -1

2. IsEmpty() Untuk memeriksa apakah Antrian sudah penuh atau belum Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail.

3. IsFull Untuk mengecek apakah Antrian sudah penuh atau belum Dengan cara mengecek nilai Tail, jika

Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh

4. Enqueue Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu

5. Dequeue() Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1 Penggeseran dilakukan dengan menggunakan looping.

6. Clear() Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1 Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca

7. Tampil() Untuk menampilkan nilai-nilai elemen Antrian Menggunakan looping dari head s/d tail

Queue juga mempunya dua tipe, yaitu:

1. Queue dalam bentuk Linier

Linear array adalah suatu array yang dibuat seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar.

2. Queue dalam bentuk Circular

Circular array adalah suatu array yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal (head) dan titik akhir (tail) saling bersebelahan jika array tersebut masih kosong. Posisi head dan tail itu bebas asalkan saling bersebelahan.

Implementasi Antrian dengan Array

Seperti halnya pada tumpukan, maka dalam antrian kita juga mengenal ada dua operasi dasar, yaitu menambah elemen baru yang akan kita tempatkan di bagian belakang antrian dan menghapus elemen yang terletak di bagian depan antrian. Disamping itu seringkali kita juga perlu melihat apakah antrian mempunyai isi atau dalam keadaan kosong.

Operasi penambahan elemen baru selalu bisa kita lakukan karena tidak ada pembatasan banyaknya elemen dari suatu antrian. Tetapi untuk menghapus elemen, maka kita harus melihat apakah antrian dalam keadaan kosong atau tidak. Tentu saja kita tidak mungkin menghapus elemen dari suatu antrian yang sudah kosong. Untuk menyajikan antrian menggunakan array, maka kita membutuhkan deklarasi antrian, misalnya sebagai berikut:

#define MAXQUEUE 100;

typedef int ItemType;

typedef struct{

int Count;

int Front;

int Rear;

ItemType Item[MAXQUEUE];

}Queue;

Front, menunjukkan item yang paling depan, yaitu elemen yang akan dihapus jika dilakukan operasi penghapusan. Setelah kita melakukan penghapusan, kita melakukan increment pada indeks Front, sehingga indeks menunjuk pada posisi berikutnya. Jika indeks ini jatuh pada angka tertinggi, yaitu angka paling maksimum dari array (N), maka kita melakukan setting ulang ke 0. Array Item[0:N-1] berisi N item yang merupakan isi dari antrian. Berada pada posisi 0:N-1dimana pada posisi ini dapat diindikasikan dua pengenal, yaitu Front dan Rear.

Count menunjukkan jumlah item dalam antrian. Rear menunjukkan posisi dimana setelahnya dapat dimasukkan item berikutnya. Representasi antrian lengkap dengan operasi-operasi yang merupakankarakteristik antrian adalah sebagai berikut:

Implementasi Antrian dengan Linked list

Antrian yang direpresentasikan dengan linked list mempunyai beberapa variasi. Pada kesempatan kali ini hanya direpresentasikan satu macam saja. Linked list yang digunakan di sini menggunakan struktur yang berisi pointer yang menunjuk pada simpul Front dan Rear dari linked list. Masing-masing simpul berisi data dari antrian dan juga link yang menunjuk pada simpul selanjutnya dari linked list, yang dinamakan Link.

Antrian Berprioritas

Dalam antrian yang telah dibahas di atas, semua elemen yang masuk dalam antrian dianggap mempunyai prioritas yang sama, sehingga elemen yang masuk lebih dahulu akan diproses lebih dahulu. Dalam praktek, elemen-elemen yang akan masuk dalam suatu antrian ada yang dikatakan mempunyai prioritas yang lebih tinggi disbanding yang lain. Antrian yang demikian ini disebut dengan antrian berprioritas (priority queue).

Dalam antrian berprioritas, setiap elemenn yang akan msuk dalam antrian sudah ditentukan lebih dahulu prioritasnya. Dalam hal ini berlaku dua ketentuan, yaitu:

1. Elemen-elemen yang mempunyai prioritas lebih tinggi akan diproses lebih dahulu.

2. Dua elemen yang mempunyai prioritas sama akan dikerjakan sesuai dengan urutan

pada saat kedua elemen ini masuk dalam antrian.

Dengan memperhatikan kedua ketentuan di atas, akan berlaku ketentuan bahwa elemen yang mempunyai prioritas lebih tinggi akan dikerjakan lebih dahulu disbanding elemen yang mempunyai prioritas lebih rendah, meskipun elemen yang berprioritas tinggi masuknya sesudah elemen yang berprioritas rendah. Salah satu contoh antrian berprioritas ini adalah pada sistem berbagi waktu (time-sharing system) dimana program yang mempunyai prioritas tinggi akan dikerjakan lebih dahulu dan program-program yang berprioritas sama akan membentuk antrian biasa. Ada beberapa cara untuk mengimplementasikan antrian berprioritas. Salah satu caranya adalah dengan menggunakan linked list. Jika kita menggunakan linked list, khususnya single linked list atau double linked list, maka ada ketentuan lain yang perlu diperhatikan, yaitu:

1. Setiap node dari linked list terdiri tiga bagian, yaitu bagian informasi, angka prioritas dan bagian-bagian penyambung ke simpul lain.

2. Simpul X mendahului (terletak di sebelah kiri) simpul Y, jika prioritas X lebih tinggi dibanding prioritas Y atau jika prioritas X dan Y sama, maka simpul X datang lebih dahulu dibanding dengan Y.

Biasanya dibuat suatu perjanjian bahwa angka prioritas yang lebih kecil menunjukkan derajad prioritas yang lebih tinggi. Sebagai contoh, jika angka prioritas pada simpul X adalah 1 dan pada simpul Y adalah 2, maka dikatakan bahwa simpul X berprioritas lebih tinggi dibanding dengan simpul Y.

Contoh program Queue

#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#include <iomanip.h>
#define max 6

typedef struct
{
int head;
int tail;
}antrian;

antrian ue;

typedef struct
{
char *nm[max], *almt[max], *tgl[max];
} variabel;

variabel qu;

void creat()
{
ue.head=ue.tail=-1;
}

empty()
{
if(ue.tail==-1)
return 1;
else
return 0;
}

full()
{
if(ue.tail==max-1)
return 1;
else
return 0;
}

void en(char *a, char *b, char *c)
{
if(empty()==1)
{
ue.head=ue.tail=0;
qu.nm[ue.tail]=a;
qu.almt[ue.tail]=b;
qu.tgl[ue.tail]=c;
}

else if(full()==0)
{
ue.tail++;
qu.nm[ue.tail]=a;
qu.almt[ue.tail]=b;
qu.tgl[ue.tail]=c;
}

else if(full()==1)
{
cout<<"QUEUE PENUH";
}
}

de()
{
if(empty()==0)
{
int i;
char *aa=qu.nm[ue.tail];
char *bb=qu.almt[ue.tail];
char *cc=qu.tgl[ue.tail];

   for(i=ue.head; 1<=ue.tail-1; i++)
{
   qu.nm[i]=qu.nm[i+1];
qu.almt[i]=qu.almt[i+1];
   qu.tgl[i]=qu.tgl[i+1];
    }

ue.tail--;
cout<<"DATA YANG DIHAPUS ADALAH : \n";

cout<<"NAMA : "<<aa<<endl;
cout<<"ALAMAT : "<<bb<<endl;
cout<<"TANGGAL: "<<cc<<endl;
}

else if(empty()==1)
{ cout<<"DATA EROR......QUEUE KOSONG"; }

return 1;
}

void clear()
{
ue.head=ue.tail=-1;
cout<<"QUEUE CLEAR";
}

void view()
{
if(empty()==0)
{
cout<<"NO NAMA ALAMAT TANGGAL\n";

for(int i=ue.head; i<=ue.tail; i++)
{
   cout<<setiosflags(ios::left)<<setw(3)<<i;
cout<<setiosflags(ios::left)<<setw(11)<<qu.nm[i];
cout<<setiosflags(ios::left)<<setw(18)<<qu.almt[i];
cout<<setiosflags(ios::left)<<setw(9)<<qu.tgl[i]<<endl;
}
}
else
{ cout<<"NO NAMA ALAMAT TANGGAL\n"; }
}

main()
{

int menu;
char nm[20], almt[40], tgl[20];

creat();

do{

clrscr();

cout<<"===========================\n";
cout<<" MENU PROGRAM QUEUE\n";
cout<<"===========================\n";
cout<<"1.ENQUEUE\n";
cout<<"2.DEQUEUE\n";
cout<<"3.CLEAR\n";
cout<<"4.VIEW\n";
cout<<"5.EXIT\n";
cout<<"===========================\n";
cout<<"PILIH MENU : ";       cin>>menu;

if(menu==1)
{     cout<<"MASUKAN NAMA : ";   gets(nm);
   cout<<"MASUKAN ALAMAT : ";   gets(almt);
cout<<"MASUKAN TANGGAL: "; gets(tgl);
   en(nm, almt, tgl);
}

else if(menu==2)
{
   de();
}

else if(menu==3)
{
    clear();
}

else if(menu==4)
{
    view();
}

else if(menu==5)
{
    cout<<"exiiitttt......";
}
getch();

}while(menu!=5);

}