QUEUE (ANTREAN)

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.

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.

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.

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 ini menunjukkan bagaimana menyajikan suatu antrean dalam sebuah array QUEUE dengan N elemen. Gambar itu juga menunjukkan bagaimana melakukan pemasukan dan penghapusan elemen antrean.