< Queue >

QUEUE >>

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.

DEFINISI >>

•Bersifat FIFO (First In First Out)

•Elemen yang pertama masuk ke antrian akan keluar pertama kalinya

•ENQUEUE: menambahkan data pada sebuah list

•DEQUEUE adalah mengeluarkan satu elemen dari suatu Antrian

•Antrian dapat dibuat dengan menggunakan 2 cara: Liniear Array dan Circular Array

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

Queue (Antrian)

1. Dikenali data pertama (Head) dan data terakhirnya (Tail)

2.Aturan penambahan dan penghapusan datanya didefinisikan sebagai berikut ::

     - Penambahan selalu dilakukan dari belakang

     - Penghapusan selalu dilakukan dari depan

3. Satu data dengan data lain dapat diakses melalui informasi

4. Pada queue prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out)

Data-data di dalam antrian dapat bertipe integer, real, record

Contoh aplikasi queue dalam kehidupan sehari-hari:

1. Antrian di jalan tol
2. Antrian saat mengantri di loket
3. Antrian reservasi tiket kereta api, dll
Semua itu menggunakan aturan FIFO (First In, First Out)


Operasi-operasi pada Antrian (queue):

1.Create()
Untuk menciptakan dan menginisialisasi Queue
Dengan cara membuat Head dan Tail  = -1

2. IsEmpty()
Untuk memeriksa apakah antrian masih kosong atau sudah terisi
Dengan cara memeriksa nilai tail, jika tail = -1 maka empty
Pergerakan pada Antrian terjadi dengan penambahan data 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 data array pada C) berarti sudah penuh

4. Enqueue
Untuk menambahkan data ke dalam antrian, penambahan data selalu ditambahkan di data paling belakang
Penambahan data selalu menggerakan variabel tail dengan cara increment counter tail

5. Dequeue()
Digunakan untuk menghapus data terdepan dari Antrian
Dengan cara mengurangi counter tail dan menggeser semua data antrian kedepan.
Penggeseran dilakukan dengan menggunakan looping

6. Clear()
Untuk menghapus semua data Antrian dengan cara membuat tail dan head = -1
Penghapusan data-data antrian sebenarnya tidak menghapus arraynya, namun hanya mengeser indeks pengaksesannya ke nilai -1 sehingga data-data Antrian tidak lagi terbaca

7. Tampil()
Untuk menampilkan nilai-nilai data Antrian menggunakan looping dari head s/d tail