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 = [Q₁, Q₂, ... , Q_N]

• Front(Q)        = Q₁                  bagian depan antrean
• Rear(Q)          = Q_N                 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)