QUEUE

QUEUE (ANTREAN)

ANTREAN (Queue)

Suatu bentuk khusus dari linear list, dengan operasi penyisipan (insertion) hanya diperbolehkan pada salah satu sisi, yang disebut REAR, dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi yang lainnya, yang disebut FRONT dari list.

Antrean Q = [Q1, Q2, ... , QN]

Front(Q) = Q1 bagian depan antrean

Rear(Q) = QN bagian belakang antrean

Noel(Q) = N jumlah elemen dalam antrean

Operasi Antrean : FIFO (First In First Out)

Elemen yang pertama masuk merupakan elemen yang pertama keluar.

Operator : Penyisipan : Insert

Penghapusan : Remove

Empat operasi dasar antrean, yaitu :

1. CREATE

2. ISEMPTY

3. INSERT

4. REMOVE

• CREATE (Q)

Operator yang menunjukkan suatu antrean hampa Q.

Berarti : Noel (Q) = 0

Front (Q) & Rear (Q) = tidak terdefinisi

• ISEMPTY (Q)

Operator yang menunjukkan apakah antrean Q hampa.

Operand : tipe data antrean

Hasil : tipe data boolean

ISEMPTY (CREATE (Q)) = True

• INSERT (E, Q)

Operator yang menginsert elemen E ke dalam antrean Q.

E ditempatkan di bagian belakang antrean.

Hasil : antrean yang lebih besar.

REAR (INSERT (E, Q)) = E

ISEMPTY (INSERT (E, Q)) = False

• REMOVE (Q)

Operator yang menghapus elemen bagian depan dari antrean Q.

Hasil : antrean yang lebih pendek.

Pada setiap operasi, Noel (Q) berkurang 1 dan elemen ke-2 menjadi elemen terdepan.

Jika Noel (Q) = 0 maka Q = hampa

Remove (Q) = kondisi error (underflow condition)

Remove (Create (Q)) = kondisi error (underflow condition)

PENYAJIAN DARI ANTREAN

1. One Way List (Linear Linked List)

2. Array

Array Queue

Kalau tidak disebutkan lain, maka Antrean disajikan dalam Array Queue, dilengkapi 2 variabel penunjuk :

FRONT (elemen depan antrean)

REAR (elemen belakang antrean)

ALGORITMA

1. QINSERT (Memasukkan data ke dalam suatu antrean)

Memeriksa kemungkinan terjadi overflow, yakni dengan melihat apakah antrean tersebut terisi penuh.

2. QDELETE (Menghapus elemen depan dari antrean)

Memeriksa kemungkinan terjadi underflow, yakni dengan melihat apakah antrean tersebut kosong.

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.

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

Front := Null,

Dalam hal lain

Jika Front = N, maka Front := 1

Dalam hal lain

Front := Front + 1

4. Return.

DEQUE (Queue Ganda atau Double Queue)

Suatu linear list, yang penambahan dan penghapusan elemen dapat dilakukan pada kedua sisi ujung list, tetapi tidak dapat dilakukan ditengah-tengah list.

Deque (menggunakan array sirkular)

Menggunakan 2 pointer/penunjuk :

1. LEFT : sisi kiri dari deque

2. RIGHT : sisi kanan dari deque

Asumsi : elemen deque berurut dari kiri ke kanan.

ANTREAN BERPRIORITAS

Himpunan elemen, yang setiap elemennya telah diberikan sebuah prioritas, dan urutan proses penghapusan elemen adalah berdasarkan aturan berikut :

1. Elemen yang prioritasnya lebih tinggi, diproses lebih dahulu dibandingkan dengan elemen yang prioritasnya lebih rendah.

2. Dua elemen dengan prioritas yang sama, diproses sesuai dengan urutannya sewaktu dimasukkan ke dalam antrean berprioritas.

PENYAJIAN ONE WAY LIST DARI ANTREAN BERPRIORITAS

Ketentuan :

1. Setiap simpul dalam list berisi 3 buah data/field yaitu :

(Info, Prn, Link)

2. Simpul X mendahului simpul Y di dalam list, bila :

a. X mempunyai prioritas lebih tinggi dari Y.

b. Mempunyai prioritas yang sama, tetapi X dimasukkan kedalam queue terlebih dahulu sebelum Y.

Ket : Simpul dengan Prn rendah, mendapat prioritas tertinggi.

REFERENSI : MODUL PRAKTIKUM STRUKTUR DATA dari PJ-nya

Free Template Blogger collection template Hot Deals SEO