Queue adalah struktur data yang mirip dengan Stack. Perbedaan yang mencolok dibandingkan dengan Stack adalah menggunakan sistem FIFO (First In, First Out), dimana item atau elemen pertama yang ditambahkan ke dalam Queue akan menjadi item pertama yang dikeluarkan dari Antrian. Apabila menggunakan analogi, Queue dapat diibaratkan sebagai antrian pembeli untuk membeli makanan, dimana yang pertama mengantre akan menjadi yang pertama mendapatkan makanan.

Dalam istilah software, Queue adalah sebuah aturan atau koleksi elemen yang diatur secara linear atau barisan, seperti yang digambarkan sebagai berikut:

Queue memiliki dua ujung, yaitu "front" dan "rear" dari queue. Apabila queue dalam keadaan kosong, maka kedua pointer akan diatur menjadi -1 (dan item pertama pada queue akan memiliki indeks 0). "rear" pointer adalah posisi dimana elemen dimasukkan ke dalam queue, operasi ini "enqueue". Sedangkan "front" pointer adalah tempat dimana elemen dihilangkan dari queue, operasi ini disebut "dequeue".

Apabila sebuah queue[SIZE] memiliki nilai "rear" pointer sebesar SIZE-1, maka dapat dikatakan queue itu penuh. Apabila nilai dari "front" adalah NULL, maka queue itu kosong.

Operasi-operasi yang dapat dilakukan pada Queue adalah sebagai berikut:

1. Enqueue

Enqueue melakukan penambahan item atau elemen pada queue. Setiap penambahan item itu terjadi pada belakang queue. Enqueue memiliki algoritma sebagai berikut:

• Melakukan pengecekan pada queue apabila penuh
• Apabila queue penuh, tampilkan informasi "Queue Penuh" dan hentikan operasi.
• Apabila queue tidak penuh, lakukan increment pada "rear"
• Tambahkan elemen pada lokasi yang ditunjuk oleh "rear"
• Return success

2. Dequeue

Dequeue melakukan penghapusan item atau elemen pada queue. Setiap penghapusan item itu terjadi pada depan queue. Dequeue memiliki algoritma sebagai berikut:

• Melakukan pengecekan pada queue apabila kosong
• Apabila queue kosong, tampilkan informasi "Queue Kosong" dan hentikan operasi.
• Apabila queue tidak kosong, akses elemen yang ditunjuk oleh "front"
• Lakukan increment pada "front" ke elemen yang ditunjuk
• Return success

3. isEmpty

isEmpty akan melakukan pengecekan queue apabila queue dalam keadaan kosong

4. isFull

isFull akan melakukan pengecekan queue apabila queue dalam keadaan penuh

5. peek

peek akan mengambil nilai yang ada di depan queue namun tidak melakukan modifikasi pada nilai tersebut

Ilustrasi

1. Preprocessor dan Headerfile

#include <iostream>
#define MAX 20
using namespace std

Lakukan definisi menggunakan header <iostream> dan MAX sebagai besaran maksimal dari nilai array pada queue

2. Struct

struct Queue {
	int front, rear, data[MAX];
}Q;

Deklarasi struct berisi front dan rear yang akan berfungsi sesuai yang telah ditulis sebelumnya, yaitu penunjuk atau penanda pada queue.

3. Pengecekan stack

Fungsi-fungsi berikut berfungsi untuk mengecek keadaan stack, apakah Stack dalam keadaan kosong atau penuh.

bool isFull() {
	return Q.rear == MAX;
}

bool isEmpty() {
	return Q.rear == 0;
}

Fungsi isEmpty() sendiri akan mengembalikan nilai true (karena tipe data yang digunakan adalah boolean) jika nilai nya sebesar MAX, atau nilai maksimum data array, atau falsejika tidak sama. Fungsi isFull() akan mengembalikan nilai true jika nilainya sama dengan 0, atau false jika tidak sama.

4. Menambahkan data ke stack

void enqueue() {
	if (isFull())
	{
		cout << "Antrian penuh!"<<endl;
	}
	else {
		int data;
		//menambahkan data ke antrian
		cout << "Masukkan Data : ";cin >> data;
		Q.data[Q.rear] = data;
		//menempatkan tail pada elemen data terakhir yang ditambahkan
		Q.rear++;
		cout << "Data ditambahkan\n";
	}
}

Dalam hal menambahkan data ke antrian, maka algoritma yang perlu diperhatikan adalah

• Cek terlebih dahulu apakah Queue sudah penuh, jika penuh, maka hentikan.
• Jika tidak penuh, maka masukkan data ke dalam antrian dan tambahkan nilai ke "rear" untuk ditaruh di paling belakang
• Masukkan data ke dalam tempat yang diarahlan oleh top

5. Menghapus data dari stack

void dequeue() {
	if (isEmpty())
	{
		cout << "Antrian masih kosong"<<endl;
	}
	else{
		cout << "Mengambil data \"" << Q.data[Q.front] << "\"..." << endl;
		//menggeser antrian data ke head
		for (int i = Q.front; i < Q.rear; i++)
			Q.data[i] = Q.data[i + 1];
		//menempatkan tail pada data terakhir yang digeser
		Q.rear--;
	}
}

Mirip dengan menambahkan data, ada algoritma yang perlu diperhatikan ketika ingin menghilangkan data dari queue, yaitu:

• Periksa apakah queue kosong, jika kosong, maka hentikan.
• Jika tidak kosong, maka geser setiap data yang ada di belakang "front" dan mengurangi atau decrement nilai "rear"

6. Menampilkan data pada tumpukan

void printQueue() {
	if (isEmpty()) {
    cout << "Antrian kosong"<<endl;
	}
	else {
		cout << "QUEUE : ";
		for (int i = Q.front; i < Q.rear; i++)
		//menambahkan koma jika data tidak terdapat di antrian pertama
			cout << Q.data[i] << ((Q.rear-1 == i) ? "" : ",");
		cout << endl;
  }
}

Dalam menampilkan data, algoritmanya adalah sebagai berikut:

• Periksa apakah Queue kosong, jika kosong, maka hentikan.
• Jika tidak kosong, maka lakukan penampilan data satu-persatu menggunakan perulangan atau looping

Queue sebagai standard library tentu saja mirip dengan Stack, yang mana Queue ini sendiri memiliki header library sendiri yang bernama <queue>. Header tersebut memiliki beberapa functions yang bisa digunakan, diantaranya adalah

• (constructor) untuk melakukan insialisasi atau construct queue
• empty untuk mengecek apakah container dalam keadaan kosong
• size untuk mengembalikan nilai ukuran queue
• front untuk mengakses elemen selanjutnya
• back untuk mengakses elemen terakhir dari queue
• push untuk memasukkan elemen
• emplace untuk membuat dan memasukkan elemen
• pop untuk menghapus elemen berikutnya
• swap untuk menukar elemen

#include <iostream>       // std::cout
#include <queue>          // std::queue
using namespace std;

int main () 
{
  queue<int> my_queue;
  my_queue.push(7);
  my_queue.push(3);
  my_queue.front(); // returns 7
  my_queue.back(); // returns 3
}

Berikut adalah contoh inisialisasi queue menggunakan standard library (STL)

#include <iostream>
#include <queue>
using namespace std;

void showqueue(queue<int> gq)
{
    queue<int> g = gq;
    while (!g.empty())  
    {
        cout<<'\t'<<g.front();
        g.pop();
    }
    cout<<'\n';
}

int main()
{
    queue<int> gqueue;
    gqueue.push(10);
    gqueue.push(20);
    gqueue.push(30);
    gqueue.push(40);
    gqueue.push(50);

    cout<<"Queue : ";
    showqueue(gqueue);

    cout<<"Queue Size : "<<gqueue.size();
    cout<<"\nQueue Front : "<<gqueue.front();
    cout<<"\nQueue Back : "<<gqueue.back();
    
    gqueue.pop();
    cout<<"\nQueue Pop : Do .pop ";
    cout<<"\nFinal Queue : ";
    showqueue(gqueue);
}