QUEUE (ANTRIAN)

PENDAHULUAN

Pada pokok bahasan ini akan dibahas mengenai antrian atau queue, dimana struktur data hamper sama dengan tumpukan atau stack yang merupakan struktur data yang linier. Perbedaanya adalah operasi penambahan dan pengurangan pada ujung yang berbeda. Setelah mempelajari materi ini diharapkan mahasiswa mampu :

1. Mengetahui dan memahami definisi antrian.
2. Memahami operasi-operasi dasar pada antrian.
3. Memahami representasi statis dan dinamis pada antrian.

PENYAJIAN (TUTORIAL)

Antrian adalah suatu kumpulan data yang penambahan elemenya hanya bisa dilakukan pada suatu ujung (disebut sisi belakang atau REAR), dan penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain (disebut sisi depan atau FRONT). Prinsip yang digunakan dalam antrian ini adalah FIFO (First In First Out) yaitu elemen yang pertama kali masuk akan keluar pertama kalinya.

Penggunaan antrian antara lain simulasi antrian di dunia nyata (antrian pembelian tiket), sistem jaringan computer (pemrosesan banyak paket yang dating dari banyak koneksi pada host, bridge, gateway), dan lain-lain.

Karakteristrik penting antrian sebagai berikut :

1. Elemen antrian yaitu item-item data yang terdapat dalam antrian.
2. Head/front (elemen terdepan antrian).
3. Tail/rear (elemen terakhir antrian).
4. Jumlah antrian pada antrian (count).
5. Status/kondisi antrian, ada dua yaitu :

-          Penuh

Bila elemen di antrian mencapai kapasitas maksimum antrian. Pada kondisi ini, tidak mungkin dilakukan penambahan ke antrian. Penambahan di elemen menyebabkan kondisi kesalahan Overflow.

-          Kosong

Bila tidak ada elemen antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.

Operasi-operasi pokok pada antrian diantaranya adalah :

1. Create Membuat antrian baru.

NOEL(CREATE(Q))=0

            FRONT(CREATE(Q))=tidak terdefinisi

            REAR(CREATE(Q)=tidak terdefinisi

2. IsEmpty Untuk memeriksa apakah antrian sudah penuh atau belum.

ISEMPTY(Q)=True, jika Q adalah queue penuh.

3. IsFull Mengecek apakah antrian sudah penuh atau belum.

ISFULL(Q)=True, jika Q adalah queue penuh.

4. Enqueue/Insert Menambahkan elemen kke dalam antrian, penambahan elemen selalu ditambahkan di dalam elemen paling belakang.

REAR(INSERT(A,Q))=A

ISEMPTY(INSERT(A,Q))=FALSE

Algoritma QINSERT :

a.       IF FRONT = 1 AND REAR = N, OR IF FRONT = REAR +

1, THEN OVERFLOW, RETURN

b.      IF FRONT := NULL, THEN

SET FRONT := 1 AND REAR := 1

ELSE IF REAR = N,

THEN SET REAR := 1

ELSE

SET REAR := REAR+!

c.       SET QUEUE[REAR] := ITEM

d.      RETURN

5. Dequeu/Remove Unttuk menghapus elemen terdepan/pertama dari antrian.

Algoritma QDELETE :

a.       IF FRONT := NULL, THEN UNDERFLOW, RETURN

b.      SET ITEM := QUEUE{FRONT]

c.       [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+!

d.      RETURN

Representasi Queue :

Representasi statis

Queue dengan representasi statis biasanya diimplementasikan dengan menggunakan array. Sebuah array memiliki tempat yang dialokasikan diawal sehingga sebuah elemen yang dimasukkan dalam sebuah array terbatas pada tempat yang ada pada array. Karena menggunakan array maka queue dengan representasi statis dalam mengalami kondisi elemen penuh. Ilustrasi queue dengan representasi statis dapat dilihat pada gambar :

Representasi dinamis

Queue dengan representasi dinamis biasanya diimplementasikan dengan menggunakan pointer yang menunjuk pada elemen-elemen yang dialokasikan pada memori