PENGERTIAN QUEUE BESERTA JENIS DAN CONTOHNYA PADA C++
PENGERTIAN QUEUE BESERTA JENIS DAN CONTOHNYA PADA C++
PENGERTIAN QUEUE
Queue atau antrian adalah suatu kumpulan data, dimana penambahan elemen hanya bisa dilakukan di satu ujung (disebut sisi belakang atau rear) dan penghapusan (pengambilan) elemen dilakukan melaui ujung yang lain (disebut sisi depan atau front). Prinsip pada queue adalah FIFO (First In First Out), yaitu objek yang pertama masuk ke dalam queue, akan dikeluarkan terlebih dahulu dari queue, dengan kata lain: urutan masuk elemen = urutan keluar elemen.Operasi semua pada Queue :
Menginisialisasi Queue baru
IsFull mengecek apakah QUEUE sudah penuh
IsEmpty mengecek apakah QUEUE sudah kosong
Enqueue menambah data pada QUEUE pada tumpukan paling belakang
Dequeue mengambil data pada QUEUE pada tumpukan paling depan
Show mencetak semua data dalam tumpukan
Sebagai ilustrasi dari penggunaan operator-operator di atas, perhatikan contoh berikut ini: Dimulai dari sebuah Queue S kosong, S = [ ]. Depan dan belakang = belum terdefinisi. Mula-mula kita ENQUEUE elemen A, diperoleh Queue S = [A].
S.depan = A. S.belakang = A.
Setelah itu kita ENQUEUE elemen B, diperoleh Queue S = [A, B].
S.depan = A. S.belakang = B.
Kemudian kita ENQUEUE kembali elemen C, diperoleh Queue S = [A, B, C].
S.depan = A. S.belakang = C.
Apabila kita lakukan DEQUEUE sekali, diperoleh Queue S = [B, C].
S.depan = B. S.belakang = C.
Kemudian kita ENQUEUE elemen D, diperoleh Queue S = [B, C, D].
S.depan = B. S.belakang = D.
Agar lebih jelas, perhatikan Gambar 5.1.
Gambar 5.1
C. Scenario
Kegiatan 1: Queue menggunakan Array
Pada kegiatan ini, digunakan contoh mahasiswa antri di loket, kita dapat membuat
Queue menggunakan Array sebagai berikut:
Step 1 : Buat struck mahasiswa. Mahasiswa dalam hal ini kita anggap memiliki nim dan nama.
struct Mahasiswa{
string nim;
string nama;
};
Step 2 : Buat struck Loket. Loket disini harus mempunyai Array yang menyimpan data antrian dengan tipe Mahasiswa). Selain menyimpan antrian mahasiswa, Loket juga menyimpan kapasitas maksimum panjang antrian yang dapat disimpan dan banyak mahasiswa yang sedang mengantri.
struct Loket{
Mahasiswa antrian[10];
int max;
int panjang;
};
Step 3 : Buat method untuk menginisialisasi antrian baru.
void newQueue(Loket &Q, int kapasitas){
Q.panjang = 0;
Q.max = kapasitas;
}
Step 4 : Buat method isFull. Method ini digunakan untuk mengecek apakah antrian dalam keadaan penuh atau tidak.
int isFull(Loket Q){
return ( Q.max <= Q.panjang);
}
Step 5 : Buat method isEmpty. Method ini digunakan untuk mengecek apakah antrian dalam keadaan kosong atau tidak.
int isEmpty(Loket Q){
return ( Q.panjang <= 0);
}
Step 6 : Buat method enqueue. Digunakan untuk memasukkan objek ke dalam antrian pada posisi paling antrian paling belakang (ke-panjang antrian)
Algoritma:
• Cek apakah antrian penuh
• Jika antrian belum penuh, masukkan objek pada antrian dengan indeks panjangAntrian
• Naikkan nilai panjangAntrian
void enqueue(Loket &Q, Mahasiswa M){
if(isFull(Q)){
cout<<"Antrian Penuh"<<endl;
} else{
Q.antrian[Q.panjang] = M;
Q.panjang++;
}
}
Step 7 : Buat method dequeue. Digunakan untuk mengambil objek paling depan dari sebuah antrian. Algoritma:
• Cek apakah stack dalam keadaan kosong atau tidak
• Jika tidak ambil objek pada indek 0 dari antrian
• Setiap objek di antrian, majukan satu indeks
• Kurangi nilai panjang antrian
Mahasiswa dequeue(Loket &Q){
if(isEmpty(Q)){
cout<<"Antrian Kosong"<<endl;
}else{
Mahasiswa out = Q.antrian[0];
for(int i=1; i<Q.panjang;i++){ Q.antrian[i-1] = Q.antrian[i];
}
Q.panjang--;
return out;
}
}
Step 8 : Buat method show. Digunakan untuk menampilkan semua data dari indeks ke-0 sampai indeks ke panjang.
void show(Loket Q){
for(int i=0; i<Q.panjang;i++){
cout<<Q.antrian[i].nim<<"\t"<<Q.antrian[i].nama<<endl;
}
}
Step 9 : Buat method main. Untuk method ini, buat sesuai kebutuhan. Misal, pada kasus ini untuk melakukan pengecekan saja. Dari method main ini, maka didapatkan output seperti pada Gambar 5.2.
int main(){
Loket A;
newQueue(A,5);
cout<<isFull(A)<<endl;
cout<<isEmpty(A)<<endl;
Mahasiswa B1;
B1.nim = “10”;
B1.nama = "Balok satu";
Mahasiswa B2;
B2.nim = “5”;
B2.nama = "Balok dua";
enqueue(A,B1);
enqueue(A,B2);
show(A);
dequeue(A);
show(A);
dequeue(A);
show(A);
dequeue(A);
show(A);
getch();
return 0;
}
Gambar 5.2
Kegiatan 2: Antrian menggunakan Array Melingkar
Kegiatan 3: Antrian menggunakan Pointer
Pada kegiatan ini, digunakan contoh mahasiswa antri di loket, kita dapat membuat Queue menggunakan pointer sebagai berikut:Step 1 : Buat struck mahasiswa. Mahasiswa dalam hal ini kita anggap memiliki nim dan nama.
struct Mahasiswa{
string nim;
string nama;
Mahasiswa *next;
};
Step 2 : Buat struck Loket. Loket disini harus mempunyai variabel pointer yang menyimpan depan dan belakang.
struct Loket{
Mahasiswa *depan;
Mahasiswa *belakang;
};
Step 3 : Buat method untuk menginisialisasi antrian baru.
void newQueue(Loket &Q){
Q.depan = NULL;
Q.belakang = NULL;
}
Step 4 : Buat method isEmpty. Method ini digunakan untuk mengecek apakah antrian dalam keadaan kosong atau tidak. Karena menggunakan pointer, maka queue dianggap kosong jika Q.depan menunjuk ke NULL. Method isFull tidak perlu dibuat karena jika menggunakan pointer, panjang stack bisa dinamis.
int isEmpty(Loket &Q){
return ( Q.depan == NULL);
}
Step 5 : Buat method enqueue. Digunakan untuk memasukkan objek ke dalam antrian pada posisi paling antrian paling belakang (ke-panjang antrian)
Algoritma:
• Cek apakah antrian kosong
• Jika antrian kosong, set objek baru sebagai data paling depan dan data paling belakang
• Jika antrian tidak kosong, set next dari data paling belakang menuju objek baru. Kemudian set objek baru sebagai data paling belakang
• Set next dari data paling belakang menjadi NULL
void enqueue(Loket &Q, Mahasiswa *&M){
if(isEmpty(Q)){
Q.depan = M;
Q.belakang = M;
}else{
Q.belakang->next = M;
Q.belakang = M;
}
Q.belakang->next = NULL;
}
Step 6 : Buat method dequeue. Digunakan untuk mengambil objek paling depan dari sebuah antrian. Algoritma:
• Cek apakah queue dalam keadaan kosong atau tidak
• Jika tidak ambil objek pada antrian paling depan
• Set data paling depan menjadi next dari Q.depan
Mahasiswa dequeue(Loket &Q){
if(isEmpty(Q)){
cout<<"Paku Kosong"<<endl;
}
else{
Mahasiswa *d = Q.depan;
Q.depan = Q.depan->next; return *d;}
}
Step 7 : Buat method show. Digunakan untuk menampilkan semua data dari indeks depan sampai indeks belakang.
void show(Loket Q){
Mahasiswa *p;
p=Q.depan;
while(p != NULL){
cout<<p->nim<<"\t"<<p->nama<<endl;
p=p->next;
}
}
Step 8 : Buat method main. Untuk method ini, buat sesuai kebutuhan. Misal, pada kasus ini untuk melakukan pengecekan saja. Dari method main ini, maka didapatkan output seperti pada Gambar 5.4.
int main(){
Loket A;
newQueue(A);
cout<<isEmpty(A)<<endl;
Mahasiswa *B1 = new Mahasiswa;
B1->nim = "10";
B1->nama = "Balok satu";
Mahasiswa *B2 = new Mahasiswa;
B2->nim = "12";
B2->nama = "Balok dua";
enqueue(A,B1);
enqueue(A,B2);
show(A);
dequeue(A);
show(A);
dequeue(A);
show(A);
dequeue(A);
show(A);
getch();
return 0;
}
