02/05/2011

1

PI1043 Sturktur DataPriority Queue

Pengertian Priority Queue

• Suatu kontainer yang berisi beberapa item dimana setiap item memiliki prioritas.

• Kemungkinan setiap item mempunyai waktu tenggat yang berbeda-beda.

• Item dengan prioritas tertinggi merupakan item yang akan diproses atau dilayani selanjutnya.

3/11/'06PrioQ/rmb

2

• Seringkali, penunggu dalam antrian harus diatur menurut prioritas.

• Antrian disimpan menurut prioritas.• Aturan priority queue bukan lagi FIFO murni.• Implementasi priority queue dalam sorted

table.

3/11/'06PrioQ/rmb

3

Sorted Table

• Pengambilan elemen untuk dilayani selalu dari HEAD

• Penambahan elemen dilakukan sesuai prioritas. Elemen dalam antrian selalu dalam prioritas, dengan prioritas lebih tinggi untuk dilayani selalu lebih “dekat” ke HEAD

3/11/'06PrioQ/rmb

4

02/05/2011

2

Representasi Penyimpanan Antrian

• Queue lebih tepat direpresentasikan sebagai tabel.

• Terdapat tiga alternatif penyimpanan antrian

3/11/'06PrioQ/rmb

5

Alternatif I

• Tabel dengan hanya representasi TAIL adalah indeks elemen terakhir. HEAD selalu diset =1 jika queue tidak kosong. Jika queue kosong, maka HEAD=0. Berikut ini ilustrasi queue tidak kosong dengan 5 elemen:

3/11/'06 PrioQ/rmb

6

Alternatif I (cont’d)

• Ilustrasi queue kosong

• Algoritma paling sederhana untuk penambahan elemen▫ Jika masih ada tempat adalah dengan

“memajukan” TAIL. • Kasus khusus untuk queue kosong karena

HEAD harus diset nilainya menjadi 1.

3/11/'06 PrioQ/rmb

7

Alternatif I (cont’d)

• Algoritma paling sederhana dan “naif” untuk penghapusan elemen jika queue tidak kosong ambil nilai elemen HEAD, geser semua elemen ulai dari HEAD+1 s/d TAIL(jika ada), kemudian TAIL “mundur”.

• Kasus khusus untuk queue dengan keadaan awal berelemen 1, yaitu menyesuaikan HEAD & TAIL dengan DEFINISI. Algoritma ini mencerminkan pergeseran orang yang sedang mengantri di dunia nyata tapi tidak EFISIEN.

3/11/'06PrioQ/rmb

8

02/05/2011

3

Alternatif II

• Tabel dengan representasi HEAD & TAIL. HEAD bergerak ketika sebuah elemen dihapus jika queue tidak kosong. Jika queue kosong maka HEAD=0.

3/11/'06PrioQ/rmb

9

Alternatif II (cont’d)

• Ilustrasi queue tidak kosong, dengan 5 elemen, kemungkinan pertama HEAD sedang di posisi awal:

3/11/'06 PrioQ/rmb

10

Alternatif II (cont’d)

• Ilustrasi queue tidak kosong, dengan 5 elemen, kemungkinan pertama HEAD tidak berada di posisi awal. Hal ini terjadi akibat algoritma penghapusan yang dilakukan

3/11/'06 PrioQ/rmb

11

Alternatif II (cont’d)

• Ilustrasi queue kosong

• Algoritma untuk penambahan elemen = alternatif I: jika masih ada tempat adalah dengan memajukan TAIL. Kasus khusus untuk queue kosong karena HEAD harus diset nilainya menjadi 1. Algoritma = alternatif I

3/11/'06 PrioQ/rmb

12

02/05/2011

4

Alternatif II (cont’d)

• Algoritma untuk penghapusan elemen jika queue tidak kosong: ambil nilai elemen HEAD, kemudian HEAD maju. Kasus khusus untuk queue dengan keadaan awal berelemen 1, yaitu menyesuaikan HEAD & TAIL dengan DEFINISI.

• Algoritma ini tidak mencerminkan pergeseran orang yang sedang mengantri di dunia nyata, tapi efisien.

3/11/'06PrioQ/rmb

13

Alternatif II (cont’d)

• Namun suatu saat terjadi keadaan queue penuh tetapi “semu” sebagai berikut:

• Jika keadaan ini terjadi, haruslah dilakukan aksi menggeser elemen untuk menciptakan ruangan kosong. Pergeseran dilakukan jika dan hanya jika

3/11/'06 PrioQ/rmb

14

Alternatif III

• Tabel dengan representasi HEAD & TAIL “berputar” mengelilingi indeks tabel dari awal sampai akhir, kemudian kembali ke awal.

• Jika queue kosong maka HEAD=0. Representasi memungkinkan tidak perlu lagi ada pergeseran yang harus dilakukan seperti pada alternatif II pada saat penambahan elemen

3/11/'06PrioQ/rmb

15

Alternatif III (cont’d)

• Ilustrasi queue tidak kosong dengan 5 elemen dan HEAD berada di posisi awal:

3/11/'06 PrioQ/rmb

16

02/05/2011

5

Alternatif III (cont’d)

• Ilustrasi queue tidak kosong dengan 5 elemen dan HEAD tidak berada di posisi awal, tetapi “<” atau “sebelum” TAIL.

3/11/'06 PrioQ/rmb

17

Alternatif III (cont’d)

• Ilustrasi queue tidak kosong dengan 5 elemen, HEAD tidak berada di posisi awal, tetapi “>” atau “sesudah” TAIL.

3/11/'06 PrioQ/rmb

18

Alternatif III (cont’d)

• Algoritma untuk penambahan elemen ▫ Jika masih ada tempat adalah dengan memajukan

TAIL.▫ Jika TAIL sudah mencapai IdxMax maka suksesor dari

IdxMax adalah 1 sehingga TAIL yang baru=1.▫ Jika TAIL belum mencapai IdxMax maka algoritma

penambahan elemen = altern II.• Kasus khusus untuk queue kosong karena HEAD

harus diset nilainya menjadi 1.

3/11/'06PrioQ/rmb

19

Alternatif III (cont’d)• Algoritma penghapusan elemen▫ Jika queue tidak kosong ambil nilai elemen HEAD,

kemudian HEAD maju.• Penentuan suksesor dari indeks yang sudah

diubah/”maju” dibuat seperti algoritma penambahan elemen.▫ Jika HEAD mencapai IdxMax, maka suksesor dari

HEAD =1• Kasus khusus untuk queue dengan keadaan awal

berelemen 1, yaitu menyesuaikan HEAD & TAIL dengan DEFINISI.

3/11/'06PrioQ/rmb

20

02/05/2011

6

Alternatif III (cont’d)

Algoritma ini EFISIEN karena tidak perlu pergeseran dan seringkali strategi pemakaian

tabel semacam ini disebut sebagai “circular buffer”, dimana tabel penyimpan elemen

dianggap sebagai “buffer”

3/11/'06PrioQ/rmb

21 Representasi Penyimpanan Priority Queue

Tempat penyimpanan antrian dapat diadaptasi dari salah satu alternatif. Penomoran prioritas dapat ditentukan, misal:

• Prioritas bernilai 0 s/d PrioMax, dengan 0 untuk prioritas paling tinggi (ascending)

• Prioritas bernilai 0 s/d PrioMax, dengan 0 untuk prioritas paling rendah (descending)

3/11/'06PrioQ/rmb

22

• Contoh keadaan queue dengan prioritas 0 s/d 5, tersusun ascending

• Ilustrasi queue tidak kosong, dengan 5 elemen, dengan HEAD tidak berada di posisi awal, tetapi masih “lebih kecil” atau “sebelum” TAIL. Angka(1,0) berarti nilai informasi yang disimpan adalah 1 dengan prioritas 0.

3/11/'06PrioQ/rmb

23

ADT Priority Queue (PQ)

• Representasi fisik:▫ Tabel kontigu▫ Berkait pointer

• Primitif-primitif ADT PQ yang didefinisikan:▫ Menentukan apakah suatu PQ kosong atau tidak

(IsEmpty)▫ Menentukan apakah suatu PQ telah penuh atau belum

(IsFull)▫ Mengirimkan banyaknya elemen PQ (NbElmt)▫ Menginisialisasi sebuah PQ kosong (CreateEmpty)

3/11/'06PrioQ/rmb

24

02/05/2011

7

Primitif PQ (cont’d)▫ Mengembalikan semua memori PQ, PQ kosong

(dealokasi)▫ Menambahkan elemen X pada PQ dengan aturan

PQ (add)▫ Menghapus elemen X pada PQ dengan aturan

FIFO (del)

3/11/'06PrioQ/rmb

25

Representasi Kontigu/*file : prioque.h*/#ifndef prioque_h#define prioque_h#include “boolean.h”#include <stdlib.h>#define Nil 0#define maxprio 5/*definisi elemen & address*/typedef struct { int info;

int prio;}infotype;typedef int address; /*indeks tabel*/typedef struct { infotype *T; /*tabel elemen*/

address HEAD;/*alamat penghapusan*/address TAIL;/*alamat penambahan*/int MaxEl;/*max elemen PQ*/

3/11/'06PrioQ/rmb

26

Representasi Kontigu (cont’d)/*jika PQ adalah prioq, maka akses elemen: */#define head(pq) (pq).head#define tail(pq) (pq).tail#define infohead(pq) (pq).T[(pq).head].info#define infotail(pq) (pq).T[(pq).tail].info#define MaxEl(pq) (pq).MaxEl

/*prototype*/boolean IsEmpty(PrioQ);/* mengirimkan true jika prioq kosong */boolean IsFull(PrioQ);/* mengirimkan true jika tabel penampung prioq sudah penuh */

3/11/'06PrioQ/rmb

27

int NbElmt(PrioQ);/* mengirimkan banyaknya elemen prioq. Mengirimkan 0 jika kosong */

void CreateEmpty(PrioQ*,int);/* I.S. sembarang *//* F.S. sebuah pq kosong terbentuk dan salah satu kondisi sbb: */

/* jika alokasi berhasil, tabel memori dialokasi berukuran Max */

/* atau: jika alokasi gagal, pq kosong dg max elemen=0 */

/* proses: melakukan alokasi, membuat sebuah pq kosong */

3/11/'06PrioQ/rmb

28

02/05/2011

8

/* destruktor */void Dealokasi(PrioQ*);/* proses: mengembalikan memori pq *//* I.S. pq pernah dialokasi *//* F.S. pq menjadi tidak terdefinisi lagi. MaxEl(pq) diset 0 */

/*** primitif Add/Delete ***/void Add(PrioQ*,infotype);/* proses: menambahkan X pada pq shg elemen tetap terurut menaik menurut Prio(P). Tabel penyimpan elemen dipakai secara sirkuler */

/* elemen berikut setelah elemen terakhir adalah elemen dg indeks 1 */

3/11/'06PrioQ/rmb

29

/*I.S. pq mungkin kosong, tabel penampung elemen pq tidak penuh*/

/*F.S. elemen pq bertambah 1 sesuai aturan prioq dg prio menurun*/

void Del(PrioQ*,infotype*);/* proses: menghapus X pada pq dari head(pq) *//* I.S. pq tidak mungkin kosong *//* F.S. X=nilai elemen head pada I.S. jika head(pq)=MaxEl+1 */

/* head(pq) diset=1; Q mungkin menjadi kosong*/

#endif

3/11/'06PrioQ/rmb

30

Representasi List Berkait/* File: Lpqueue.h *//* deklarasi PrioQ, diimplementasi dg list berkait */

#ifndef Lpqueue_h#define Lpqueue_h#include “boolean.h”#include <stdlib.h>#define Nil NULL

/* definisi elemen & address */typedef struct { int info;

int prio;}infotype;

3/11/'06PrioQ/rmb

31

typedef struct t_ElmtQ *address;typedef struct t_ElmtQ {

infotype info;address next;

}ElmtPQ;typedef struct {

address head;address tail;

}Pqueue;

/*jika Q adalah Pqueue maka akses elemen: */#define head(Q) (Q).head#define tail(Q) (Q).tail

3/11/'06PrioQ/rmb

32

02/05/2011

9

/* Jika P adalah address */#define info(P) ((P)->info).info#define prio(P) ((P)->info).prio#define next(P) (P)->next

/*prototype*/boolean IsEmpty(PrioQ);/* mengirimkan true jika prioq kosong */boolean IsFull(PrioQ);/* mengirimkan true jika tabel penampung prioq sudah penuh */

3/11/'06PrioQ/rmb

33

int NbElmt(PrioQ);/* mengirimkan banyaknya elemen prioq. Mengirimkan 0 jika kosong */

void CreateEmpty(PrioQ*);/* I.S. sembarang *//* F.S. sebuah pq kosong terbentuk *//* Proses. Membuat pq kosong */

/* destruktor */void Dealokasi(PrioQ*);/* proses: mengembalikan memori pq *//* I.S. pq pernah dialokasi *//* F.S. pq menjadi tidak terdefinisi lagi.*/

3/11/'06PrioQ/rmb

34

/*** primitif Add/Delete ***/void Add(PrioQ*,infotype);/* proses: menambahkan X pada pq shg elemen tetap terurut menaik menurut Prio(P). Tabel penyimpan elemen dipakai secara sirkuler */

/* elemen berikut setelah elemen terakhir adalah elemen dg indeks 1 */

/*I.S. pq mungkin kosong, tabel penampung elemen pq tidak penuh*/

/*F.S. elemen pq bertambah 1 sesuai aturan prioq dg prio menurun*/

3/11/'06PrioQ/rmb

35

void Del(PrioQ*,infotype*);/* proses: menghapus X pada pq dari head(pq) *//* I.S. pq tidak mungkin kosong *//* F.S. X=nilai elemen head pada I.S. jika head(pq)=MaxEl+1 */

/* head(pq) diset=1; Q mungkin menjadi kosong*/

#endif

3/11/'06PrioQ/rmb

36

02/05/2011

10

References

• Liem, Inggriani. “Diktat Struktur Data”. ITB. 1999

• Thomas A. Standish,“Data Structures, Algorithms & Software Principles in C” Addison-Wesley, 1995

3/11/'06PrioQ/rmb

37