QUEUE ( ANTREAN ) dalam C++

1. PENGERTIAN QUEUE (ANTREAN)

Queue adalah suatu bentuk khusus dari linear list, dengan operasi penyisipan (insertion) hanya diperbolehkan pada salah satu sisi, yang disebut sisi belakang (REAR), dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi lainnya, yang disebut sisi depan (FRONT), dari list. Sebagai contoh dapat kita lihat antrean (Q1, Q2,...,QN). Kita notasikan bagian depan dari antrean Q sebagai FRONT(Q) dan bagian belakang sebagai REAR(Q). Jadi untuk antrean Q = [Q1, Q2, …, QN] : FRONT(Q) = Q1 dan REAR(Q) = QN

Kita menggunakan notasi NOEL(Q) untuk menyatakan jumlah elemen di dalam antrean Q. NOEL(Q) mempunyai harga integer. Untuk antrean Q = [Q1,Q2,…, QN], maka NOEL(Q) = N. Operator penyisipan (insertion) disebut INSERT dan operator penghapusan (deletion) disebut REMOVE.

2. OPERASI DASAR PADA ANTREAN

Ada 4 operasi dasar yang dapat dilakukan pada struktur data antrean, yakni :

1. CREATE (antrean) :

CREATE(Q) adalah suatu operator untuk membentuk dan menunjukkan suatu antrean hampa Q.
Berarti :
NOEL(CREATE(Q)) = 0
FRONT(CREATE(Q)) = tidak terdefinisi
REAR(CREATE(Q)) = tidak terdefinisi

2. ISEMPTY (antrean)


ISEMPTY(Q) adalah operator yang menentukan apakah antrean Q hampa atau tidak. Operand dari operator ini merupakan antrean, sedangkan hasilnya merupakan tipe data boolean.
Di sini :
ISEMPTY(antrean) = true, jika Q hampa, yakni jika NOEL(Q)=0 = false, dalam hal lain. Maka, ISEMPTY(CREATE(Q)) = true.

3. INSERT (elemen, antrean)

INSERT(E,Q) adalah operator yang memasukkan elemen E ke dalam antrean Q. Elemen E ditempatkan di bagian belakang dari antrean. Hasil dari operasi ini adalah antrean yang lebih panjang.
REAR(INSERT(E,Q)) = E
QNOEL adalah E
ISEMPTY(INSERT(E,Q)) = false


4. REMOVE (antrean)

REMOVE(Q) adalah operator yang menghapus elemen bagian depan dari Antrean Q. Hasilnya merupakan antrean yang lebih pendek. Pada setiap operasi ini, harga dari NOEL(Q) berkurang satu, dan elemen kedua dari Q menjadi elemen terdepan. Jika NOEL(Q) = 0, maka REMOVE(Q) memberikan suatu kondisi error, yakni suatu underflow. Jelas bahwa REMOVE(CREATE(Q)) juga memberikan kondisi underflow
error.

Contoh Program :

#include <iostream.h>
#include <conio.h>

class Linked_list_Queue
{
private:
struct node
{
int data;

node *next;
};

node *rear;
node *entry;
node *print;
node *front;

public:
Linked_list_Queue();

void Delete();
void insert();
void print_list();
void show_working();
};

Linked_list_Queue::Linked_list_Queue()
{
rear=NULL;
front=NULL;
}
//***********************************************
//-------------- Insert() ---------------------
//***********************************************

void Linked_list_Queue::insert()
{
int num;
cout<<"\n\n\n\n\n\t Masukkan angka dalam Queue : ";
cin>>num;

entry=new node;
if (rear==NULL)
{
entry->data=num;
entry->next=NULL;
rear=entry;
front=rear;
}
else
{
entry->data=num;
entry->next=NULL;
rear->next=entry;
rear=entry;
}
cout<<"\n\n\t *** "<<num<<" sudah masuk dalam Queue."<<endl;
cout<<"\n\n\n\t\t Pres any key to return Menu. ";
getch();
}

//***********************************************//
//-------------- Delete() --------------------- //
//***********************************************//

void Linked_list_Queue::Delete()
{
if (front==NULL)
cout<<"\n\n\n\t *** Error : Queue is empty. \n"<<endl;
else
{
int deleted_element=front->data;
node *temp;
temp=front;
front=front->next;
delete temp;

cout<<"\n\n\n\t*** "<<deleted_element<<" dihapus dari Queue."<<endl;
}
cout<<"\n\n\n\t\t Pres any key to return Menu.";
getch();
}

//***********************************************
//-------------- print_list() ---------------------
//***********************************************

void Linked_list_Queue::print_list()
{
print=front;
if(print!=NULL)
cout<<"\n\n\n\n\n\t Angka - angka yang ada dalam queue adalah : \n"<<endl;
else
cout<<"\n\n\n\n\n\t *** Tidak ada yang ditampilkan."<<endl;
while(print!=NULL)
{
cout<<"\t"<<print->data<<endl;
print=print->next;
}
cout<<"\n\n\n\t\t Pres any key to return Menu.";
getch();
}

//***********************************************
//-------------- show_working() ---------------------
//***********************************************

void Linked_list_Queue::show_working()
{
char Key=NULL;
do
{
clrscr();

gotoxy(5,5);
cout<<"****Implementation of Linked List as a Queue****"<<endl;

gotoxy(10,8);
cout<<"Pilih salah satu menu : "<<endl;

gotoxy(15,10);
cout<<"-Press\'I\' to Masukkan data dalam queue"<<endl;

gotoxy(15,12);
cout<<"-Press\'D\' to Hapus data dari queue"<<endl;

gotoxy(15,14);
cout<<"-Press\'T\' to Tampilkan data dari queue"<<endl;

gotoxy(15,16);
cout<<"-Press\'E\' to Exit"<<endl;

input:

gotoxy(10,20);
cout<<" ";

gotoxy(10,20);
cout<<"Masukkan pilihan : ";

Key=getche();
if (int(Key)==27 || Key=='e' || Key=='E')
break;

else if(Key=='i' || Key=='I')
insert();

else if (Key=='d' || Key=='D')
Delete();

else if (Key=='t' || Key=='T')
print_list();

else
goto input;
}
while(1);
}

//********************************************
//--------------- main() --------------------
//********************************************

int main()
{

Linked_list_Queue obj;
obj.show_working();
return 0;
}