Queue

Karakteristik yang membedakan queue (antrian) dari stack adalah cara
menyimpan dan mengambil data dengan struktur first in first out (FIFO). Hal ini berarti
elemen pertama yang ditempatkan pada queue adalah yang pertama dipindahkan.
Contoh yang paling populer untuk membayangkan sebuah queue adalah antrian
pada kasir sebuah bank. Ketika seorang pelanggan datang, akan menuju ke belakang
dari antrian. Setelah pelanggan dilayani, antrian yang berada di depan akan maju. Pada
saat menempatkan elemen pada ujung (tail) dari queue disebut dengan enqueue, pada
saat memindahkan elemen dari kepala (head) sebuah queue disebut dengan dequeue.
Pada Gambar 5.1 diperlihatkan sebuah queue serta proses enqueue dan dequeue.
Gambar 5.1 (1) Queue dengan 2 elemen; (2) Queue setelah proses enqueue C, D dan E;
(3) Setelah proses dequeue A dan B
4.1 Karakteristik Queue
Karakteristik penting dari antrian adalah :
B C D
D
head
A
A
B
E
C E
􀁘
􀁙
􀁚
tail
head
head
tail
tail
30
1. Elemen antrian yaitu item-item data yang terdapat di elemen antrian
2. Front (elemen terdepan dari antrian)
3. Rear (elemen terakhir dari antrian)
4. Jumlah elemen pada antrian (Count)
5. Status antrian
Kondisi antrian yang menjadi perhatian adalah ;
1. Penuh
Bila elemen pada antrian mencapai kapasitas maksimum antrian. Pada kondisi ini,
tidak mungkin dilakukan penambahan ke antrian. Penambahan elemen
menyebabkan kondisi kesalahan Overflow.
2. Kosong
Bila tidak ada elemen pada antrian. Pada kondisi ini, tidak mngkin dilakukan
pengambilan elemen dari antrian. Pengambilan elemen menyebabkan kondisi
kesalahan Overflow.
4.2 Representasi Antrian
Representasi antrian secara sekuen relatif lebih sulit dibanding stack. Seperti
dijelaskan di atas bahwa antrian juga merupakan satu kumpulan data. Dengan demikian
tipe data yang sesuai untuk menyajikan antrian adalah menggunakan array atau linked
list.
4.2.1 Implementasi Antrian dengan Array
Seperti halnya pada tumpukan, maka dalam antrian kita juga mengenal ada dua
operasi dasar, yaitu menambah elemen baru yang akan kita tempatkan di bagian
belakang antrian dan menghapus elemen yang terletak di bagian depan antrian.
Disamping itu seringkali kita juga perlu melihat apakah antrian mempunyai isi atau dalam
keadaan kosong.
Operasi penambahan elemen baru selalu bisa kita lakukan karena tidak ada
pembatasan banyaknya elemen dari suatu antrian. Tetapi untuk menghapus elemen,
maka kita harus melihat apakah antrian dalam keadaan kosong atau tidak. Tentu saja kita
tidak mungkin menghapus elemen dari suatu antrian yang sudah kosong.