Struktur Data dan Algoritma ( Queue )

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

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.

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).

Jenis-jenis Antrian

Selain antrian yang telah kita bahas di atas, masih ada dua tipe antrian lagi

yang penggunaannya juga banyak di dalam kehidupan sehari hari atau dalam

dunia komputer itu sendiri, diantaranya adalah :

1. DEQUE

DEQUE adalah antrian dimana elemennya bisa masuk dan keluar lewat

kedua ujungnya (berbeda dengan queue yang hany bisa masuk lewat ujung

belakang dan keluar lewat ujung depan). Biasanya DEQUE disajikan dengan

menggunakan Double link list yang memiliki dua buah pointer yang

menunjuk ke posisi sebelumnya dan sesudahnya. Gambar 5.1 menunjukkan

struktur umum dari sebuah DEQUE.

DEQUE juga mempunyai dua jenis variasi yaitu :

a. Deque input terbatas : suatu deque yang membatasi pemasukkan

elemen hanya pada satu ujung dari list, sementara penghapusan

elemen boleh dilakukan pada kedua ujung list.

b. Deque output terbatas : merupakan kebalikan dari deque input

terbatas yaitu suatu deque yang membatasi penghapusan elemen

hanya pada satu ujung dari list, sementara pemasukkan elemen boleh

dilakukan pada kedua ujung list.

2. ANTRIAN BERPRIORITAS

Antrian berprioritas adalah suatu queue yang setiap elemennya telah

diberikan sebuah prioritas, dan urutan proses penghapusan elemen adalah

berdasarkan aturan berikut :

a. Elemen yang prioritasnya lebih tinggi, diproses lebih dahulu

dibandingkan dengan elemen yang prioritas lebih rendah.

b. Dua elemen dengan prioritas yang sama, diproses sesuai dengan urutan

mereka sewaktu dimasukkan ke dalam priority queue.

Salah satu contoh antrian berprioritas ini adalah sistem berbagi waktu (time

sharing system), dimana program yang mempunyai prioritas tinggi akan

dikerjakan lebih dahulu dan program-program yang berprioritas sama akan

membentuk antrian yang biasa.