ALGORITMA DAN STRUKTUR DATA : BAB 6

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

Image

Illustrasi Struktur data QUEUE

6. 2 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)

Image

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.

Image

6. 3 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).

Image

 

Circular Array

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);
}

Image

 

Array setelah di CREATE / CLEAR

Image

Image

Beberapa operasi enqueue dengan circular array

 

Image

Operasi dequeue pada queue dengan circular array

ImageImage

Beberapa contoh Queue dalam kondisi EMPTY

 

Salah satu hal penting yang harus diperhatikan pada Circular array adalah kondisi seperti pada gambar di atas yang menunjukan bahwa array telah FULL terisi. Bila array di atas check dengan menggunakan function EMPTY maka pada kondisi yang bersamaan akan  dihasilkan  EMPTY = TRUE. Hal ini dapat diatas dengan mencegah array agar tidak terisi sampai penuh seperti di atas, dimana bila tersisa satu tempat kosong maka itu sudah menunjukan kondisi FULL dan tidak boleh diisi lagi, hal ini dilakukan untuk membedakan antara kondisi FULL dengan kondisi EMPTY . Gambar berikut ini menggambarkan  kondisi FULL seperti yang dimaksud dan dengan function FULL akan mencegah  terjadi full yang dimaksud diatas.Image

Array sudah FULL terisi

 

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s