QUEUE n DEFINISI Queue adalah suatu linear list di mana operasi DELETE terjadi pada sisi depan (FRONT) dan operasi INSERT terjadi pada sisi belakang (REAR). Jika diberikan suatu Queue Q dengan elemen-elemennya yang terdiri atas Q1, Q2, ....., QT maka queue Q dituliskan
Q = [ Q1, Q2, .........., QT ] FRONT(Q) = Q1
REAR(Q) = QT
Selanjutnya untuk menyatakan jumlah elemen dalam suatu queue Q digunakan notasi NOEL(Q).
CAT : Satu pengoperasian berlaku hanya untuk satu elemen.
n GAMBAR QUEUE & PENGOPERASIANNYA
Untuk menggambarkan suatu queue dapat dilakukan beberapa cara , yaitu :
Misal : diberikan Queue Q = [A, B, C, D, E, F], maka Queue Q dapat digambarkan sebagai berikut : A â
B
C
D
E
FRONT
F â
F â REAR
E
D
C
REAR
B
A â FRONT
atau dapat pula digambarkan dengan posisi tegak.
n PRINSIP KERJA QUEUE
Prinsip kerja Queue adalah FIFO (First In First Out), di mana data yang masuk terlebih dahulu akan keluar pertama. 27
n OPERASI-OPERASI PADA QUEUE (Q) Terdapat empat operasi dasar yang didefinisikan pada queue, yaitu :
1. CREATE Bentuk Umum : CREATE(Queue) Suatu operasi CREATE(Q) akan menghasilkan suatu queue kosong dengan nama Q, dan didefinisikan bahwa : NOEL(CREATE(Q)) = 0 FRONT(CREATE(Q)) = tidak terdefinisi REAR(CREATE(Q)) = tidak terdefinisi
2. ISEMPTY Bentuk Umumnya adalah : ISEMPTY(queue) Jika Q adalah Queue, maka ISEMPTY(Q) adalah suatu operasi yang digunakan untuk memeriksa apakah Queue Q adalah queue kosong. Jika hasil dari operasi ini akan berjenis data boolean (true/false), dengan bentuk sebagai berikut : ISEMPTY(Q) = True, jika Q adalah queue kosong. = False, jika Q bukan queue kosong.
3. INSERT Bentuk Umumnya : INSERT(elemen, Queue) INSERT(E,Q), di mana E = elemen dan Q = queue, adalah suatu operasi yang digunakan untuk memasukkan elemen E ke dalam queue Q. Didefinisikan, bahwa elemen E akan menjadi elemen yang berada pada posisi REAR dari queue Q. Akibat dari operasi ini adalah : - REAR(INSERT(E,Q)) = E - NOEL(Q) bertambah satu dan QNOEL adalah E Jika Q adalah queue kosong, maka :
ISEMPTY(INSERT(E,Q)) = False Dalam bentuk statement Pascal, biasanya dituliskan : IF ISEMPTY(Q) Then front(insert(E,Q)) = E Else front(insert(E,Q)) = front(Q) ;
4. REMOVE Bentuk Umum : REMOVE(elemen, queue) REMOVE(Q) berarti mengeluarkan elemen Q yang berada pada posisi FRONT. Akibat dari operasi ini, elemen Q akan berkurang satu dan elemen kedua (elemen yang berada disebelahnya) akan menjadi elemen yang berada pada posisi FRONT dari queue Q ini.
28
Selanjutnya, jika Q adalah queue kosong, maka REMOVE(Q) akan menghasilkan suatu Error. IF NOEL(Q) = 0 Then Remove(Q) = erroe_condition Remove(create(Q)) = error_condition
n
DEKLARASI QUEUE DALAM COBOL DAN PASCAL
Dalam bahasa pemrograman biasanya tidak ada fasilitas queue (built in queue). Untuk itu setiap programmer harus mendefinisikan sendiri dengan bantuan fasilitas yang ada. Pada umumnya fasilitas yang digunakan untuk mendeklarasikan queue adalah Array. Bentuk deklarasinya dalam bahasa Pascal dan Cobol adalah sebagai berikut :
m DALAM BAHASA PASCAL TYPE StrukQueue = Record Q : Array[1..100] of integer; Front, Rear : integer; End; VAR Q : StrukQueue;
m DALAM BAHASA COBOL 01 StrukQueue. 02 Q Occurs 100 times Pic 9(5). 02 Front Pic 9(3). 02 Rear Pic 9(3). Selanjutnya untuk keperluan operasinya (bentuk proses atau logikanya), harus dibuat suatu procedure tersendiri dan disesuaikan dengan aturan-aturan yang berlaku (yang telah didefinisikan). Berikut ini contoh sebuah procedure yang digunakan untuk menggantikan operator insert. Pada procedure berikut ini dimisalkan eon adalah elemen yang akan dimasukkan ke dalam queue dan noelmax adalah kapasitas maximum elemen-elemen yang dapat ditampung dalam queue. Procedure INSERT (eon : integer); Begin If (q.rear < noelmax) Then Begin q.rear := q.rear + 1; q.queue[q.rear] := eon; If (q.front = 0) Then q.front := 1 End Else overflow_condition End; Procedure REMOVE(var eoff : integer); 29
Begin If (q.front > 0) Then Begin eoff := q.queue[q.front]; If (q.front = q.rear) Then Begin q.front := 0; q.rear := 0; End Else q.front := q.front + 1 End Else underflow-condition End;
n CIRCULAR QUEUE Misal diberikan queue Q dengan jumlah maksimum elemen sebanyak 100, yang digambarkan sebagai berikut :
1
2
3
4
5
.................................
99
100
Queue di atas diisi secara berurutan empat elemen A, B, C dan D, sehingga bentuknya menjadi: A 1
B 2
C 3
D 4
5
6
FRONT = 1
7 ;
8
......................
99
100
REAR = 4
Kemudian dilakukan operasi REMOVE dua kali berurutan, sehingga bentuknya menjadi :
1
2
C 3
D 4
5
6
FRONT = 3 ;
7
8
......................
99
100
REAR = 4
Selanjutnya dilakukan operasi INSERT untuk 3 elemen secara berurutan, yaitu E, F dan G, maka bentuknya menjadi :
1
2
C 3
D 4
E 5
F 6
G 7
8
......................
99
100
30
FRONT = 3 ;
REAR = 7
Kemudian dilakukan operasi REMOVE lagi berurutan terhadap dua elemen, sehingga bentuknya menjadi :
1
2
3
4
E 5
F 6
G 7
FRONT = 5 ;
8
......................
99
100
REAR = 7
Terlihat bahwa elemen-elemen queue bergerak terus dari kiri ke kanan sepanjang arraynya. Apa yang terjadi bila suatu saat REAR = 100 dan kita masih akan memasukkan suatu elemen ke dalam queue ? Dalam keadaan ini, batas maksimum telah dicapai, padahal kita masih ingin menambah/memasukkan beberapa elemen lagi. Salah satu cara/pendekatan untuk menyelesaikan masalah seperti ini adalah dengan menambah ukuran array yang digunakan. Artinya kita harus mendeklarasikan array dengan ukuran yang besar untuk menempatkan queue tersebut. Tetapi cara ini dianggap tidak efektif, karena keadaan serupa masih dapat muncul kembali. Cara lain yang dianggap lebih baik adalah dengan mengubah queue tersebut ke dalam bentuk yang disebut CIRCULAR. Berikut ini contoh bentuk circular tersebut : ... Q(5)
Q(N-3)
Q(4) Q(N-2) Q(3) Q(N-1)
Q(2) Q(N) Q(1)
Dalam hal ini kondisi dari suatu queue kosong adalah :FRONT = REAR = 0 Jika queue hanya berisi dua elemen, maka bentuknya adalah :
F R
Selanjutnya jika elemen queue melampaui batas yang ada sedangkan kita masih memiliki ruang yang kosong, maka posisi FRONT dan REAR harus di-'reset' dulu agar kita bisa memasukkan elemen ke dalam queue tersebut. Berikut ini sebuah algoritma yang digunakan untuk operasi INSERT 31
start
REAR
ya
pd akhir array?
Move REAR ke posisi yg pertama dr array
tdk Move REAR satu posisi dalam array
FRONT & REAR pd posisi yg sama ?
ya
overflow
tdk
Insert elemen pd posisi REAR dlm array
satu-satunya elemen pd queue
ya
Move FRONT pd posisi tsb dlm array
tdk
selesai
Algoritma yang digunakan untuk operator REMOVE pada circular queue :
32
start
queue kosong ?
ya underflow
selesai
tdk REMOVE elemen pada posisi FRONT
satusatunya elemen pd queue ?
ya
reset FRONT dan REAR = 0
tdk
FRONT pd akhir array ?
ya
move FRONT ke posisi awal dari array
tdk move FRONT pd posisi yang baru dalam array
selesai
33
Sedangkan bentuk procedure-nya dalam bahasa Pascal adalah sebagai berikut PROCEDURE insert (eon : integer); BEGIN IF (q.rear = n) THEN q.rear := 1 ELSE q.rear := q.rear + 1; IF (q.rear = q.front) THEN overflow_condition ELSE BEGIN q.queue[q.rear] := eon; IF (q.front = 0) THEN q.front := 1 end; end; PROCEDURE remove (eoff : integer); BEGIN IF (q.front = 0) THEN underflow_condition ELSE BEGIN eoff := q.queue[q.front] ; IF (q.front = q.rear) THEN BEGIN q.front := 0; q.rear := 0 END ELSE IF (q.front = n) THEN q.front := 1 ELSE q.front:=q.front + 1 END; END;
34
