PENGERTIAN QUEUE (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.
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.
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
- - - - - - - - - - - - - - - - - -
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.
- - - - - - - - - - - - - - - - - -
AB
- - - - - - - - - - - - - - - - - -
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.
- - - - - - - - - - - - -
ABC
- - - - - - - - - - - - -
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
- - - - - - - - - - - - -


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.

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:
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.
58 STRUKTUR DATA
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.

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. Gambar4.6.(c) menggambarkan keadaan setelah penambahan berturut-turut elemen EEE danFFF. Terakhir sekali, keadaan setelah penghapusan elemen DEPAN, BBB.

AAA
QUEUE
BBB CCC DDD . . .
1 2 3 4 5 6 7 . . .
N
FRONT : 1
REAR : 4
1 2 3 4 5 6 7 . . .
N
QUEUE
FRONT : 2 BBB CCC DDD . . .
REAR : 4

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.
Sekarang kita akan menampilkan algoritma QINSERT, yang dimaksudkan untuk
memasukkan data ke dalam suatu antrean. Yang mula-mula kita laksanakan dalam algoritmaadalah, memeriksa kemungkinan terjadi overflow error, yakni dengan melihat apakah antreantersebut terisi penuh.
Algoritma kedua adalah algoritina QDELETE yang dimaksudkan untuk menghapus
elemen DEPAN dari antrean.Yang mula-mula kita laksanakan ialah memeriksa kemungkinanterjadi 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
FRONT : 4
REAR : 1
QUEUE
F D E
FRONT : 5
REAR : 1
QUEUE
F E
FRONT : 5
REAR : 3
QUEUE
F G H E
FRONT : 1
REAR : 3
QUEUE
F G H
QUEUE (ANTREAN) 61
Algoritma QDELETE
QDELETE(QUEUE, N, FRONT, REAR, DATA)
1. [Apakah antrean kosong]
Jika FRONT:= NULL, maka
Write: UNDERFLOW, return
2. DATA:= QUEUE(FRONT)
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.