Queue (Antrian)
Queue (antrian) merupakan representasi data yang hanya memperbolehkan pengaksesan
data pada dua ujung. Penyisipan data dilakukan dibelakan (ekor) dan pengeluaran data
dilakukan diujung (kepala). Berbeda dengan double lingked list pada praktikum 5 yang
diperbolehkan mengakses data di sembarang tempat. Perilaku seperti ini meniru kejadian
pada masalah antrian pada dunia nyata yakni yang pertama masuk dialah yang dilayani
duluan (FIFO). :
Dua operasi pada antrian yakni enQueue dan deQueue. Untuk menyisipkan data pada
antrian menggunakan enQueue dan menghapus data dari antrian menggunakan deQueue.
Queue (antrian) adalah struktur data dimana data yang pertama kali dimasukkan
adalah data yang pertama kali bisa dihapus. Atau bisa juga disebut dengan struktur data yang
menggunakan mekanisme FIFO (First In First Out).
Queue dalam kehidupan sehari-hari seperti antrian pada penjualan tiket kereta api,
dimana orang yang pertama datang adalah orang yang pertama kali dilayani untuk membeli
tiket. Jika ada orang baru yang datang akan membali tiket, maka posisinya berada pada
urutan paling belakang dalam antrian tersebut. Orang yang berada pada posisi terakhir dalam
antrian adalah yang terakhir kali dapat dilayani dan memperoleh tiket kereta api (kalau
kurang beruntung, maka akan kehabisan tiket). Contoh lain adalah nasabah yang antri di
teller bank, paket data yang menunggu untuk ditransmisikan lewat internet, antrian printer
dimana terdapat antrian print job yang menunggu giliran untuk menggunakan printer, dsb.
Fungsi dalam Queue:
Fungsi init : digunakan untuk membuat queue baru atau kosong, yaitu dengan
memberi nilai awal (head) dan nilai akhir (tail) dengan -1.
Fungsi full: digunakan untuk mengetahui apakah queue sudah penuh atau belum.
Dilakukan dengan memeriksa nilai akhir (tail) apakah sudah sama dengan maksimal
queue.
Fungsi empty: digunakan untuk mengetahui apakah queue masih kosong atau tidak.
Dilakukan dengan memeriksa nilai akhir (tail) bernilai -1 atau tidak.
Fungsi enqueue : digunakan untuk menambahkan elemen ke dalam queue.
Fungsi dequeue : digunakan untuk mengambil elemen dari queue, dengan cara
memindahkan semua elemen satu langkah ke posisi depannya sehingga elemen yang
paling depan tertimpa.
Fungsi clear : digunakan untuk menghapus semua elemen dalam queue. Ada dua cara
yang bisa digunakan, yaitu menuliskan fungsi seperti inisialisasi atau memanggil
fungsi remove sampai queue kosong.
Istilah-istilah yang digunakan dalam queue (antrian)
Memasukkan data (insert) disebut juga dengan put, add, atau enqueue.
Menghapus data (remove) biasa disebut dengan istilah delete, get, atau dequeue.
Bagian belakang queue, dimana data bisa dimasukkan disebut dengan back, tail (ekor), atau
end (akhir).
Sedangkan bagian depan (front) queue dimana data bisa dihapus juga biasa disebut dengan
istilah kepala (head).
Circular Queue
Di dunia nyata apabila seseorang sedang mengantri (misalnya antri tiket kereta api), apabila
telah dilayani dan memperoleh tiket, maka ia akan keluar dari antrian dan orang-orang yang
berada di belakangnya akan bergerak maju ke dapan. Kita bisa saja menggerakkan setiap item
data ke depan apabila kita menghapus data yang terdepan, tetapi hal ini kurang efektif.
Sebaliknya kita tetap menjaga setiap item data di posisinya, yang kita lakukan hanyalah
merubah posisi front dan rear saja.
Yang menjadi permasalahan adalah apabila posisi rear berada pada bagian akhir dari array
(atau pada nomor indeks yang terbesar). Meskipun ada bagian yang kosong di awal-awal
array – karena mungkin data telah dihapus, data baru tidak bisa dimasukkan lagi karena rear-
nya sudah tidak bisa bergerak lagi. Atau mungkinkah posisi rear nya bisa berpindah? Situasi
seperti itu bisa dilihat seperti gambar berikut:
Untuk menghindari permasalahan seperti itu (tidak bisa memasukkan data baru) – meskipun
queue-nya belum penuh, maka front dan rear-nya berputar (kembali) ke bagian awal array.
Kejadian seperti ini dinamakan dengan circular queue (atau kadang-kadang disebut juga
dengan istilah ring buffer). Kejadian seperti ini seperti terlihat pada gambar berikut:
Perhatikan bahwa setelah rear berputar (kembali) ke bagian awal array, posisinya sekarang di
bawah front, kebalikan dari posisi aslinya (front berada di bawah rear). Coba hapus beberapa
data sehingga pada suatu saat front juga akan berputar (balik) ke bagian awal array, sehingga
front dan rear akan ke susunan aslinya (front di bawah rear).
Pada Queue atau antrian Terdapat satu buah pintu masuk di suatu ujung dan satu buah
pintu keluar di ujung satunya dimana membutuhkan variabel Head dan Tail ( depan/front,
belakang/rear).
Karakteristik Queue atau antrian :
1. elemen antrian
2. front (elemen terdepan antrian)
3. tail (elemen terakhir)
4. jumlah elemen pada antrian
5. status antrian
Operasi pada Queue atau antrian
1. tambah(menambah item pada belakang antrian)
2. hapus (menghapus elemen depan dari antrian)
3. kosong( mendeteksi apakah pada antrian mengandung elemen atau tidak)
Operasi-operasi Queue :
1. Create()
Untuk menciptakan dan menginisialisasi Queue
Dengan cara membuat Head dan Tail = -1
2. IsEmpty()
Untuk memeriksa apakah Antrian sudah penuh atau belum
Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama
dalam antrian) yang tidak akan berubah-ubah
Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu
menggunakan nilai Tail.
3. IsFull
Untuk mengecek apakah Antrian sudah penuh atau belum
Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen
array pada C) berarti sudah penuh
4. Enqueue
Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di
elemen paling belakang
Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail
terlebih dahulu
5. Dequeue()
Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian
Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1
Penggeseran dilakukan dengan menggunakan looping.
6. Clear()
Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1
Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya
mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi
terbaca
7. Tampil()
Untuk menampilkan nilai-nilai elemen Antrian
Menggunakan looping dari head s/d tail
ADT Antrian
Dari ilustrasi gambar di atas ADT antrian dapat direpresentasikan sebagai berikut
Node
Object data
Node next
Node(Object)
Node(Object,Node)
Object getObject()
Node getNext()
List
Node nodeAwal, nodeAkhir;
String nama;
public List()
public List( String namaList )
public void sisipDiAwal(Object
dt)
public void sisipDiAkhir(Object
dt)
public Object hapusDrDepan()
public boolean kosong()
public void cetak()
Queue
List listAntrian
Queue()
enqueue(Object
object)
Object dequeue()
boolean kosong()
public void cetak()
Contoh Program Antrian :
Program Latihan Praktikum 1
pulic class Node {
Object data;
Node next;
Node( Object object ){this ( object, null );}
Node( Object object, Node node ){
data = object;
next = node;
}
Object getObject(){return data;}
Node getNext() {return next;}
}
Program Latihan Praktikum 2
public class List {
private Node nodeAwal;
private Node nodeAkhir;
private String nama;
public List(){ this( "list" ); }
public List( String namaList ){
nama = namaList;
nodeAwal = nodeAkhir = null;
}
public void sisipDiAwal( Object dt ){
if (kosong()) nodeAwal = nodeAkhir = new Node( dt );
else nodeAwal = new Node( dt, nodeAwal );
}
public void sisipDiAkhir( Object dt ){
if (kosong()) nodeAwal = nodeAkhir = new Node( dt );
else nodeAkhir = [Link] = new Node( dt );
}
public Object hapusDrDepan(){
Object itemDihapus = null;
if (!kosong()) {
itemDihapus = [Link];
if ( nodeAwal == nodeAkhir )
nodeAwal = nodeAkhir = null;
else nodeAwal = [Link];
}
return itemDihapus;
}
public boolean kosong(){return nodeAwal == null;}
public void cetak(){
if ( kosong() ){
[Link]( "Kosong %s\n", nama );
return;
}
[Link]( "Isi %s adalah : ", nama );
Node kini = nodeAwal;
while ( kini != null ){
[Link]( "%s ", [Link] );
kini = [Link];
}
[Link]( "\n" );
}
}
Program Latihan Praktikum 3
public class Queue {
private List listAntrian;
public Queue() {
listAntrian = new List( "queue" );
}
public void enqueue( Object object ){
[Link]( object );
}
public Object dequeue(){
return [Link]();
}
public boolean kosong(){
return [Link]();
}
public void cetak(){[Link]();}
public static void main( String args[]){
Queue q = new Queue();
[Link]( 10 );
[Link]();
[Link]( 40 );
[Link]();
[Link]( 25 );
[Link]();
[Link]( 30 );
[Link]();
Object dtHapus = null;
while(![Link]()){
dtHapus = [Link]();
[Link]("%s dihapus \n",dtHapus );
[Link]();
}
}
}
Screenshot Program :
Penjelasan :
KESIMPULAN
Antrian (Queue) adalah suatu kumpulan data yang penambahan elemennya hanya bisa
dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear), dan penghapusan atau
pengambilan elemen dilakukan lewat ujung yang lain (disebut dengan sisi depan atau
front). Antrian (Queue) mempunyai prinsip FIFO (Firs In Firs Out) bahwa yang pertama
masuk maka yang pertama keluar .Contoh penggunaan atau implementasi dari ADT
Queue misalnya aplikasi untuk antrian di rumah sakit, mailbox dalam komunikasi antar
proses, simulasi dan modeling (misalnya simulasi sistem pengendali lalu lintas udara)
dalam memprediksi performansi, Waiting Line pada Sistem Operasi
Operasi pada Queue yaitu Create (untuk membuat antrian), IsEmpty (untuk mengecek apakah
antrian kosong), IsFull (untuk mengecek apakah antrian penuh), enQueue (untuk menambah data
pada elemen terakhir), deQueue (untuk menghapus data pada elemen pertama), dan Clear (untuk
mengosong antrian)