Implementasi
Queue di C++
Queue
atau antrian merupakan suatu kumpulan data yang memiliki head/front dimana data
dikeluarkan (dequeue) dan tail/rear dimana data dimasukkan (enqueue) ke
antrian.
Proses QUEUE
Seperti
halnya pada antrian yang biasa kita lakukan sehari-hari, di manapun. Antrian
dimulai dari depan ke belakang, jika didepan belum pergi meninggalkan antrian
maka antrian terus bertambah dari belakang dan antrian paling belakang disini
dinamakan rear/tail.
Jadi
selama antrian terus bertambah (enqueue) maka antrian yang paling akhir adalah
tail/rear.
Jika
ada yang keluar dari antrian (dequeue) maka data tersebut adalah yang paling
depan (head/front), dan data berikutnya setelah data yang keluar berubah
menjadi yang paling depan (head/front).
Queue
menggunakan metode FIFO, dimana yang masuk pertama kali akan keluar pertama
kali juga.
Program QUEUE
- Untuk mengimplementasikan program queue di C++ kita membutuhkan tiga method atau fungsi enqueue(); untuk menambahkan data ke antrian, dequeue(); untuk me ngeluarkan data dari antrian dan printQueue() untuk menampilkan queue.
- Selain tiga fungsi tersebut, kita akan membuat dua fungsi opsional untuk mengecek apakah antrian kosong isEmpty() dan antrian penuh isFull().
- Untuk menyimpan data kita bisa menggunakan empty array dengan maksimum array yang nanti akan kita definisikan sebagai maksimum antrian, jadi kita bisa mengetahui indeks pertama adalah front dan data indeks yang kosong untuk menambahkan data sebagai rear-nya.
- Untuk data antriannya terstruktur kita bisa menggunakan struct sehingga lebih mudah mengakses data front, rear dan array datanya sendiri seperti sebuah object.
- Karena ini adalah program konsole maka tentu kita juga akan membuat fungsi main().
Kode Program QUEUE
1. Preprocessor dan Header File
#include <iostream>
#define MAX 20 //maksimum data queue
using namespace std;
Disini kita hanya menggunakan dua baris preprocessor untuk
mendefinisikan header file iostream untuk standard input/output stream
dan MAX untuk maksimum data array pada queue/antrian.
2. Struct data
//Deklarasi struct antrian
struct Queue {
int front, rear,
data[MAX];
}Q;
Pada struct kita mendeklarasikan front,
rear dan array data[] dengan jumlah array dari data
maksimum yang telah di definisikan sebelumnya yaitu MAX.
Deklarasi variabel pada struct
sama halnya dengan pendeklarasian variabel pada umumnya, karena disini kita
hanya memiliki tipe data yang sama, jadi kita bisa menghemat baris dengan
menyebariskan tiga variabel bertipe integer.
Info:
Disini kita hanya membuat program untuk mengetahui dasar implementasi queue di
c++, Sebenarnya kita juga bisa menggunakan variabel data
dengan tipe data lain selain integer, atau sebagai data struct
seperti pada program sederhana ini.
3. Memeriksa antrian
//cek apakah antrian penuh
bool isFull() {
return Q.rear ==
MAX;
}
//cek apakah antrian kosong
bool isEmpty() {
return Q.rear ==
0;
}
Kedua fungsi ini akan digunakan untuk memeriksa apakah
antrian penuh isFull() (fungsi pertama) dan antrian kosong
isEmpty(), keduanya mengembalikan nilai
boolean, jadi kita cukup mengembalikan nilai perbandingan pada fungsi masing -
masing.
- Pada fungsi isFull() akan mengembalikan nilai true jika nilai Q.rear sama dengan maksimum data array yang telah ditentukan MAX, atau false jika tidak sama.
- Pada fungsi isEmpty() akan mengembalikan nilai true jika nilai Q.rear sama dengan 0, atau false jika tidak sama.
4. Menampilkan Antrian
//Menampilkan Queue
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;
}
}
Untuk menampilkan antrian, kita
perlu memeriksa apakah antriannya kosong. Jika kosong maka tidak ada data untuk
ditampilkan, jadi cukup tampilkan pesan. Tapi jika antrian berisi data atau ada
antrian disana maka tampilkan data yang ada di antrian menggunakan for
loop.
Disini kode di dalam perulangan/loop
hanyalah elemen setiap data yang telah dimasukkan dengan menggunakan koma
kecuali data terakhir.
Info :
Mungkin kalian bertanya kenapa kita tidak memulai membuat fungsi yang utama
dari program yang kita tulis yaitu enqueue(), dequeue() dan fungsi dan kode lain
setelahnya.
Ini dikarenakan kompiler pada c++
membaca kode yang kita tulis dari baris atas ke bawah. Kompiler tidak akan
mengkompile program jika ada variabel atau fungsi yang tidak di definisikan
atau di deklarasikan.
Kompiler
juga tidak akan mengkompile program dengan variabel atau fungsi yang di
didefinisikan di baris paling bawah, tapi di panggil pada baris kode di
atasnya.
5. Input Data ke antrian
//manambahkan data ke antrian
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";
printQueue();
}
}
Untuk menginputkan data ke antrian
hal utama yang perlu kita lakukan adalah memeriksa apakah antrian penuh atau
tidak, jika penuh, maka kita tidak dapat menambahkan data ke antrian karena
sudah tidak ada ruang lagi yang tersedia.
Jika masih ada ruang maka inputkan
data ke antrian dan tambahkan satu nilai ke Q.rear dimana data tersebut berada pada
antrian paling belakang.
Disini
kita juga memanggil fungsi printQueue() yang telah didefinisikan pada baris
kode sebelumnya, secara langsung setelah data ditambahkan. Jadi user bisa
melihat data ada di dalam antrian.
6. Mengambil Data antrian
// mengambil data dari antrian
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--;
printQueue();
}
}
Sama halnya dengan menampilkan
antrian, untuk mengambil data dari dalam antrian atau mengeluarkannya
(dequeue), pertama kali kita perlu memeriksa apakah ada data dalam antrian.
Karena kita tidak dapat menghapus data yang tidak ada pada antrian.
Jika
ada data pada antrian, maka geser data ke antrian palng depan atau Q.front,
disini kita akan menimpa data yang keluar dari antrian yang paling depan dan
kemudian mengurangi satu nilai Q.rear.
7. Menampilkan Menu
int main() {
int choose;
do
{
//Tampilan
menu
cout
<< "-------------------\n"
<<
" Menu Pilihan\n"
<<
"-------------------\n"
<<
" [1] Enqueue \n"
<<
" [2] Dequeue\n"
<<
" [3] Keluar \n\n"
<<
"-------------------\n"
<<
"Masukkan pilihan : "; cin >> choose;
switch
(choose)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
default:
cout
<< "Pilihan tidak tersedia";
break;
}
} while (choose
!=3);
return 0;
}
Setelah semua fungsi dan variabel
yang kita butuhkan telah tersedia, langkah terakhir adalah menggunakan
fungsi-fungsi dan variabel tersebut menjadi sebuah program yang kita inginkan (program
queue) dengan memanggilnya dan memolesnya menjadi sebuah menu pada fungsi main.
Disini kita hanya perlu menggunakan perulangan while dan switch untuk menentukan pilihan user.
switch
akan memeriksa pilihan user (disini adalah nilai variabel choose
dengan tipe data integer). Disini hanya ada dua pilihan. pilihan pertama jika
user ingin menambahkan data ke antrian dan pilihan kedua jika user ingin
menghapus atau mengeluarkan data dari antrian. Selain dari kedua pilihan
tersebut maka tampilkan pesan pilihan
tidak tersedia.
Sedangkan
while sendiri akan mengulang pilihan pada switch,
selama user tidak memilih pilihan dengan nilai 3 atau choose == 3.
DAFTAR PUSTAKA
https://bekti.net/blog/implementasi-queue-di-cpp/
