QUEUE
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
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 :
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 :
Queue di atas diisi secara berurutan empat elemen A, B, C dan D, sehingga bentuknya menjadi:
FRONT = 1 ; REAR = 4
Kemudian dilakukan operasi REMOVE dua kali berurutan, sehingga bentuknya menjadi :
Selanjutnya dilakukan operasi INSERT untuk 3 elemen secara berurutan, yaitu E, F dan G, maka bentuknya menjadi :
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
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
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;
0 komentar:
Posting Komentar