Artikel antrian (dalam struktur data)

Queue (antrian) adalah struktur data dimana elemen (item) yang pertama kali dimasukkan adalah yang pertama kali bisa dikeluarkan (First In First Out, FIFO). Ada 3 macam struktur QUEUE (Antrian) yang menggunakan Array Satu Dimensi diantarnya adalah liniear queue, circular queue, dan double ended queue (deque).

Cara kerja queue seperti pada antrian loket kereta api. Orang yang lebih dahulu mengantri adalah orang yang pertama kali dilayani untuk membeli tiket kereta. Orang yang paling belakang antriannya akan dilayani paling terakhir. Contoh yang lain misalnya: antrian di teller bank, pesawat terbang yang menunggu untuk mengudara, atau paket data yang menunggu untuk dikirimkan melalui internet. Ada banyak contoh queue yang mengerjakan tugasnya di sebuah sistem operasi (atau jaringan) komputer. Ada queue printer dimana tugas pencetakan menunggu sampai printer siap mencetak.

Queue juga menyimpan data ketukan kunci yang diketikkan pada keyboard. Jadi, jika Anda menggunakan program pengolah kata (misalnya OpenOffice.org) tetapi komputer sedang mengerjakan tugas lain ketika Anda sedang mengetikkan sebuah kunci, ketukan tersebut tidak akan hilang; akan menunggu dalam queue sampai pengolah kata mempunyai waktu untuk membacanya. Digunakannya queue menjamin ketukan keyboard tetap dalam antrian sampai dapat diproses.

Istilah yang digunakan untuk memasukkan dan mengeluarkan pada sebuah stack adalah standar yaitu push dan pop. Tidak demikian dengan queue. Memasukkan bisa juga disebut put atau add atau enqueue, sedangkan mengeluarkan bisa disebut dengan delete atau get atau dequeue. Tempat di belakang queue, dimana elemen (item) dimasukkan, disebut dengan back atau tail atau end. Yang depan, dimana elemen (item) dikeluarkan, bisa juga disebut dengan head (kepala). Untuk menyamakan persepsi kita gunakan saja istilah insert, remove, front, dan rear.