Priority Queue adalah queue dengan basis HPIFO ( Highest Priority In First Out ). Berbeda
dengan queue yang sangat tergantung kepada waktu kedatangan ( elemen yang datang
pertama akan selalu diambil / dihapus adalah elemen yang memilki priority tertinggi ( bila
yangmenjadi prioritas adalah waktu kedatangan maka Priority Queue berfungsi seperti queue
biasa ).
Priority Queue dibedakan atas 2 tipe yaitu ;
Ascending Priority Queue; adalah Queue yang diurutkan dengan prioritas menarik.
Descending Priority Queue; adalah queue yang diurutkan dengan prioritas menurun.
Untuk merepresentasikan Priority Queue dapat dilakukan dengan 3 cara : yaitu set, list dan
array. Dengan representasi set, data dimasukkan ke dalam ke dalam queue (enQueue),
berdasarkan waktu kedatangan, sedangkan pengambilannya ( dequeue ) tetap berdasarkan
prioritas. Keuntungan representasi set adalah operasi enQueue sngat cepat dan sederhana ,
tetapi operasi deQueue menjadi sangat kompleks karena diperlukan pencarian elemen dengan
prioritas tertinggi. Sedangkan dengan representasi list, data dienQueue dan dideQueue
berdasarkan prioritas. Gambar berikut menggambarkan posisi dari priority queue yang
direpresentasikan dengan set dan list bila dilakukan operasi sebagai berikut.
Create; enQueue (12); enQueue (117); enQueue (25); deQueue (e) .
Gambar
Gambar 8.4: Representasi queue dengan struktur data LIST
Procedure berikut ini merupakan implementasi dengan menggunakan struktur data array untuk priority
queue.
#include
#define PJG_MAX 20
typedef int DataType;
typedef struct Elemen ElemenType;
int Jum_El, Head;
struct Elemen {
DataType data;
int priority;
};
ElemenType Q[PJG_MAX];
void create()
{
int Jum_El = 0;
int Head = 0;
}
int empty()
{
if(Jum_El == 0) return (1);
else return (0);
}
int full()
{
if(Jum_El == PJG_MAX – 1) return (1);
else return (0);
}
void move_queue_down(int awal, int akhir)
{
int i;
for(i=akhir; i>= awal; i–) Q[i] = Q[i-1];
}
void move_queue_up(int awal, int akhir);
{
int I;
for(i=awal; i<= akhir; i++) Q[i] = Q [i+1];
}
void enqueue(ElemenType e)
{
int Pos;
Pos = Head;
if(full()) printf(Queue sudah penuh\n):
else {
while ((e.priority Pos)) Pos = Pos +1;
if (Jum_el > Pos) move_queue_down(Pos+1, Jum_El);
Q[Pos] = e;
Jum_El = Jum_El +1;
}
}
void dequeue(ElemenType *e);
{
if(empty()) printf(Queue masih kosong\n);
else{
*e=Q[Head];
Jum_El = Jum_El – 1;
if(!empty())move_queue_up(Head, Jum_El-1);
}
}