Antrian / Queue

Antrian. Secara umum adalah daftar elemen yang sedang menunggu proses. Di dalam routing LAN dan WAN, adalah merupakan paket yang sedang dalam antrian untuk dikirimkan ke interface router.

Pengertian Queue (Antrian)
Queue / Antrian adalah suatu kumpulan data yang mana penambahan
elemen hanya bisa dilakukan pada satu ujung (disebut dengan sisi belakang atau
rear) dan penghapusan atau pengambilan elemen dilakukan lewat ujung lain
(disebut dengan sisi depan atau front).
Antrian menggunakan prinsip Pertama Masuk Pertama Keluar – First In
First Out (FIFO). Dengan kata lain urutan masuk sama dengan urutan keluar.
Antrian banyak dijumpai dalam kehidupan sehari-hari. Mobil-mobil yang
mengantri digerbang tol untuk membeli karcis tol; orang-orang yang mengantri di
loket untuk membeli karcis film juga membentuk antrian.
Pada antrian kita tidak menentukan batasan seberapa banyak antrian itu akan
berakhir tapi jika kita menggunakan array untuk mengimplementasikan queue/
tumpukan kita harus membatasi jumlah antrian yang dapat masuk. Ini dikarenakan
array memiliki batasan (upperbound) yang menjadi penghambat jika kita
menggunakan antrian. Oleh sebab itu kita akan mengimplementasikan antrian ini
dengan menggunakan link list.
Dengan menggunakan link list tepatnya Single Link List maka elemen dapat
dimasukkan secara tidak terbatas. Kita menggunakan Header Single Link List
Queue (Antrian)yang seperti Stack pada posisi Header dapat kita pergunakan untuk menyimpan
informasi mengenai banyaknya elemen dalam Queue.

Notasi Pada Queue
Notasi yang dapat digunakan didalam Queue Q adalah :
1. FRONT(Q) menunjukkan posisi terdepan dari suatu antrian. Contoh jika
kita mempunyai antrian Q = [A,B,C,D,E] maka FRONT(Q) = A.
2. REAR(Q) menunjukkan posisi terakhir dari suatu antrian. Contoh jika kita
mempunyai antrian Q = [A,B,C,D,E] maka REAR(Q) = E.
3. NOEL(Q) menunjukkan jumlah elemen di dalam Antrean Q. Contoh jika
kita mempunyai antrian Q = [A,B,C,D,E] maka NOEL(Q) = 5.
6.3. Deklarasi Queue Dalam Link List
Pendeklarasian Queue di dalam link list sama seperti kita mendeklarasikan link
list. Menggunakan pointer sebagai variabel yang menunjuk ke elemen antrian
selanjutnya.
Deklarasi Queue menggunakan Linked List di dalam Pascal :
Type
Queue = ^Simpul
Simpul = Record
Info : Char;
Next : Queue;
End;
Var
Head, Tail : Queue;
Max : Byte;
Link list yang kita gunakan ialah jenis Header Single Link List. Kita
menggunakan jenis link list ini karena pada bagian header dapat kita manfaatkan
untuk menyimpan informasi mengenai banyaknya elemen dalam Antrian
(NOEL(Q)).


Operasi Dasar Pada Queue
Ada 4 operasi dasar yang dapat dilakukan pada struktur data antrian, yaitu:
1. CREATE(Q)
CREATE(Q) adalah suatu operator yang digunakan untuk membentuk dan
menunjukkan suatu antrian hampa. Contoh :
NOEL(CREATE(Q)) = 0
FRONT(CREATE(Q)) = Tidak Terdefinisi
REAR(CREATE(Q)) = Tidak Terdefinisi
Berikut ini merupakan procedure CREATE simpul pada Pascal :
Procedure CREATE(Var Head, Tail : Queue);
Begin
New(Head);
Head^.Info := 0;
Head^.Next := Head;
Tail := Head;
End;
2. ISEMPTY(Q)
ISEMPTY(Q) adalah operator yang menentukan apakah antrian Q hampa
atau tidak. ISEMPTY(Q) di terapkan di dalam pascal menjadi sebuah function
yang bertipe boolean sehingga hasil dari function ini akan bernilai True jika
antrian dalam keadaan kosong / hampa (NOEL(Q) = 0) dan akan bernilai
False jika antrian dalam keadaan terisi / tidak kosong (NOEL(Q) > 0). Contoh
:
ISEMPTY(CREATE(Q)) = True
Berikut ini merupakan procedure ISEMPTY simpul pada Pascal :
Function ISEMPTY(Head : Queue);
Begin
ISEMPTY := (Head^.Next = Head);
End;



3. INSERT(E,Q)
INSERT(E,Q) adalah operator yang digunakan untuk memasukkan elemen E
pada antrian Q di posisi depan dari antrian. Hasil dari operator ini adalah
antrian yang lebih panjang.
Berikut ini merupakan procedure INSERT simpul pada Pascal :
Procedure INSERT(Elemen : Byte; Var Head, Tail : Queue);
Var Temp : Queue;
Begin
New(Temp);
Temp^.Info := Elemen;
Temp^.Next := Head;
Tail := Temp;
Inc(Head^.Info);
End;
4. REMOVE(Q)
REMOVE(Q) adalah operator yang menghapus elemen bagian depan dari
antrian Q. Hasilnya merupakan antrian 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 erroe, yakni suatau UNDERFLOW. Contoh :
REMOVE(CREATE(Q)) = UNDERFLOW.
Berikut ini merupakan procedure REMOVE simpul pada Pascal :
Procedure REMOVE(Var Head : Queue);
Var Temp : Queue;
Begin
If Not (ISEMPTY(Head)) Then
Begin
Temp := Head^.Next;
Head^.Next := Temp^.Next;
Dispose(Temp);
Dec(Head^.Info);
End;
End;



Untuk memahami pengertian antrian sekaligus penerapan operator-operator queue
dan notasi-notasinya perhatikan ilustrasi berikut :
CREATE(Q) = Membuat Antrian Baru
ISEMPTY(Q) = Apakah Antrian dalam keadaan kosong ?
REMOVE(Q) = Mengeluarkan elemen terdepan dari dalam antrian.
INSERT(1,Q) = Memasukkan elemen 1 kedalam antrian.
INSERT(2,Q) = Memasukkan elemen 2 kedalam antrian.
INSERT(3,Q) = Memasukkan elemen 3 kedalam antrian.
REMOVE(Q) = Mengeluarkan elemen terdepan dari dalam antrian.
INSERT(4,Q) = Memasukkan elemen 3 kedalam antrian.
ISEMPTY(Q) = Apakah Antrian dalam keadaan kosong ?
= Q
FRONT(Q) = Tidak Terdefinisi
REAR(Q) = Tidak Terdefinisi
NOEL(Q) = 0
= Q
FRONT(Q) = 1
REAR(Q) = 1
NOEL(Q) = 1
1
= Q
FRONT(Q) = 1
REAR(Q) = 2
NOEL(Q) = 2
1 2
= Q
FRONT(Q) = 1
REAR(Q) = 3
NOEL(Q) = 3
1 2 3
= Q
FRONT(Q) = 2
REAR(Q) = 3
NOEL(Q) = 2
2 3
= Q
FRONT(Q) = 2
REAR(Q) = 4
NOEL(Q) = 3
2 3 4
= Q
FRONT(Q) = Tidak Terdefinisi
REAR(Q) = Tidak Terdefinisi
NOEL(Q) = 0
UNDERFLOW !!!
= Q
FRONT(Q) = Tidak Terdefinisi
REAR(Q) = Tidak Terdefinisi
NOEL(Q) = 0
TRUE
= Q
FRONT(Q) = Tidak Terdefinisi
REAR(Q) = Tidak Terdefinisi
NOEL(Q) = 0
FALSE