Allabout queue & deque
QUEUE ( ANTREAN )
4.1. PENGERTIAN QUEUE (ANTREAN)
Setelah pada Bab 3 yang lalu kita bahas tentang salah satu jenis daftar (list) linear, yakni
stack, kali ini kita bahas jenis lain dari daftar linear, yakni queue atau antrean. Struktur
data antrean atau queue adalah suatu bentuk khusus dari linear list, dengan operasi
penyisipan (insertion) hanya diperbolehkan pada salah satu sisi, yang disebut sisi belakang
(REAR), dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi lainnya, yang
disebut sisi depan (FRONT), dari list.
Sebagai contoh dapat kita lihat antrean (Q1, Q2,...,QN). Kita notasikan bagian depan
dari antrean Q sebagai FRONT(Q) dan bagian belakang sebagai REAR(Q).
Jadi untuk antrean Q = [Q1, Q2, …, QN] :
FRONT(Q) = Q1 dan REAR(Q) = QN
Kita menggunakan notasi NOEL(Q) untuk menyatakan jumlah elemen di dalam
antrean Q. NOEL(Q) mempunyai harga integer. Untuk antrean Q = [Q1,Q2,…, QN], maka
NOEL(Q) = N.
Operator penyisipan (insertion) disebut INSERT dan operator penghapusan (deletion)
disebut REMOVE.
Pengantar Struktur Data Bab 4 – Queue (Antrean)
66
Sebagai contoh untuk memperjelas bekerjanya antrean, kita perhatikan sederetan
operasi berikut ini. Kita mulai dengan antrean hampa Q. Antrean hampa Q, atau Q[ ] dapat
disajikan seperti terlihat pada Gambar 4-1
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Gambar 4.1. Antrean hampa
Di sini :
NOEL(Q) = 0
FRONT(Q) = tidak terdefinisi
REAR(Q) = tidak terdefinisi
Lalu kita INSERT elemen A, diperoleh Q = [A], seperti terlihat di Gambar 4.2.
- - - - - - - - - - - - - - - - - -
A
- - - - - - - - - - - - - - - - - -
Gambar 4.2. Elemen A dimasukkan
Di sini :
NOEL(Q) = 1
FRONT(Q) = A
REAR(Q) = A
Dilanjutkan dengan INSERT elemen B, sehingga diperoleh Q = [A, B], seperti terlihat
di Gambar 4-3.
- - - - - - - - - - - - - - - - - -
A B
- - - - - - - - - - - - - - - - - -
Gambar 4.3. Elemen B dimasukkan setelah elemen A
Di sini :
NOEL(Q) = 2
FRONT(Q) = A
REAR(Q) = B
Dilanjutkan dengan INSERT elemen C, sehingga diperoleh Q = [A, B, C], seperti
terlihat di Gambar 4.4.
- - - - - - - - - - - - -
A B C
- - - - - - - - - - - - -
Gambar 4.4. Elemen C dimasukkan setelah elemen B
Pengantar Struktur Data Bab 4 – Queue (Antrean)
67
Di sini :
NOEL(Q) = 3
FRONT(Q) = A
REAR(Q) = C
Dilanjutkan dengan DELETE satu elemen dari Q, sehingga diperoleh Q = [B, C],
seperti terlihat di Gambar 4.5.
- - - - - - - - - - - - -
B C
- - - - - - - - - - - - -
Gambar 4.5. Satu elemen dihapus
Di sini :
NOEL(Q) = 2
FRONT(Q) = B
REAR(Q) = C
Demikian seterusnya, kita dapat melakukan serangkaian INSERT dan DELETE yang
lain. Suatu kesalahan underflow dapat terjadi, yakni apabila kita melakukan penghapusan
pada antrean hampa. Antrean dikatakan beroperasi dalam cara FIRST-IN-FIRST-OUT
(FIFO). Disebut demikian karena elemen yang pertama masuk merupakan elemen yang
pertama ke luar.
Model antrean, sangat sering ditemukan dalam kejadian sehari-hari, seperti mobil yang
menunggu untuk pengisian bahan bakar, mobil pertama dari antrean merupakan mobil
pertama yang akan keluar dari antrean. Sebagai contoh lain adalah orang yang menunggu
dalam antrean di suatu bank. Orang pertama yang berada di dalam barisan tersebut akan
merupakan orang pertama yang akan dilayani.
4.2 OPERASI DASAR PADA ANTREAN
Ada 4 operasi dasar yang dapat dilakukan pada struktur data antrean, yakni :
1. CREATE(antrean)
2. ISEMPTY(antrean)
3. INSERT(elemen,antrean)
4. REMOVE(antrean)
Pandang misalnya antrean Q = [Q1, Q2, …, QNOEL], maka :
Pengantar Struktur Data Bab 4 – Queue (Antrean)
68
CREATE(antrean) :
CREATE(Q) adalah suatu operator untuk membentuk dan menunjukkan suatu antrean
hampa Q.
Berarti :
NOEL(CREATE(Q)) = 0
FRONT(CREATE(Q)) = tidak terdefinisi
REAR(CREATE(Q)) = tidak terdefinisi
ISEMPTY(antrean)
ISEMPTY(Q) adalah operator yang menentukan apakah antrean Q hampa atau tidak.
Operand dari operator ini merupakan antrean, sedangkan hasilnya merupakan tipe data
boolean.
Di sini :
ISEMPTY(antrean) = true, jika Q hampa, yakni jika NOEL(Q)=0
= false, dalam hal lain.
Maka, ISEMPTY(CREATE(Q)) = true.
INSERT(elemen, antrean)
INSERT(E,Q) adalah operator yang memasukkan elemen E ke dalam antrean Q. Elemen
E ditempatkan di bagian belakang dari antrean. Hasil dari operasi ini adalah antrean yang
lebih panjang.
REAR(INSERT(E,Q)) = E
QNOEL adalah E
ISEMPTY(INSERT(E,Q)) = false
REMOVE(antrean)
REMOVE(Q) adalah operator yang menghapus elemen bagian depan dari Antrean Q.
Hasilnya merupakan antrean yang lebih pendek. Pada setiap operasi ini, harga dari
NOEL(Q) berkurang satu, dan elemen kedua dari Q menjadi elemen terdepan.
Jika NOEL(Q) = 0, maka REMOVE(Q) memberikan suatu kondisi error, yakni suatu
underflow. Jelas bahwa REMOVE(CREATE(Q)) juga memberikan kondisi underflow
error.
Pengantar Struktur Data Bab 4 – Queue (Antrean)
69
4.3 PENYAJIAN DARI ANTREAN
Antrean dapat disajikan di dalam komputer dalam berbagai cara. Biasanya dengan
menggunakan one-way-list (linear linked list) ataupun menggunakan array. Kalau tidak
disebutkan lain, maka antrean kita sajikan dalam array QUEUE, dengan dilengkapi dua
variabel penunjuk. FRONT, berisi lokasi dari elemen DEPAN antrean dan REAR, berisi
lokasi dari elemen BELAKANG antrean. Nilai FRONT = NULL menunjukkan bahwa
antrean adalah hampa.
Gambar 4.6 menunjukkan bagaimana menyajikan suatu antrean dalam sebuah array
QUEUE dengan N elemen. Gambar itu juga menunjukkan bagaimana melakukan
pemasukan dan penghapusan elemen antrean.
Pada Gambar 4.6(a) terlihat bahwa antrean mula-mula terdiri atas elemen AAA
(sebagai DEPAN), BBB, CCC, dan DDD (sebagai BELAKANG). Gambar 4.6.(b) menunjukkan
keadaan setelah penghapusan elemen. Di sini elemen DEPAN yakni AAA
dihapus. Gambar 4.6.(c) menggambarkan keadaan setelah penambahan berturut-turut
elemen EEE dan FFF. Terakhir sekali, keadaan setelah penghapusan elemen DEPAN,
BBB.
Gambar 4.6. Cara kerja antrean
Pengantar Struktur Data Bab 4 – Queue (Antrean)
70
Dapat kita lihat bahwa pada setiap kali penghapusan, nilai lokasi FRONT akan
bertambah 1. Untuk setiap kali pemasukan elemen, nilai REAR akan bertambah 1. Hal ini
berakibat bahwa setelah pemasukan elemen ke N (berawal dari antrean hampa), maka
lokasi QUEUE(N) telah diduduki. Di sini mungkin saja tidak sebanyak N elemen ada
dalam antrean (karena sudah dilakukan beberapa penghapusan).
Untuk melakukan pemasukan berikutnya, yakni memasukkan elemen ITEM, kita dapat
menggunakan lokasi QUEUE(1). Demikian seterusnya. Dalam hal ini, kita menggunakan
array sirkular, yakni bahwa QUEUE(1) datang sesudah QUEUE(N) di array dalam.
Berdasarkan asumsi ini, maka REAR adalah 1.
Secara yang sama, jika FRONT = N dan kita akan melakukan penghapusan, maka
sekarang FRONT adalah 1, bukan N+l.
Gambar 4.7 memperlihatkan antrean yang disimpan dalam array dengan 5 lokasi
memori, sebagai array sirkular.
Pengantar Struktur Data Bab 4 – Queue (Antrean)
71
Gambar 4.7. Circular Array
Sekarang kita akan menampilkan algoritma QINSERT, yang dimaksudkan untuk
memasukkan data ke dalam suatu antrean. Yang mula-mula kita laksanakan dalam
algoritma adalah, memeriksa kemungkinan terjadi overflow error, yakni dengan melihat
apakah antrean tersebut terisi penuh.
Algoritma kedua adalah algoritina QDELETE yang dimaksudkan untuk menghapus
elemen DEPAN dari antrean.Yang mula-mula kita laksanakan ialah memeriksa
kemungkinan terjadi underflow error, yakni dengan melihat apakah antrean tersebut
kosong.
Algoritma QINSERT
QINSERT(QUEUE, N, FRONT, DATA)
1. [Apakah antrean penuh]
Jika FRONT := 1 dan REAR := N, atau jika FRONT := REAR + 1, maka write
OVERFLOW, return.
2. Jika FRONT := NULL, maka FRONT := 1
REAR := 1
dalam hal lain
jika REAR := N, maka
REAR := 1
dalam hal lain
REAR := REAR + 1
3. QUEUE(REAR) := DATA (masukkan elemen baru)
4. Return
Algoritma QDELETE
QDELETE(QUEUE, N, FRONT, REAR, DATA)
1. [Apakah antrean kosong]
Jika FRONT := NULL, maka
Write : UNDERFLOW, return
2. DATA := QUEUE(FRONT)
Pengantar Struktur Data Bab 4 – Queue (Antrean)
72
3. (FRONT mendapat nilai baru). Jika FRONT := REAR, maka (antrean memuat
hanya 1 elemen) FRONT := NULL.
REAR := NULL, dalam hal lain
Jika FRONT := N, maka FRONT := 1, dalam hal lain :
FRONT := FRONT + 1
4. Return.
4.4 DEQUE
Kali ini akan kita bicarakan beberapa struktur data yang merupakan bentuk variasi dari
struktur data antrean atau queue, yang telah kita bicarakan terdahulu. Struktur data tersebut
adalah deque (atau deck atau dequeue) dan Antrean berprioritas (atau priority queue).
DEQUE adalah suatu linear list atau daftar linear, yang penambahan dan penghapusan
elemennya dapat dilakukan pada kedua sisi ujung list, tetapi tidak dapat dilakukan di
tengah-tengah list. Dari sini, kita boleh mengatakan bahwa deque adalah suatu queue
ganda atau double queue.
Ada banyak cara penyajian suatu deque di dalam komputer. Namun yang biasa
digunakan adalah penyajian dengan cara penempatan di dalam sebuah array sirkular atau
array putar DEQUE.
Di sini kita menggunakan dua pointer atau penunjuk, LEFT dan RIGHT, yang
berturut-turut menunjuk pada sisi kiri dan sisi kanan dari deque. Kita senantiasa
mengasumsikan bahwa elemen deque berurut dari kiri ke kanan. Pengertian sirkular di atas
timbul karena elemen DEQUE(l) berada sesudah elemen DEQUE(N) dari array.
Gambar 4.8 menggambarkan 2 buah deque, masing-masing berisi 4 elemen, yang
ditempatkan di dalam sebuah array dengan 8 lokasi memori. Kondisi LEFT = NULL
dipergunakan untuk menyatakan bahwa suatu deque adalah hampa.
Selain deque dengan sifat yang telah kita sebutkan di atas, masih ada 2 model variasi
deque. Kedua variasi tersebut adalah deque input terbatas, dan deque output terbatas, yang
merupakan tengah-tengah antara deque dan antrean.
Deque input terbatas adalah suatu deque yang membatasi pemasukan elemen hanya
pada satu ujung dari list, sementara penghapusan elemen boleh dilakukan pada kedua
ujung list.
Deque output terbatas adalah suatu deque yang hanya memperbolehkan penghapusan
elemen pada salah satu ujung, tetapi memperbolehkan pemasukan elemen pada kedua
ujung list.
