ALGORITMA DAN STRUKTUR DATA : BAB 7

7.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;
};

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;
}
}

Image

Beberapa operasi enqueue pada queue dengan linked list

Image

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 ;

> 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)

Image

Representasi Queue dengan struktur data SET

Image

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);

}

}

 

Latihan/ Tugas:

Apa yang dicetak dilayar monitor oleh main program dibawah ini

void main()

{

ElemenType x;

x.data=23;

x.priority=23;

enqueue(x);

 

x.data=44;

x.proirity=1;

enqueue(x);

 

x.data=45;

x.priority=7;

enqueue(x);

 

x.data=45;

x.priority=0;

enqueue(x);

 

dequeue(&x);

printf(“Data=%d Priority =%d\n”,x.data,x.priority);

dequeue(&x);

printf(“Data=%d Priority =%d\n”,x.data,x.priority);

dequeue(&x);

printf(“Data=%d Priority =%d\n”,x.data,x.priority);

dequeue(&x);

printf(“Data=%d Priority =%d\n”,x.data,x.priority);

}

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