Thursday, February 24, 2011
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 diujung 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
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 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 diujung 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
- 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
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
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!!";
}
}
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;
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);
}
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
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!!";
}
}
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;
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);
}
