QUEUE

(Queue) adalah suatu bentuk khusus dari List Linier dengan operasi penyisipan (Insertion) hanyadiperbolehkan pada salah satu sisi, yang disebut sisi Belakang (Rear) dan operasi penghapusan (Deletion) hanyadiperbolehkan pada sisi lainnya yang disebut sisi Depan(Front) dari List.

Prinsip Antrean : FIFO (First In First Out) atau FCFS (First Come First Serve)“Yang Tiba lebih awal Maka akan dilayani TerlebihDahulu”. Jika diartikan secara harafiah, 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. Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue. Walaupun berbeda implementasi, struktur data queue setidaknya harus memiliki operasi-operasi sebagai berikut :

·         EnQueue Memasukkan data ke dalam antrian

·         DeQueue Mengeluarkan data terdepan dari antrian

·         Clear Menghapus seluruh antrian

·         IsEmpty Memeriksa apakah antrian kosong

·         IsFull Memeriksa apakah antrian penuh

Implementasi Queue dengan Linear Array

Linear array adalah suatu array yang dibuat seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar. Berikut ini diberikan deklarasi kelas Queue Linear sebagai implementasi dari Queue menggunakan linear array. Dalam prakteknya, anda dapat menggantinya sesuai dengan kebutuhan Anda. Data diakses dengan field data, sedangkan indeks item pertama dan terakhir disimpan dalam field Head dan Tail. Konstruktor akan menginisialisasikan nilai Head dan Tail dengan -1 untuk menunjukkan bahwa antrian masih kosong dan mengalokasikan data sebanyak MAX_QUEUE yang ditunjuk oleh Data. Destruktor akan mengosongkan antrian kembali dan mendealokasikan memori yang digunakan oleh antrian. 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.

Implementasi Queue dengan Circular Array

Circular array adalah suatu array yang dibuat seakan-akan merupakan sebuah
lingkaran dengan titik awal (head) dan titik akhir (tail) saling bersebelahan jika array tersebut masih kosong. Posisi head dan tail pada gambar diatas adalah bebas asalkan saling bersebelahan. Berikut ini diberikan deklarasi kelas Queue Circular sebagai implementasi circular array. Dalam prakteknya, Anda dapat menggantikanny sesuai dengan kebutuhan Anda. Data diakses dengan field data, sedangkan indeks itemn pertama dan terakhir disimpan dalam field Head dan Tail. Konstruktor akan menginisialisasi nilai Head dan Tail dengan 0 dan MAX-QUEUE-1 untuk menunjukkan bahwa antrian masih kosong dan mengalokasikan data sebanyak MAX-QUEUE yang ditunjuk oleh Data. destruktor akan mengosongkan antrian kembali dan mendealokasikan memori yang digunakan oleh antrian. Operasi-Operasi Queue dengan Circular Array :

• IsEmpty, Fungsi IsEmpty berguna untuk mengecek apakah Queue masih kosong atau sudah berisi. Hal ini dilakukan dengan mengecek apakah tail masih terletak bersebelahan dengan head dan tail lebih besar dari head atau tidak. Jika benar, maka queue masih kosong.
• IsFull, Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bias menampung data dengan cara mengecek apakah tempat yang masih kosong tinggal satu atau tidak (untuk membedakan dengan empty dimana semua tempat kosong). Jika benar berarti queue penuh.
• EnQueue, Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue tail dan head mula-mula bernilai nol (0).
• DeQueue, DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara memindahkan posisi head satu langkah ke belakang.

Dengan deklarasi di atas, 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 teraihir dalam array.

Algoritma dari penggalan program di atas adalah :

Tentukan elemen yang akan dimasukkan ke dalam antrian (dalam hal ini adalah 6 elemen).

Deklarasikan struktur untuk menampung elemen pada antrian.
Selesai.

Untuk menambah elemen baru dan mengambil elemen dari antrian dalam antrian, diperlukan deklaras berikut ini :

 

PADA QUEUE

 KONDISI ANTRIAN LURUS

Kondisi Antrian	Ciri
KOSONG PENUH BISA DIISI ADA ISINYA PERLU DIRESET	F = R + 1 dimana saja R = n – 1 R < n – 1 F < R + 1 F = R + 1 dan R = n - 1

 

ALGORITMA LENGKAP INSERT

Periksa apakah Antrian BISA DIISI

 

  if ( R < n – 1)

  {

  R = R + 1;

  Q[R] = x;

  }

  else

  cout<<“Antrian Penuh”;

ALGORITMA LENGKAP DELETE

Periksa apakah Antrian ADA ISINYA

  if ( F < R + 1)

  {

  x = Q[F];

  F = F + 1;

  if ((F=R+1) && (R=n-1))

  { F = 0;

    R = -1; }

  }

  else

  cout<<“Antrian Kosong”;

Contoh Program :

#include “stdio.h”
void main()
{ int queue[5];
int depan = -1;
int belakang = -1;
int pilihan, data, i;

do{
printf(“MENU\n”);
printf(“1. ENQUEUE\n2. DEQUEUE\n3. VIEW\n4. EXIT\n”);
printf(“Pilihan = “); scanf(“%d”, &pilihan);
switch (pilihan)
{
case 1: //enqueue
//apakah queue belum penuh?
if (belakang < 4 )
{ printf(“Data Masuk = “); scanf(“%d”, &data);
queue[belakang+1] = data;
belakang++;
if (belakang == 0)
depan = 0;
}
else
printf(“Queue penuh!\n”);

break;
case 2: //dequeue
//apakah queue belum kosong?
if (depan <= belakang)
{ printf(“Data keluar = %d\n”, queue[depan]);
depan++;
}
else
printf(“Queue kosong!\n”);
break;
case 3:
for(i=depan; i<=belakang; i++)
printf(“%d “, queue[i]);
printf(“\n”);
break;
}
}while (pilihan != 4);
}

PADA DEQUE

Prinsip / Konsep Proses :

–bukan FIFO, bukan juga LIFO, tergantung kesempatan yang ada.

Proses :

a.AWAL (Inisialisasi)

b.INSERT (Sisip, Masuk, Simpan, Tulis)

c.DELETE (Hapus, Keluar, Ambil/Dilayani, Baca)

  

Kondisi Deque

	Kondisi Antrian	Ciri
a. b. c. d. e. f.	KOSONG PENUH KIRI PENUH KANAN BISA DIISI DARI KIRI BISA DIISI DARI KANAN ADA ISINYA	L = R + 1 dimana saja L = 0 R = n – 1 L  > 0 R < n – 1 L  < R + 1

Algoritma Lengkap Insert Kiri

Periksa apakah Deque BISA DIISI DARI KIRI

  void INSERT_KIRI()

  {  if ( L > 0)

  {

  L = L - 1;

  Q[L] = x;

  }

  else

  cout<<“Antrian Kiri Penuh”;

  }

Algoritma Lengkap Insert Kanan

Periksa apakah Deque BISA DIISI DARI KANAN

  void INSERT_KANAN() 

  {  if ( R < n - 1)

  {

  R = R + 1;

  Q[R] = x;

  }

  else

    cout<<“Antrian Kanan Penuh”;

  }

 Algoritma Lengkap Delete Kiri

Periksa apakah Deque ADA ISINYA

  void DELETE_KIRI()

  {  if (L < R + 1)

  {

  x = Q[L];

  L = L + 1;

  }

  else

  cout<<“Antrian Kosong”;

  }

 Algoritma Lengkap Delete Kanan

•Periksa apakah Deque ADA ISINYA

  void DELETE_KANAN()

  {  if (L < R + 1)

  {

  x = Q[R];

  R = R - 1;

  }

  else

  cout<<“Antrian Kosong”;

  }

  Referensi :

https://www.google.co.id/search?sclient=psy-
ab&site=&source=hp&btnG=Search&
q=materi+tentang+queue

http://arna.lecturer.pens.ac.id/Modul_ASD/3.%20Queue.pdf