|
Q U E U E
|
Queue adalah salah satu list linier
dari struktur data. Queue beroperasi dengan cara First In First Out (FIFO)
elemen pertama masuk merupakan elemen yang pertama keluar. Untuk penyisipan (INSERT)
hanya dapat dilakukan pada satu sisi yaitu sisi belakang (REAR),
sedangkan untuk penghapusan (REMOVE) pada sisi depan (FRONT)
dari list.
Sebagai gambaran, cara kerja queue
dapat disamakan pada sebuah antrean di suatu loket dimana berlaku prinsip ‘
siapa yang duluan antre dia yang akan pertama kali dilayani ‘ , sehingga dapat
dikatakan prinsip kerja queue sama dengan prinsip sebuah antrean.
Representasi dari Queue
 |
hapus
elemen 1 2
…….. ke – n sisip elemen
front rear
Di
bawah ini diperlihatkan suatu queue yang akan menempati N elemen array memori,
serta cara pengurangan (delete) dan penambahan (added) elemen pada queue
tersebut.
|
Front : 1
Rear :
4
1 2 3 4 5 6 7 ..... N
REMOVE(Q)
|
Front : 2
Rear :
4
1 2 3 4 5 6 7 ..... N
INSERT(INSERT(E),F)
|
Front : 2
Rear :
6
1 2 3 4 5 6 7 ..... N
REMOVE(Q)
|
Front : 3
Rear :
6
1 2 3 4 5 6 7 ..... N
Dapat dilihat bahwa setiap terjadi
penghapusan elemen pada queue nilai (index) dari Front bertambah satu (1) ; dapat ditulis FRONT := FRONT+1
Begitu pula bila terjadi penambahan
elemen pada queue nilai (index) Rear bertambah satu (1) ; dapat ditulis REAR := REAR + 1
Akan terjadi ketidakefisienan bila
penambahan elemen sudah pada posisi index N (Rear = N) maka tidak dapat lagi
dilakukan penambahan elemen, sedangkan dilokasi memori yang lain (nilai di
bawah N) masih terdapat memori array yang kosong.
Untuk mengatasi hal tersebut maka kita
bayangkan bahwa memori dari queue tersebut berbentuk melingkar dimana kedua
ujungnya saling bertemu atau disebut juga dengan Circular Queue
Circular Queue
Anggap Queue ini mempunyai ukuran m
elemen. Karena sisip elemen di
lakukan pada satu sisi dan hapus elemen dilakukan pada sisi yang lain, maka Q(m) disatukan dengan Q(1)
{adjacent}.
Pada gambar di bawah, elemen-elemen
queue menduduki tempat Q(f) sampai dengan Q(r) dimana pointer Front menunjuk ke
Q(f) dan pointer REAR menunjuk ke Q(r).
Kondisi overflow terjadi jika (r+1)
mod m = f dan kondisi underflow terjadi jika r = f = 0
|
|
|
|
|
|
 |
Front
|
|||||||
|
|||||||
|
|||||||
 |
|||||||
|
|
|
|
|
|
|
|
|
|
Q(1)
|
Q(2)
|
......
|
Q(f)
|
Q(f+1)
|
......
|
Q(r)
|
......
|
Q(m)
|
Ket.
Gambar diarsir adalah tempat kedudukan elemen-elemen queue dari
Q(f) sampai Q(r)
Contoh :
Suatu queue
akan menempati lokasi sebanyak 5 array memori, dengan urutan operasi sebagai
berikut :
1. Create(Q) F
= 0
R
= 0
1 2 3 4 5
|
2. Insert A, B, C F
= 1
R
= 3
|
3. Remove (Q) F
= 2
R
= 3
|
4. Insert D dan E F
= 2
R
= 5
|
5. Remove(Remove(Q)) F
= 4
R
= 5
|
6. Insert F F
= 4
R
= 1
|
7. Remove(Q) F
= 5
R
= 1
|
8. Insert G, H, K F
= 5
R
= 4
|
9. Insert L F
= 5
( OVERFLOW ) R =
4
|
10. Remove(Remove(Q)) F
= 2
R
= 4
|
11. Insert L F
= 2
R
= 5
|
12. Remove(Remove(Q)) F
= 4
R
= 5
|
13. Remove(Remove(Q)) F
= 0
R
= 0
|
14. Remove(Q) F
= 0
R
= 0
( UNDERFLOW )
Operasi dasar pada
Queue
1. CREATE
Adalah suatu operator
untuk membentuk dan menunjukkan suatu antrean hampa Q.
Noel ( Create(Q)) = 0
Front (Create(Q))=
tidak terdefinisi
Rear (Create(Q)) =
tidak terdefinisi
2. ISEMPTY
Adalah operator yang
menentukan apakah antrean Q hampa atau tidak. Hasil dari operator ini merupakan
tipe data berjenis Boolean.
Isempty (Q) = True ,
jika Q hampa
= False , jika Q tidak hampa.
3. INSERT
Suatu operator yang menyisipkan elemen
ke dalam queue pada bagian belakang (rear)
-
REAR
(INSERT(A,Q)) = A
-
ISEMPTY
(INSERT(A,Q)) = FALSE
Algoritma QINSERT
1. if FRONT = 1 and REAR = N , or If
FRONT = REAR + 1, then
OVERFLOW, Return
2. if FRONT := NULL, then
set FRONT := 1 and REAR := 1
else if REAR = N , then
set REAR := 1
else
set
REAR := REAR + 1
3. set QUEUE [REAR] := ITEM
4. Return
4. REMOVE
Operator yang menghapus elemen bagian
depan (FRONT)dari QUEUE
Algoritma QDELETE
1. if FRONT := NULL , then UNDERFLOW ,
Return
2. set ITEM := QUEUE[FRONT]
3. [find new value of FRONT]
if FRONT = REAR , then
set
FRONT := NULL and REAR := NULL
else if FRONT = N, then
set
FRONT := 1
else
set
FRONT := FRONT + 1
4. Return
Latihan :
1. Diketahui Queue menempati 6 array memori
|
Jika dilakukan operasi berturut-turut
sebagai berikut :
a. Insert X
b. Remove (Queue)
c. Remove (insert(M,Queue))
d. Insert (S, Remove(Queue))
Maka hasilnya adalah :
2. Diketahui Queue dengan 7 array memory
|
Nilai awal Front = 2 dan Rear = 4
Jika dilakukan operasi secara berturutan :
a. Insert MM
b. Remove (Queue)
c. Insert
(SS,insert(PP,insert,(KK,)))
d. Remove (Remove(Queue))
Maka Hasilnya adalah :
a. Queue : ---, CC , AA , BB , ..... , ....., .....
FRONT =
REAR =
b. Queue : .... , ..... , ..... , ...... , ..... , ..... , .....
FRONT =
REAR =
c. Queue : .... , ..... , ..... , ...... , ..... , ..... , .....
FRONT =
REAR =
Queue : .... , ..... , ..... , ......
, ..... , ..... , .....
FRONT =
REAR =
Queue : .... , ..... , ..... , ......
, ..... , ..... , .....
FRONT =
REAR =
d. Queue : .... , ..... , ..... , ...... , ..... , ..... , .....
FRONT =
REAR =
Queue : .... , ..... , ..... , ......
, ..... , ..... , .....
FRONT =
REAR =
DEQUEUE (DOUBLE ENDED QUEUE)
DEQUEUE adalah suatu List Linier, yang
penambahan dan penghapusan elemen-nya dapat dilakukan pada kedua sisi ujung
List, tetapi tidak dapat dilakukan ditengah-tengah list. Dari sini dapat kita
katakan bahwa Dequeue adalah suatu Queue ganda atau Double Ended Queue.
Deque menggunakan dua pointer penunjuk
yaitu :
LEFT :
petunjuk untuk elemen pada posisi kiri
RIGHT : petunjuk untuk elemen pada posisi kanan
Sebagai gambaran :
|
|
|
|
AAA
|
BBB
|
CCC
|
DDD
|
|
1 2
3 4
5 6 7
8
Left : 4
Right : 7
|
YYY
|
ZZZ
|
|
|
|
|
WWW
|
XXX
|
1 2
3 4
5 6 7 8
Left : 7
Right : 2
Ada dua jenis Dequeue :
1. Input-Restricted-Deque
adalah
deque yang operasi pemasukan elemen datanya hanya dapat dilakukan di satu ujung
kanannya (RIGHT), tetapi dapat menghapus dari kedua ujungnya ( LEFT dan RIGHT).
2. Output-Restricted-Deque
adalah
deque yang operasi pemasukan elemen datanya dapat dilakukan melalui kedua
ujungnya (LEFT dan RIGHT), tetapi hanya dapat menghapus dari ujung
kanannya(RIGHT).
Contoh DEQUEUE :
Diketahui Circular Dequeue
dengan 6 array memori :
|
Left : 2
Right : 4
dilakukan operasi
berturut-turut :
1. F
is added to the Right of the deque
2. 2
item on the Right are deleted
3. K,
L, M are added to the Left
4. One
item on the Left is deleted
5. R
is added to the Left
6. S
is added to the Right
7. T
is added to the Right
Jawab :
1. ---, A , C , D , F , ---
2. ---, A , C , ---,---,---
3. K , A , C ,---, M , L
4. K , A , C ,---,---, L
5. K , A , C ,---, R , L
6. K , A , C , S , R , L
7. LEFT = RIGHT+1 , Queue is Full Then
OVERFLOW
Tidak ada komentar:
Posting Komentar