ALGORITMA DAN STRUKTUR DATA : BAB 8

QUENUE

8.1 Implementasi Queue dengan struktur data Linked– List

Implementasi Queue dengan linked-list dapat menghindari masalah pengalokasian memory seperti
yang terjadi pada implementasi dengan array biasa ( dalam pembahasan di bab sebelumnya diajukan
circular array yang mengatasi permasalahan ini ). Hal ini dikarenakan alokasi memory yang bersifat
dinamis pada implementasi dengan menggunakan linked-list. Seperti halnya implementasi dengan
menggunakan array yang memerlukan dua buah penunjuk, maka implementasinya dengan link-list
juga memerlukan 2 penunjuk, yang bisa kita namakan head yang menunjuk posisi awal queue dan
tail tail menunjukkan posisi akhir queue.

Implementasi struktur data Queue dengan linked list dalam bahasa C

#include <stdio.h>
#include <malloc.h>
typedef int Elementype;
struct Node {
ElemenType data;
struct Node *next;
};
struct QUEUE{
struct Node *Head;
struct Node *Tail;
};
Struktur Data Dengan Bahasa C – 65 –
Bab 8 Queue II
struct QUEUE Q;
void create()
{
Q.Head = NULL;
Q.Tail = NULL;
}
Int empty()
{
if(Q.Head == NULL) return (1);
else return (0);
}
void enqueue(ElemenType e)
{
struct Node *Temp;
Temp = (struct Node*) malloc(sizeof(struct Node));
Temp -> data = e;
Temp -> next = NULL;
if(empty()){
Q.Head = Temp;
Q.Tail = Temp;
}
else {
Q.Tail-> next = Temp;
Q.Tail = Temp;
}
}

Gambar

Gambar 8.1: Beberapa operasi enqueue pada queue dengan linked list

void dequeue(ElemenType *e)
{
struct Node *Temp;
if(empty()) printf(“Queue masih kosong\n”);
else{
Temp = Q.Head;
Q.Head = Q.Head->next;
*e=Temp->data;
free(Temp);
}
}

Gambar

 

Gambar 8.2: Operasi dequeue pada queue dengan linked list

Priority Queue
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 ;

  1. Ascending Priority Queue; adalah Queue yang diurutkan dengan prioritas menarik.
  2. 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 <stdio.h>
#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 < Q[Pos].priority && (Jum_El > 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);
}
}

 

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s