Kamis, 03 Maret 2011

QUEUE (ANTRIAN)

Queue (Antrian) adalah suatu kumpulan data yang penambahan elemennya
hanya bisa dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear),
dan penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain
(disebut dengan sisi depan atau front)
Jika pada tumpukan dikenal dengan menggunakan prinsip LIFO (Last In First
Out), maka pada antrian prinsip yang digunakan adalah FIFO (First In First Out).
IMPLEMENTASI ANTRIAN DENGAN ARRAY
Karena antrian merupakan suatu kumpulan data, maka tipe data yang sesuai
untuk menyajikan antrian adalah menggunakan array atau list (senarai
berantai).
depan
keluar A B C D E F masuk
belakang
Antrian tersebut berisi 6 elemen, yaitu A, B, C, D, E, dan F. Elemen A terletak
dibagian depan antrian dan elemen F terletak di bagian belakang antrian.
Jika terdapat elemen baru yang akan masuk, maka elemen tersebut akan
diletakkan disebelah kanan F.
Jika ada elemen yang akan dihapus, maka A akan dihapus terlebih dahulu.
depan
keluar A B C D E F G H masuk
belakang
Antrian dengan penambahan elemen baru, yaitu G dan H.
depan
keluar C D E F G H masuk
belakang
Antrian dengan penghapusan elemen antrian, yaitu A dan B.
Modul 8 Struktur Data (Arie) - 2
Seperti dalam tumpukan atau stack, maka di dalam antrian juga dikenal dua
operasi dasar yaitu menambah elemen baru yang akan diletakkan di bagian
belakang antrian dan menghapus elemen yang terletak di bagian depan antrian.
Selain itu juga harus dilihat kondisi antrian mempunyai isi atau masih kosong.
Contoh :
#define MAXN 6
typedef enum {NOT_OK, OK} Tboolean;
typedef struct {
Titem array[MAXN];
int first;
int last;
int number_of_items;
} Tqueue;
Elemen antrian dinyatakan dalam tipe integer yang semuanya terdapat dalam
struktur. Variabel first menunjukkan posisi elemen pertama dalam array, dan
variabel last menunjukkan posisi elemen terakhir dalam array.
Untuk menambah elemen baru dan mengambil elemen dari antrian diperlukan
deklarasi.
Contoh :
void initialize_queue (Tqueue *Pqueue) {
Pqueue->first=0;
Pqueue->last=-1;
Pqueue->number_of_items=0;
}
Tboolean enqueue (Tqueue *Pqueue, Titem item) {
if (Pqueue->number_of_items >= MAXN)
return (NOT_OK);
else {
Pqueue->last++;
if (Pqueue->last > MAXN – 1)
Pqueue->last=0;
Pqueue->array[Pqueue->last]=item;
Pqueue->number_of_items++;
return (OK);
}
}
Tboolean dequeue (Tqueue *Pqueue, Titem *Pitem) {
if (Pqueue->number_of_items==0)
return (NOT_OK);
else {
*Pitem=Pqueue->array[Pqueue->first++];
if (Pqueue->first > MAXN – 1)
Pqueue->first=0;
Pqueue->number_of_items--;
return (OK);
}
}
Modul 8 Struktur Data (Arie) - 3
Kondisi awal sebuah antrian dapat digambarkan sebagai berikut.
Antrian
6
5
4
3
2
1 first = 1
last = 0
Pada kondisi awal ini antrian terdiri dari last dibuat = 0 dan first dibuat = 1.
Antrian dikatakan kosong jika last < first. Banyaknya elemen yang terdapat
dalam antrian dinyatakan sebagai last – first + 1.
Antrian
6
5
4 D last = 4
3 C
2 B
1 A first = 1
Dengan MAXN = 6 antrian telah terisi empat buah data yaitu A, B, C, dan D.
Kondisi first = 1 dan last = 4.
Antrian
6
5
4 D last = 4
3 C first = 3
2
1
Pada antrian dilakukan penghapusan dua buah data yaitu A dan B. Sehingga
kondisi first = 3 dan last = 4.
Antrian
6 F last = 6
5 E
4 D
3 C first = 3
2
1
Pada antrian dilakukan penambahan dua buah data yaitu E dan F. Elemen E
akan diletakkan setelah D dan elemen F akan diletakkan setelah E. Sehingga
kondisi first = 3 dan last = 6.
Dapat diperoleh jumlah elemen yaitu 6 – 3 + 1 = 4. Dengan pembatasan data
maksimal 6 elemen akan terdapat sisa 2 elemen. Jika pada antrian akan
ditambahkan elemen yang baru, misal G, elemen G akan diletakkan setelah
elemen F. Hal ini akan menyebabkan elemen yang baru tersebut tidak dapat
masuk (MAXN = 6), meskipun masih tersisa 2 buah elemen yang kosong.
Modul 8 Struktur Data (Arie) - 4
IMPLEMENTASI ANTRIAN DENGAN POINTER
Pada prinsipnya, antrian dengan pointer akan sama dengan antrian yang
menggunakan array. Penambahan akan selalu dilakukan di belakang antrian dan
penghapusan akan selalu dilakukan pada elemen dengan posisi paling depan.
Antrian sebenarnya merupakan bentuk khusus dari suatu senarai berantai
(linked list).
Pada antrian bisa digunakan dua variabel yang menyimpan posisi elemen paling
depan dan elemen paling belakang. Jika menggunakan senarai berantai maka
dengan dua pointer yang menunjuk elemen kepala (paling depan) dan elemen
ekor (paling belakang) dapat dibentuk antrian.
Contoh :
struct queueNode {
char data;
struct queueNode * nextPtr;
};
typedef struct queueNode QUEUENODE;
typedef QUEUENODE *QUEUENODEPTR;
QUEUENODEPTR headPtr = NULL, tailPtr = NULL;
Contoh :
Untuk menambah elemen baru yang selalu diletakkan di belakang senarai.
void enqueue (QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr, char
value) {
QUEUENODEPTR newPtr = malloc (sizeof(QUEUENODE));
if (newPtr != NULL) {
newPtr->data=value;
newPtr->nextPtr=NULL;
if (isEmpty(*headPtr))
*headPtr=newPtr;
else
(*tailPtr)->nextPtr=newPtr;
*tailPtr=newPtr;
}
else
printf(“%c not inserted. No memory available. \n”, value);
}
Contoh :
Untuk menghapus akan dilakukan pemeriksaan terlebih dahulu antrian dalam
keadaan kosong atau tidak.
int isEmpty (QUEUENODEPTR headPtr) {
return headPtr==NULL;
}
Modul 8 Struktur Data (Arie) - 5
CONTOH SOAL :
Soal 1
Buatlah program dalam bentuk menu untuk mengimplementasikan antrian.
Menu tersebut berisi memasukkan data, menghapus data, menampilkan data,
dan keluar
//Program : queue1
# include
# include
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;
}
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;
Modul 8 Struktur Data (Arie) - 6
rear=entry;
}
cout<<"\n\n\t *** "<cout<<"\n\n\n\t\t Pres any key to return to Menu. ";
getch( );
}
void Linked_list_Queue::Delete( )
{
if(front==NULL)
cout<<"\n\n\n\t *** Error : Queue is empty. \n"<else
{
int deleted_element=front->data;
node *temp;
temp=front;
front=front->next;
delete temp;
cout<<"\n\n\n\t *** "<}
cout<<"\n\n\n\t\t Pres any key to return to Menu. ";
getch( );
}
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"<else
cout<<"\n\n\n\n\n\t *** Tidak ada yang ditampilkan. "<while(print!=NULL)
{
cout<<"\t "<data<print=print->next;
}
cout<<"\n\n\n\t\t Pres any key to return to Menu. ";
getch( );
}
void Linked_list_Queue ::show_working( )
{
char Key=NULL;
do
{
clrscr( );
gotoxy(5,5);
gotoxy(10,8);
cout<<"Pilih salah satu menu :"<gotoxy(15,10);
cout<<"- Press \'I\' to Masukkan data dalam Queue"<gotoxy(15,12);
cout<<"- Press \'D\' to Hapus data dari Queue"<gotoxy(15,14);
cout<<"- Press \'P\' to Tampilkan data dari Queue"<gotoxy(15,16);
Modul 8 Struktur Data (Arie) - 7
cout<<"- Press \'E\' to Exit"<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=='p' || Key=='P')
print_list( );
else
goto Input;
}
while(1);
}
int main( )
{
Linked_list_Queue obj;
obj.show_working( );
return 0;
}
SOAL LATIHAN :
Buatlah program untuk memasukkan dan mengeluarkan data dalam antrian.
Contoh ada di file : queue2.exe
Save dengan nama file : qu1_nim (4 digit nim terakhir)

Tidak ada komentar:

Posting Komentar