QUEUE

Definisi Queue
Queue merupakan satu bagian dari tipe data abstrak yang dibicarakan pada bab 5. Queue adalah
suatu tipe data yang mengikuti pola First In First Out (FIFO), yang berarti elemen yang pertama
masuk adalah elemen yang pertama pula dikeluarkan. Banyak contoh dalam kehidupan sehari-hari
yang menerapkan konsep dari Queue, atau yang dalam bahasa Indonesia lebih dikenal dengan istilah
antrian seperti antrian pasien di ruang tunggu dokter, antrian penonton yang membeli tiket, dsbnya.
Sama halnya seperti stack, queue juga merupakan satu tipe data abstrak yang
pengimplementasiannya bebas, artinya dapat diimplemetasikan dengan array maupun dengan list.

Implementasi Queue dengan struktur data Array

Untuk setiap struktur data queue yang diimplementasikan dengan array, posisi front (depan) back
(belakang) akan selalu ada. Perhatikan gambar berikut ini menunjukkan ilustrasi dari sebuah queue
yang diimplementasikan dengan menggunakan array. Dua hal yang menarik perhatian adalah (1)
queue bergerak dari indeks kecil menuju indeks yang besar dan (2) diperlukan dua buah penunjuk
(dalam ilustrasi disebut head dan tail)

Hal yang menarik, sekaligus merupakan kelemahan dari implementasi ini terjadi bila tail dari queue
telah merambat sampai keposisi pjg_max maka queue tersebut tidak dapat diisi lagi walaupun
sebenarnya queue tersebut belum penuh ( area yang berada di posisi 1 sampai head sebenarnya
merupakan tempat yang kosong). Ilustrasinya digambarkan berikut ini.

Circular Array

Ide yang paling sederhana adalah dengan mengisi tempat kosong (jika tersedia) yang berada pada
awal array bila tail telah mencapai posisi pjg_max sehingga penggunaan tempat menjadi lebih efisien.
Jadi seolah-olah array di bawah ini dibulatkan manjadi sebuah lingkaran seperti digambarkan berikut
ini (nama circular array berasal dari ide array yang dibulatkan).

Berikut adalah program C untuk mengimplementasikan Queue dengan menggunakan circular array.

#include <stdio.h>
#define PJG_MAX 10
Typedef int elemenType;
elementypeQ[PJG_MAX];
int head, tail;
void create()
{
Head = 0;
Tail = PJG_MAX -1;
}
void enqueue(elemenType e)
{
if(full()) printf(“queue sudah penuh\n”);
else {
Tail++;
Tail = Tail % PJG_MAX;
Q[Tail] = e;
}
}
void dequeue(elemenType*e)
{
if(empty()) printf(“Queue kosong\n”);
else {
*e = Q[head];
Head++;
Head = Head % PJG_MAX;
}
int empty()
{
if(((tail+1) % PJG_MAX) == Head) return (1);
else return (0);
}
void full()
{
int x;
x = Tail+2;
x = x % PJG_MAX;
if(x == Head) return (1);
else return (0);
}

Untuk lebih lengkap nya silahkan download materi nya disini