Struktur Data

Antrian (Queue)

Antrian adalah suatu kumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear), dan penghapusan (pengambilan elemen) dilakukan lewat ujung lain (disebut dengan sisi depan atau front). Maka antrian prinsip yang digunakan adalah “masuk pertama keluar pertama” atau FIFO (First In First Out). Dengan kata lain, urutan keluar elemen akan sama urutan masuknya.

Contoh lain yang lebih relevan dalam bidang computer adalah pemakaian sistem computer berbagi waktu (time-sharing-computer system) dimana ada sejumlah pemakai yang akan menggunakan sistem tersebut secara serempak. Karena sistem ini biasanya menggunakan sebuah professor dan sebuah pengingat utama, maka jikab professor sedang dipakai oleh seorang pemakai =, pemakai-pemakai lain harus antri sampai gilirannya tiba. Antirian ini mungkin tidak akan dilayani secara FIFO murni, tetapi didasarkan pada suatu prioritas tertentu. Antrian terbagi menjadi 3 yaitu antrian linier (lurus), antrian sirkular (melingkar) dan antrian double enden.

Operasi pada antrian :

1.    Menambah elemen (Add (x,q) ) Artinya menambah elemen x kedalam antrian Q.

Penambahan elemen dapat dilakukan pada saat antrian belum penuh, dimana antrian belum penuh jika posisi belakang (Q.Belakang < n).

Algoritma :

Procedure Add (x : tipe data, Q : stack)

If Q. Belakang < n then

Q. Belakang = Q. Belakang + 1

Q. Isi [Q. Belakang] = x

Else

Antrian sudah penuh

Fi

2.    Menghapus elemen (Del (q) ) Artinya menghapus elemen dari antrian Q.

Sifat antrian adalah FIFO, sehingga data yang di hapus duluan adalah data yang duluan masuk. Penghapusan elemen dapat dilakukan terhadap antrian jika komponen ada dalam antrian, untuk mengetahui bahwa elemen dalam antrian adalah jika posisi Depan < = Belakang . (Q. Depan <= Q. Belakang).

Procedure Del (Q : antrian)

If Q. Depan <= Q. Belakang

Then

Write Q. Isi [q.depan]

q.depan = q.depan + 1

else

antrian kosong

fi

Masalah :

Pada saat posisi belakang berada pada posisi belakang dan depan berada pada posisi n (hanya ada satu elemen), maka ketika kita lakukan Add (x, q) maka informasi mengatakan antrian penuh.

Algoritma :

Procedure Add (x : tipe data, Q : stack)

If Q. Belakang < n then

Q. Belakang = Q. Belakang + 1

Q. Isi [Q. Belakang]= x

Else

Antrian sudah penuh

Fi