Queue (Antrian)_Struktur Data

A. Pengertian QUEUE
queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehiduypan sehari-hari, misalnya saat Anda mengantri di loket untuk membeli tiket. Istilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah enqueue. Dalam suatu antrian, yang dating terlebih dahulu akan dilayani lebih dahulu.
B. Operasi - Operasi Pada QUEUE
operasi-operasi sebagai berikut :
1. EnQueue Memasukkan data ke dalam antrian
2. DeQueue Mengeluarkan data terdepan dari antrian
3. Clear Menghapus seluruh antrian
4. IsEmpty Memeriksa apakah antrian kosong 
5. IsFull Memeriksa apakah antrian penuh
C. Penerapan Dalam Kehidupan Sehari- Hari
Queue atau antrian adalah sebuah kumpulan benda di mana hanya benda yang terakhir dimasukkan yang dapat diakses. Queue atau Antrian merupakan perintah pengumpulan data yang disebut “first-in, first-out”. Aplikasi ini meliputi jadwal pekerjaan dalam sebuah operasi
Misalnya:
a. Antrian printer job pada sebuah jaringan
b. Antrian nasabah pada sebuah bank
c. Antrian loket bioskop, dll

GAMBAR QUEUE & PENGOPERASIANNYA

        Untuk menggambarkan suatu queue dapat dilakukan beberapa cara , yaitu :

        Misal : diberikan Queue Q = [A, B, C, D, E, F], maka Queue Q dapat digambarkan sebagai berikut :

    

	A	B	C	D	E	F
	FRONT					REAR

	F	E	D	C	B	A
	REAR					FRONT

atau dapat pula digambarkan dengan posisi tegak.

PRINSIP KERJA QUEUE

Prinsip kerja Queue adalah FIFO (First In First Out), di mana data yang masuk terlebih dahulu akan keluar pertama.

Operasi-Operasi Queue dengan Linear Array

• IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. hal ini dilakukan dengan mengecek apakah tail bernilai -1 atau tidak. Nilai -1 menandakan bahwa queue masih kosong.

• IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bias menampung data dengan cara mengecek apakah nilai tail sudah sama dengan jumlah maksimal queue. Jika nilai keduanya sama, berarti queue sudah penuh.

• EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen dalam queue.

• DeQueue

Fungsi DeQueue berguna untuk mengambil sebuah elemen dari queue. Operasi ini sering disebut juga serve. Hal ini dilakukan dengan cara memindahkan sejauh satu langkah ke posisi di depannya sehingga otomatis elemen yang paling depan akan tertimpa dengan elemen yang terletak di belakangnya.

• Clear

Fungsi Clear berguna untuk menghapus semua lemen dalam queue dengan jalan mengeluarkan semua elemen tersebut satu per satu hingga queue kosong dengan memanfaatkan fungsi DEQueue.

* Hal ini membuat antrian Pertama-In-First-Out (FIFO) struktur data . Dalam struktur data FIFO, elemen pertama ditambahkan ke antrian akan menjadi yang pertama untuk dihapus. Hal ini setara dengan persyaratan bahwa setelah unsur ditambahkan, semua elemen yang ditambahkan sebelum harus dihapus sebelum elemen baru dapat dipanggil. Antrian Sebuah contoh dari struktur data linear .
Antrian menyediakan layanan dalam ilmu komputer , transportasi , dan riset operasi di mana berbagai entitas seperti data, objek, orang, atau peristiwa yang disimpan dan diadakan untuk diproses kemudian. Dalam konteks ini, antrian melakukan fungsi sebuah penyangga .
Antrian yang umum dalam program komputer, di mana mereka diimplementasikan sebagai struktur data ditambah dengan rutinitas akses, sebagai struktur data abstrak atau dalam bahasa berorientasi objek seperti kelas. Implementasi yang umum adalah buffer lingkaran dan daftar link  

Sebuah Queue bertipe t adalah sebuah barisan berhingga atas elemen-elemen bertipe T, bersama-sama dengan operasi berikut:

1.    Inisialisasi Queue menjadi kosong.

2.    Mencari tahu status Queue kosong atau tidak

3.    Mencari tahu status Queue peenuh atau tidak

4.    Mencari panjang Queue (jumlah elemen Queue)

5.    Jika Queue tidak pennuh, memesukan elemen baru sesudah elemen paling belakang.

6.    Mengambil nilai dari elemen Queue terdepan bila Queue tidak kosong.

7.    Menghapus elemen terdepan bila Queue tidak kosong.

Queue adalah kumpulan objek data yang tipenya sama, tersusun sebagai sebuah barisan linier dengan operasi menambahkan elemen selalu dilakukan di salah satu ujung barisan, dan operasi menghapus elemen dilakukan di ujung lainya. Queue merupakan bentuk khusus dari lish, yaitu lis linier sifat “masuk awal, keluar awal’ (FIFO list : First In First Out).

Karena sifat keluar masuknya elemen queue melalui kedua ujung queue, maka elemen-elemen pada kedua ujung barisan tersebut perlu diidentifikasikan. Elemen yang pertama kali masuk antrian disebut elemen depan (front/head of queue), sedangkan elemen yang terakhir kali masuk disebut elemen belakang (read/tail queue). Gambar berikut menunjukan model penyajian antrian dengan list linear.

Berikut ini operasi-operasi stadar pada queue:

1.    Instalasi, merupakan procedure untuk membuat queue pada kondisi awal, yaitu queue yang masih kosong (belum mempunyai elemen).

2.    Inqueue, Insert Queue merupakan procedure untuk mamasukan sebuah elemen baru pada queue. Jumlah elemen queue akan bertambah satu dan elemen tersebut merupakan elemen belakang.

3.    Dequeue, Delete Queue merupakan prosedur untuk menghapus/mengambil sebuah elemen dari queue. Elemen yang diambil adalah elemen depan dan jumlah elemen queue akan berkurang satu.

Hal lain yang perlu diperhatikan dalam suatu struktur dinamis adalah jumlah elemen struktur data tersebut.operasi-operasi yang berhubungan dengan jumlah elemen suatu queue adalah:

1.    Size, yaitu operasi untuk mendapatkan banyaknya elemen Queue.

2.    Empty, yaitu prosedur untuk mengetahui apakah Queue dalam keadaan kosong atau tidak.dengan status ini maka dapat dicegah dilakukannya operasi DeQueue dari suatu queueu yang kosong.

3.    Full, merupakan prosedur untuk mengetahiu apakah queue penuh atau tidak. Prosedur ini hanya berlaku untuk queue yang jumlahnya terbatas.

Untuk mengimplementasikan queue dengan array dapat dipakai berbagai model. Sebagai gambaran modelyang dapat digunakan antara lain :

1.    Model fisik,sebuah array linier, dengan elemen depan dari queue selalu ditempatkan pada pertama dari elemen dari array dan seluruh elemen queue digser satu posisi kedepan setiap kali elemen depan dari queue diambil/dihapus.

2.    Sebuah array linier dengan indeks depan dan belakang selalu bergeser kea rah posisi terakhir dari array.

3.    Sebuah array melingkar dengan indeks depan dan belakang, serta sebuah posisi yang dibiarkan kosong.

4.    Sebuah array melingkar dengan indeks depan dan belakang, serta sebuah variable Boolean untuk menunjukan statuskosong/pemuh dari queue.

5.    Sebuah array melingjar dengan indeks depan dan belakang. Serta sebuah variabelintegerbuntuk counter yang menunjukan banyaknya dari elemen queue,

6.    Sebuah array melingkar dengan indeks  depan dan belakang,dan  nilai tertentu untuk untuk menunjukkan status kosong/penuh dari queue.

Model fisik merupakan model yang paling buruk karena memerlukan waktu yang lama untuk proses penggeseran seluruh elemen queue setiap kali ada operasi DeQueue. Kelemeahan ini diperbaiki oleh model ke-2, namun implementasi linier untuk kueue ini, masih memiliki kelemajhan dengan tidak terpakainya ruang array dari posisi pertama hingga posisi yang sebelum posisi yang ditempati elemen queue. Sementara itu, indeks depan dan belakang pasti akan mencapai posisi ruang terakhir dari array. Implementasi dari array merupakan model yang tepat untuk mengatasi inefisiensi penggunaan model array pada model linier. Array dapat dipandang sebagai sebuah lingkaran. Apabila posisi terakhir pada array telah digunakan dan posisi pertama array tidak digunakan lagi, maka elemen queue berikutn ya dapat diletakkan mulai posisi pertama lagi. Untuk mengimplementasikan array melingkar dari sebuah array linier, posisi-posisi yang mengelilingi lingkaran diberi nomor dari 1 s/d maks, sama dengan indeks array linier. Pergeseran/kenaikan indeks dilakukan dengan operasi aritmatika modulo (pembagian bilangan bulat). Ketika nilai indeks melebihi maks, maka dimulai lagi dari 1. Operasi modulo mirip operasi pada sebuah jam, dengan angka 1 s/d 12, bila kita menggeser empat jam dari jam 10 maka kita akan mencapai jam 2. Bila range index digunakan adalah 1..maks, maka pergeseranindeks ini dalam pascal dapat dilakukan dengan pernyataan berikut:

If index = maks then

Indeks := 1 else index := index+1;

Atau dengan operator berikut ini:

Indeks := (index mode maks)+1;

Untuk lebih memahami implementasi queue dengan array melingkar, berikut diilustrasikan penambahan dan penghapusan pada queue, dengan range indeks 1..maks=8.

Queue 1 adalah keadaan queue sebelum digunakan (setelah diinisialisasi). Nilai-nilai elemen array adalah sembarang nilai yang ada dalam memory.

Queue 2 adalah queue dengan 5 buah elemen, berasal dari queue 1 dan 5 kali operasi inqueue, yaitu menyisipkan data A, B, C, D dan E

Queue 3 adalah queue dengan sebuah elemen, berasal dari nqueue 2 dan adanya operasi dequeue empat kali berturut-turut, indeks d= indeks b=5.

Queue 4 adlah queue dengan tujuh elemen, berasal dari 3 queue dan memasukkan 6 buah elemen baru secara berurutan, yaitu F, G, H, I, J K, indeks d=5, indeks b=3.

Queue 5 adalah queue dengan delapan elemen (full), berasal dari queue 4 dan ditambahkan sebuah elemen baru, L indeks d=4, dan indeks b=4.

Queue 6 adalah queue dengan sebuah elemen, berasal dari queue 5 dan dilakukan operasi dequeue tujuh kali berturut-turut, indeks d=5, indeks b=4.

Queue 7 adalah queue kosong, berasal dari queue 6, dan sebuah operasi dequeue, indeks d=5. Dan indeks b=4.

Dari ilustrai tersebut masih terdapat hal yang membingungkan, yaitu pada queue 5 dan queue 7, indeks depan dan belakang pada queue tersebut menunjuk pada lokasi yang sama, tetapi status queuenya berbeda. Queue 5 menyatakan queue penuh, sedangkan queue 7 menyatakan queue kosong.Program Queue Dalam Pascal:
Uses wincrt;

Const N = 100;

Type Queve = record
      isi : Array[1..N]of integer;
      head:integer;
      tail: integer;
     end;

Procedure CreateQueve(Var S:Queve);
     begin
          S.head:=0;
          S.tail:=0;
     end;

Function IsFull(S:Queve):boolean;
     begin
         IsFull := (S.head = 1) and (S.tail = N);
     end;

Function IsEmpty(S:Queve):boolean;
     begin
          IsEmpty := (S.head = 0 ) and (S.tail = 0);
     end;

Procedure add(X:integer; var S:Queve);
     begin
          If Not IsFull(S) then
           begin
                S.tail := S.tail + 1;
                S.isi[S.tail] := X;
                if S.head=0 then
                S.head:=S.head+1;

           end;
     end;

Procedure remove(var X:integer; var S:Queve);
var i:integer;
    begin
         IF NOt IsEmpty(S) then
          begin
               X:=S.isi[S.head];
               for i:= 2 to S.tail do
               S.isi[i-1]:=S.isi[i];
               S.tail :=S.tail - 1;
               if S.tail=0 then
               S.head:=S.head-1;
          end;
    end;

{Main Program}
Var S : Queve;
    X,i,z,m,Y: integer;

Begin
      write('masukan jumlah data ');readln(X);
      CreateQueve(S);
      for i:= 1 to X do
          begin
               write('masukan data ke',i,' : ');readln(m);
               add(m,S);
          end;
      writeln;
        write('jumlah data yang akan dikeluarkan ');readln(Y);
        writeln('data yang dikeluarkan : ');
      for i:= 1 to Y do
          begin
               remove(z,S);
               writeln(z);
          end;
          writeln;
          writeln('data yang tersisa : ');
          for i:= 1 to S.tail do
          writeln(S.isi[i]);
          writeln;
          writeln('S.tail berada di elemen ke ',S.tail);
          writeln('S.head berada di elemen ke ',S.head);

End.