Queue - Materi

Dasar Teori
Antrian (Queue) dapat diartikan sebagai suatu kumpulan data yang seolah-olah
terlihat seperti ada data yang diletakkan di sebelah data yang lain seperti pada gambar 01.
Pada gambar, data masuk melalui lorong di sebelah kanan dan masuk dari terowongan
sebelah kiri. Hal ini membuat antrian bersifat FIFO (First In First Out), beda dengan
stack yang berciri LIFO.

 

 

Antrian dapat dibuat baik dengan array maupun dengan struct. Pada pembuatan
antrian dengan array, antrian yang disajikan bersifat statis. Ini disebabkan oleh jumlah
maksimal array sudah ditentukan sejak deklarasi awal

QUEUE DENGAN LINIEAR ARRAY
- Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di
ujung Satunya
- Sehingga membutuhkan variabel Head dan Tail

 

Create()
• Untuk menciptakan dan menginisialisasi Queue
• Dengan cara membuat Head dan Tail = -1

IsEmpty()
• Untuk memeriksa apakah Antrian sudah penuh atau belum
• Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
• Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala
antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah
• Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian
kebelakang, yaitu menggunakan nilai Tail

 

 

 

IsFull()
• Untuk mengecek apakah Antrian sudah penuh atau belum
• Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1
adalah batas elemen array pada C) berarti sudah penuh

 

 

Enqueue(data)
• Untuk menambahkan elemen ke dalam Antrian, penambahan elemen
selalu ditambahkan di elemen paling belakang
• Penambahan elemen selalu menggerakan variabel Tail dengan cara
increment counter Tail

Dequeue()
• Digunakan untuk menghapus elemen terdepan/pertama dari Antrian
• Dengan cara mengurangi counter Tail dan menggeser semua elemen
antrian kedepan.
• Penggeseran dilakukan dengan menggunakan looping

 

 

 

 Clear()
• Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan
Head = -1
• Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus
arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1
sehingga elemenelemen Antrian tidak lagi terbaca

 

 

 

Print()
• Untuk menampilkan nilai-nilai elemen Antrian
• Menggunakan looping dari head s/d tail
Perbedaan antara stack dan queue terdapat pada aturan penambahan dan
penghapusan elemen. Pada stack, operasi penambahan dan penghapusan elemen
dilakukan di satu ujung. Elemen yang terakhir kali dimasukkan akan berada paling dekat
dengan ujung atau dianggap paling atas sehingga pada operasi penghapusan, elemen
teratas tersebut akan dihapus paling awal, sifat demikian dikenal dengan LIFO. Pada
queue, operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu
dilakukan melalui salah satu ujung, menempati posisi di belakang elemen-elemen yang
sudah masuk sebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan
elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling
awal atau elemen terdepan. Sifat yang demikian dikenal dengan FIFO.

contoh program :

 

#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#define MAX 10
28
typedef struct
{
int data[MAX];
int head;
int tail;
} Queue;
Queue antrian;
void Create()
{
antrian.head=antrian.tail=-1;
}
int IsEmpty()
{
if(antrian.tail==-1)
return 1;
else
return 0;
}
int IsFull()
{
if(antrian.tail==MAX-1) return 1;
else return 0;
}
void Enqueue(int data)
{
if(IsEmpty()==1)
{
antrian.head=antrian.tail=0;
antrian.data[antrian.tail]=data;
cout<<"Data "<<antrian.data[antrian.tail]<<"
Masuk!!";
}
else if(IsFull()==0)
{
antrian.tail++;
antrian.data[antrian.tail]=data;
cout<<"Data "<<antrian.data[antrian.tail]<<"
Masuk!!";
}
else if (IsFull() == 1)
{
cout<<"Ruangan Penuh!!"<<endl;
cout<<data<<" Ga Bisa Masuk!!";
}
}
29
void Dequeue()
{
int i;
int e = antrian.data[antrian.head];
if (antrian.tail == -1)
{
cout<<"Ga Ada Antrian... Data Kosong"<<endl;
}
else
{
for(i=antrian.head;i<=antrian.tail-1;i++)
{
antrian.data[i] = antrian.data[i+1];
}
antrian.tail--;
cout<<"Data yang Keluar lebih dulu = "<<e<<endl;
}
}
void Clear()
{
antrian.head=antrian.tail=-1;
cout<<"Duh Lega, Ruangan Jadi Ga Sumpek...."<<endl;
cout<<"Data Clear...";
}
void Tampil()
{
if(IsEmpty()==0)
{
cout<<"Data Dalam Antrian"<<endl;
cout<<"==========================="<<endl;
cout<<endl;
for(int i=antrian.head;i<=antrian.tail;i++)
{
cout<<"| "<<antrian.data[i]<<" |";
}
}
else cout<<"Ga Ada Antrian... Data Kosong";
}
void main()
{
int pil;
int data;
Create();
do
{
clrscr();
cout<<"Implementasi Antrian dengan Struct"<<endl;
cout<<"=================================="<<endl;
cout<<endl;
30
cout<<"1. Enqueue(Push)"<<endl;
cout<<"2. Dequeue(PoP)"<<endl;
cout<<"3. Print"<<endl;
cout<<"4. Clear"<<endl;
cout<<"5. Exit"<<endl;
cout<<"Pilihan Anda= "; cin>>pil;
switch(pil)
{
case 1:
{
cout<<endl;
cout<<"Data = "; cin>>data;
Enqueue(data);
break;
}
case 2:
{
cout<<endl;
Dequeue();
break;
}
case 3:
{
cout<<endl;
Tampil();
break;
}
case 4:
{
cout<<endl;
Clear();
break;
}
}
getch();
} while(pil!=5);
}