QUEUE / ANTRIAN

Pengertian Queue / Antrian

       Queue / Antrian adalah suatu kumpulan data yang mana penambahan elemen hanya bisa dilakukan pada satu ujung (disebut dengan sisi belakang atau tail/rear) dan penghapusan atau pengambilan elemen dilakukan lewat ujung lain (disebut dengan sisi depan atau head/front). Antrian menggunakan prinsip Pertama Masuk Pertama Keluar – First In First Out (FIFO). Dengan kata lain urutan masuk sama dengan urutan keluar. Antrian banyak dijumpai dalam kehidupan sehari-hari. Mobil-mobil yang mengantri digerbang tol untuk membeli karcis tol; orang-orang yang mengantri di loket untuk membeli karcis film juga membentuk antrian. Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya. DEQUEUE adalah mengeluarkan satu elemen dari suatu antrian. Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya sehingga membutuhkan variabel Head dan Tail.

Deklarasi queue dalam program
      Sebuah queue di dalam program komputer dideklarasikan sebagai sebuah tipe bentukan baru, di dalam bahasa c, biasa disebut struct. sebuah struktur data dari sebuah queue setidaknya 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 struktur data dari sebuah queue menggunakan bahasa c:
typedef struct
 {
  int HEAD, TAIL;
  int data[max+1];
 }Queue;

dimana, nilai MAX didefinisikan sebagai jumlah tumpukan maksimum yang dapat disimpan dalam queue. Setelah strukutr data dari queue didefinisikan dengan syntax di atas, maka setelah itu dapat dibuat variabel-variabel baru yang mengacu pada tipe data Queue di atas, misalkan membuat sebuah variabel bernama antrian yang bertipe Queue;

Queue antrian;
dalam tulisan ini, sebuah queue didefinisikan dengan array berukuran max + 1, maksudnya adalah agar elemen array ke-0 tidak digunakan untuk menyimpan data, melainkan hanya sebagai tempat "singgah‟ sementara untuk variabel head dan tail. sehingga, jika head dan tail berada pada elemen array ke-0, berarti queue tersebut dalam kondisi kosong (tidak ada data yang disimpan). berikut adalah ilustrasi dari sebuah queue kosong dengan ukuran nilai max = 6:

Operasi-operasi dasar dalam Queue:
Pada dasarnya, 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.

a. Prosedur createEmpty
    Sama pada stack, prosedur ini berfungsi untuk mengosongkan queue dengan cara meletakk HEAD dan TAIL pada indeks array ke-0. Berikut deklarasi prosedur createEmpty pada qu   dalam Bahasa C:

   void createEmpty()
    {
      antrian.HEAD = 0;
      antrian.TAIL = 0;
    }

b. Prosedur enqueue .

     Prosedur 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 setelah itu memasukkan data/ nilai ke dalam array pada  indeks ke-1 terlebih dahulu, baru 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

Berikut deklarasi prosedur  enqueue dalam Bahasa C:
 
   void enqueue(int x)
    {
      if ((antrian.HEAD == 0) && (antrian.TAIL == 0))
    {
      antrian.HEAD = 1;
      antrian.TAIL = 1;
    }
      else
    {
      antrian.TAIL = antrian.TAIL + 1;
    }
    antrian.data[antrian.TAIL] = x;
    }

   Pada deklarasi prosedur enqueue di atas, prosedur memiliki sebuah parameter formal yang  bernama „x‟ yang bertipe integer. Parameter formal „x‟ ini berguna untuk menerima kirima  nilai dari program utama (void main()) yakni berupa sebuah bilangan integer yang akan   dimasukkan  ke dalam queue. Gambar di bawah ini mengilustrasikan proses enqueue ke dalam  sebuah queue  yang  masih  kosong.

 

      Berikutnya, gambar di bawah ini akan mengilustrasikan proses enqueue  ke dalam sebuah queue yang telah berisi data (queue tidak kosong).

c. Prosedur dequeue

 Prosedur 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.

Berikut deklarasi prosedur pop dalam Bahasa C:
    void Dequeue()
     {
        if (q.head > q.tail)
      {
        q.head = 0;
        q.tail = 0;
      }
       q.head = q.head + 1;
     }
            

     Ketika posisi head sudah melewati posisi tail (head > tail), berarti sudah tidak ada lagi data/ nilai di  dalam queue tersebut, maka saat itu terjadi, head dan tail dikembalikan ke posisi ke-0

gambar di  bawah ini mengilustrasikan cara kerja prosedur 2 elemen (dequeue):
Ketika nilai terakhir (yakni nilai 3) dikeluarkan, maka posisi HEAD dan TAIL akan menjadi seperti ini:

 

Maka, ketika kondisi HEAD > TAIL terjadi seperti ilustrasi di atas, maka HEAD dan TAIL dikembalikan ke indeks array ke-0.

               enqueue 4 elemen 
2.enqueue 4 elemen
-tail = -1+1
          =0 enqueue (A)                        0        1        2        3                 5
                                                A
                                                head dan tail (0
B.enqueue 4 elemen
-tail = o+1
          =1 enqueue (B)                        0        1        2        3        4        5
                                                A       B
                                                head  tail


c.enqueue 4 elemen                           0        1        2        3        4        5
-tail = 1+1                               A       B       C
 d. Fungsi IsEmpty
     Sama 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). Berikut  deklarasi fungsi IsEmpty dalam Bahasa C:
     int IsEmpty()
   {
     if ((antrian.HEAD> antrian.TAIL) || (antrian.HEAD == 0) &&
        (antrian.TAIL == 0))
         return 1;
     else
        return 0;
   }

e. Fungsi IsFull
    Fungsi 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). Berikut deklarasi fungsi    IsFull dalam Bahasa C:
      int IsFull()
   {
     if (antrian.TAIL == max)
        return 1;
     else
        return 0;
   }

Studi Kasus:
      Bagaimana membangun data terstruktu dimana struktur menyerupai barisan dengan mengeluarkan data dimana data yang dikeluarkan adalah data pertama masuk pertama kali dan seterusnya?

Algoritma:

1.     Start

2.     memberi batasan pada barisan

3.      cek apakah barisan full?

4.      Jika iya, data tidak dapat dimasukkan

5.      Jika tidak, memasukkan data pada barisan (enqueue)

6.      Data pertama akan menjadi head sekaligus tail

7.     selanjutnya memasukkan data lagi pada barisan (enqueue)

8.     kembali menyimpan data pada index setelah       index dimana data tersimpan sebelumnya .

9.     sekarang head adalah data yang pertama dan tail  adalah data baru setelahnya.

10.                        ulangi langkah 7, 8 dan 9 sampai batasan dari  barisan.

11.                        untuk mengeluarkan data (dequeue).

12.                         cek apakah barisan kosong?

13.                        Jika iya, maka operasi pengambilan tidak  dilaksanakan.

14.                        Jika tidak, pengambilan di lakukan pada data yang      berada pada head dan max – 1.

15.                        Mengulang langkah 12, 13 dan 14 hingga barisan         kosong.

 End.