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.
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
|
F
|
|
|
|
|
|
|
|
|
||
|
|
FRONT
|
|
|
|
|
REAR
|
|
|
|
F
|
E
|
D
|
C
|
B
|
A
|
|
|
|
|
|
|
|
|
||
|
|
REAR
|
|
|
|
|
FRONT
|
|
atau dapat pula
digambarkan dengan posisi tegak.
PRINSIP KERJA QUEUE
Prinsip kerja Queue adalah FIFO (First In First Out), di mana data yang masuk terlebih
dahulu akan keluar pertama.
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.
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
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 :
DALAM BAHASA PASCAL
TYPE StrukQueue = Record
Q : Array[1..100] of integer;
Front, Rear : integer;
End;
VAR Q : StrukQueue;
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);
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;
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
|
B
|
C
|
D
|
|
|
|
|
|
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
......................
|
99
|
100
|
FRONT
= 1 ; REAR = 4
Kemudian dilakukan operasi REMOVE dua kali
berurutan, sehingga bentuknya menjadi :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C
|
D
|
|
|
|
|
|
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
......................
|
99
|
100
|
FRONT
= 3 ; REAR
= 4
Selanjutnya dilakukan operasi INSERT untuk
3 elemen secara berurutan, yaitu E, F dan G, maka bentuknya menjadi :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C
|
D
|
E
|
F
|
G
|
|
|
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
......................
|
99
|
100
|
FRONT
= 3 ; REAR
= 7
Kemudian dilakukan operasi REMOVE lagi
berurutan terhadap dua elemen, sehingga bentuknya menjadi :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
E
|
F
|
G
|
|
|
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
......................
|
99
|
100
|
FRONT
= 5 ; 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 :
Dalam hal ini
kondisi dari suatu queue kosong adalah :FRONT = REAR = 0
Jika queue hanya
berisi dua elemen, maka bentuknya adalah :
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
Algoritma yang
digunakan untuk operator REMOVE pada circular queue :
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;