Selasa, 02 Juni 2015

Queue

Queue, atau lebih dikenal dengan dengan antrean adalah suatu kumpulan data yang seolah – olah terlihat seperti ada data yang diletakkan disebelah data yang lain. Apabila pada stack bersifat LIFO, maka pada antrean atau queue ini bersifat FIFO atau First In First Out, artinya data yang masuk duluan akan keluar terlebih dahulu juga.

Deklarasi Queue
Sebuah queue di dalam program komputer dideklarasikan sebagai sebuah tipe bentukan baru,biasa disebut struct. Sebuah struktur data dari suatu queue minimal harus mengandung dua tiga variabel,
yakni variabel HEAD yang akan berguna sebagai penanda bagian depan antrian, variabel TAIL yang akan berguna sebagai penanda bagian belakang antrian dan ARRAY DATA dari yang akan menyimpan data-data yang dimasukkan ke dalam queue tersebut.
Berikut adalah syntax untuk mendeklarasikan sebuah queue


#define max 7
typedef struct
{ 
  
   int data[max];
 int HEAD=-1, TAIL=-1; 
}Queue;
Queue antrian;


Operasi-operasi pada Queue
Operasi-operasi dasar pada queue mirip dengan operasi-operasi dasar pada stack. Perbedaannya hanya pada prosedur push dan pop saja. Pada queue, prosedur yang berfungsi untuk memasukkan data/ nilai ke dalam antrian adalah enqueue, sedangkan prosedur untuk mengeluarkan data/ nilai dari antrian adalah dequeue.
  1. Prosedur createEmptySama pada stack, prosedur ini berfungsi untuk mengosongkan queue dengan cara meletakkan HEAD dan TAIL pada indeks array ke-0.
  2. Prosedur enqueueProsedur ini digunakan untuk memasukkan sebuah data/ nilai ke dalam queue. Sebelum sebuah data/ nilai dimasukkan ke dalam queue, maka prosedur ini terlebih dahulu melakukan pengecekan terhadap posisi HEAD dan TAIL. Jika posisi HEAD dan TAIL masih berada pada indeks ke-0 (artinya queue masih kosong), maka prosedur ini akan menempatkan HEAD dan TAIL pada indeks ke-1 terlebih dahulu, baru setelah itu memasukkan data/ nilai ke dalam array data queue. Namun, jika posisi HEAD dan TAIL tidak berada pada posisi ke-0, maka posisi TAIL yang akan dinaikkan satu level. Jadi, pada proses enqueue, TAIL-lah  yang berjalan seiring masuknya data baru ke dalam antrian,  sedangkan  HEAD  akan  tetap  pada  posisi  ke-1.
  3. Prosedur dequeueProsedur ini digunakan untuk mengeluarkan atau membuang sebuah data/ nilai yang paling  awal  masuk  (yang  berada  pada  posisi  HEAD,  yakni  yang  paling  depan  dari antrian) ke dalam queue. Pekerjaan yang dilakukan oleh prosedur ini adalah menaikkan nilai HEAD satu level. Jadi, setiap satu kali data dikeluarkan, maka posisi HEAD naik bertambah satu level. Misalkan HEAD berada pada indeks ke-1, maka ketika akan mengeluarkan/ menghapus data pada posisi paling depan (pada posisi HEAD), prosedur ini akan menaikkan posisi HEAD ke indeks array ke-2.
  4. Fungsi IsEmptySama seperti fungsinya pada stack, fungsi ini berfungsi untuk melakukan pengecekan terhadap queue, apakah queue tersebut kosong atau tidak. Jika queue tersebut kosong (artinya, HEAD dan TAIL berada pada posisi 0, atau bisa juga ketika HEAD > TAIL), maka fungsi akan mengembalikan nilai 1 (true), tetapi jika queue tersebut tidak kosong/ berisi (artinya, HEAD dan TAIL tidak berada pada posisi 0), maka fungsi akan mengembalikan nilai 0 (false).
  5. Fungsi IsFullFungsi ini berfungsi untuk melakukan pengecekan terhadap queue, apakah queue tersebut penuh atau tidak. Jika queue tersebut penuh (artinya, TAIL berada pada posisi MAX), maka fungsi akan mengembalikan nilai 1 (true), tetapi jika queue tersebut tidak penuh (artinya, TAIL tidak berada pada posisi MAX), maka fungsi akan mengembalikan nilai 0 (false).
 Contoh Program Queue:

#include
#include
#include
#define MAX 8

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;
  printf("%d sudah dimasukan",antrian.data[antrian.tail]);
 } else if(IsFull()==0){
  antrian.tail++;
  antrian.data[antrian.tail]=data;
  printf("%d sudah dimasukan",antrian.data[antrian.tail]);
 }
}

int Dequeue()
{
 int i;
 int e = antrian.data[antrian.head];
 for(i=antrian.head; i<=antrian.tail-1;i++){
  antrian.data[i]=antrian.data[i+1];
 }
 antrian.tail--;
 return e;
}

void Clear()
{
 antrian.head=antrian.tail=-1;
 printf("CLEAR");
}

void Tampil()
{
 if(IsEmpty()==0){
  for(int i=antrian.head;i<=antrian.tail;i++){
   printf(" %d",antrian.data[i]);
  }
 }else printf("data kosong!\n");
}

main()
{
 int pil;
 int data;
 Create();
 do{
  clrscr();

  cout<<"=============================="<  cout<<"\tProgram Queue"<  cout<<"==============================\n"<  cout<<"1. Enqueue "<  cout<<"2. Dequeue "<  cout<<"3. Tampil "<  cout<<"4. Clear "<  cout<<"5. Exit\n "<      cout<<"==============================\n"<  cout<<" Masukan Pilihan : ";cin>>pil;
  switch(pil){

  case 1: clrscr();
  cout<<"Masukan Data : ";cin>>data;
  Enqueue(data);
  break;

  case 2: clrscr();
  Dequeue();
  break;

  case 3: clrscr();
  Tampil();
  break;

  case 4: clrscr();
  Clear();
  break;
  case 5:
  cout<  break;



 }

 getch();
 }while(pil!=5);
 return 0;
}
 Referensi: 
  1. Fachrie, Muhammad.2012.Stack And Queue.Yogyakarta.Stimik Amikom

Tidak ada komentar:

Posting Komentar