Antrian / Queue Pemograman C/C++ (Struktur Data - Modul 9)

No Comments

Antrian / Queue

Kaidah utama dalam konsep queue adalah FIFO yang merupakan singkatan dari First In First Out, artinya adalah data yang pertama kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan. Analoginya sama dengan antrian di sebuah loket pembelian tiket kereta, orang yang datang lebih dahulu, maka akan dilayani terlbih dahulu, dan akan selesai lebih dulu dari orang-orang yang datang setelahnya. Gambar di bawah ini mengilustrasikan kerja sebuah queue:

Dalam queue sendiri terdapat beberapa operasi , yaitu :
  1. IsEmpty : Mengecek apakah queue kosong atau tidak
  2. IsFull : Mengecek apakah queue sudah penuh atau belum
  3. Enqueue : Menambahkan data di queue
  4. Dequeue : Mengambil data dari queue
  5. Clear : Menghapus data dalam antrian
  6. View : melihat data dalam antrian
Berbeda dengan stack, queue mempunyai 2 kata kunci, yaitu tail dan head.  Fungsi nya buat apa? Head adalah penanda urutan paling depan, sedangkan tail adalah penanda urutan paling belakang.  Karena jumlah operasinya banyak, kita kerjakan secara modular aja ya biar lebih mudah.

Deklarasi Awal Queue
Variabel yang akan digunakan adalah data (array sebagai tempat queue), head, tail.  Sama seperti Stack, Nilai dari head dan tail dimulai dari -1 yang menandakan queue kosong.  Sebagai contoh kita akan membuat queue dengan data maksimal sebanyak 7 data.

Deklarasi awal variabel yang akan digunakan dalam queue



#define max 7
int data[max];
int head=-1, tail=-1;

IsEmpty
Sama seperti di Stack, IsEmpty berguna untuk mengecek apakah queue kosong atau tidak.  Indikator bahwa queue kosong adalah nilai dari head dan tail bernilai -1.  Sehingga kita tinggal buat fungsi nya sebagai berikut :






bool IsEmpty(){
   if(head == -1 && tail == -1)
       return true;
   else
       return false;
}
IsFull
Operasi IsFull digunakan untuk mengecek apakah queue sudah penuh atau belum.  Indikator kalau queue penuh adalah nilai tail = max – 1.  Mengapa? karena nilai maksimal pada array yang mempunyai index 7 pada saat diakses akan mempunyai nilai maksimal 6.  Sehingga fungsi yang terbentuk seperti ini :







</pre>
<pre style="text-align: justify;">bool IsFull(){
   if(tail == max-1)
       return true;
   else
       return false;
}
Enqueue
Enqueue digunakan untuk memasukkan data kedalam queue.  Sama seperti push dalam stack.  Sebelum memasukkan data kedalam antrian, kita harus mengecek terlebih dahulu apakah queue / antrian sudah penuh atau belum.  Kalau belum maka kita harus mengecek apakah head sudah berada pada nilai 0 atau belum.  Ini sangat penting karena nilai head tidak akan lebih dari 0.  PERLU DIPERHATIKAN !  Yang akan bergerak terus adalah tail, sedangkan head hanya penunjuk urutan paling depan, sehingga nilainya tidak pernah lebih dari 0.  Kecuali antrian kosong, maka posisi head dan tail akan kembali menjadi -1.

Saat memasukkan data pertama kali, maka nilai head dan tail berubah menjadi 0. Tetapi saat data yang dimasukkan sudah lebih dari 1 kali, maka yang akan terus berubah adalah tail, sedangkan nilai head tetap.












void Enqueue(){
   if(IsFull()) {
       cout<<"Antrian sudah penuh, mohon tunggu beberapa saat lagi ";
       getch();
   } else {
       if (IsEmpty()){
           head=tail=0;
           cout<<"Masukkan data : ";cin>>data[tail];
       } else {
           tail++;
           cout<<"Masukkan data : ";cin>>data[tail];
       }
   }
}
Dequeue
Kebalikan dari fungsi enqueue, dequeue digunakan untuk mengambil data yang sudah masuk di urutan pertama.  Sehingga kita tinggal membaca data yang ada di posisi head.  Nah inilah fungsi dari head.  Jangan lupa kita cek dulu apakah queue kosong atau tidak.  Tapi jika ada isinya, setelah data diambil, data dibelakangnya digeser ke depan.











void Dequeue(){
      if(IsEmpty()){
          cout<<"Antrian kosong ! ";
          getch();
      } else {
      cout<<"Data yang diambil : "<<data[head];
      for(a=head;a<=tail-1;a++)
          data[a]=data[a+1];
      tail--;
      if(tail == -1)
head = -1;
      }
}

Clear
Operasi clear digunakan untuk menghapus data yang ada di dalam queue.  Caranya cukup merubah nilai pada head dan tail menjadi -1.  Tidak perlu diperhatikan data yang ada di dalam array.  Nantinya data data tersebut juga akan ditimpa.




void Clear(){
     head=tail=-1;
     cout<<"Antrian sudah dikosongkan ! ";getch();
}

View
Operasi ini digunakan untuk melihat data yang ada didalam queue.  Caranya adalah dengan membaca data pada index yang terdapat diantara head sampai tail








void View(){
     if(IsEmpty()){
         cout<<"Antrian kosong ! ";
         getch();
     } else {
         for(a=head;a<=tail;a++)
              cout<<"Data pada antrian ke "<<a<<" = "<<data[a]<<endl;
         getch();
     }
}

0 komentar:

Posting Komentar