Definisi Queue

Secara harfiah, arti dari kata queue (berasal dari bahasa latin cauda {dibawa kepada masyarakat Inggris oleh orang Perancis}) adalah antrian. Sementara dalam istilah pemrograman artinya tidak jauh dari antrian. Berbeda dengan stack (tumpukan) yang menggunakan konsep LIFO (Last In First Out), konsep dari queue adalah FIFO (First In First Out), dimana data yang masuk lebih awal akan dikeluarkan terlebih dahulu.

Contoh konkret dari ADT (Abstract Data Type {tipe data abstrak} ) Queue adalah antrian pada loket bioskop. Yang mengantri terlebih dahulu akan dilayani dahulu.

Beberapa operasi dasar pada Queue pada C++ adalah:

Bool empty();

• Untuk mengecek apakah stack kosong atau tidak.

<tipe data> front();

• Untuk melihat data pada Queue terdepan. Metode ini me-return value.

Void pop(); / <tipe data> pop();

• Untuk mengeluarkan data pada Queue terdepan. Metode ini dapat dibuat me-return value.

Void push(<tipe data>);

• Untuk menambahkan data pada ujung Queue.

Int size();

• Untuk melihat dan mengembalikan nilai yang menunjukkan besar atau panjang Queue.

Java tidak secara spesifik memberi class khusus pada Queue. Untuk itu, kita harus menciptakan class tersendiri beserta metode-metodenya.

Deque

Di samping Queue, terdapat Deque. Deque adalah double-ended-Queue. Maksudnya adalah queue operasi penambahan dan pengambilan elemen dapat dilakukan pada kedua ujung Queue (baik depan maupun belakang, tapi tidak secara bersamaan).

Perbedaan implementasi Queue dengan Linked list dan Array

Array	Linked List
Dapat terjadi Underflow dan Overflow	Dapat terjadi Underflow dan Overflow (Overflow hanya akan terjadi saat memory dalam keadaan benar-benar penuh, jadi akan sangat langka terjadi)
Elemen yang dihapus harus diset ke null	Elemen yang dihapus tidak harus diset ke null

Linked List dalam Queue

Menambahkan node baru ke dalam Queue

Mengeluarkan node dari Queue