Queue adalah FIFO yang merupakan singkatan dari First In First Out, artinya adalah data yang pertama kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan. Analoginya sama dengan antrian di sebuah loket pembelian tiket kereta, orang yang datang lebih dahulu, maka akan dilayani terlbih dahulu, dan akan selesai lebih dulu dari orang-orang yang datang setelahnya.
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.
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
meletakkan HEAD dan TAIL pada indeks array ke-0. Berikut deklarasi prosedur
createEmpty pada queue 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 pada indeks ke-1 terlebih dahulu, baru setelah itu
memasukkan data/ nilai ke dalam array 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;
}
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;
6 5 4 3 2 1 0
7 6 5 4 3 2 1 0
7 6 5 4 3 2 1 0
2 7
2 HEAD TAIL TAIL HEAD
2 TAIL HEAD
11 }
7 6 5 4 3 2 1 0
7 6 5 4 3 2 1 0
2 7
2 HEAD TAIL TAIL HEAD
2 TAIL HEAD
11 }
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;
}
{
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;
}
Contoh Queue
//program implementasi queue
#include
#define max 5
typedef struct
{
int HEAD, TAIL; //untuk mencacah indeks dari stack
int data[max+1];
}Queue;
Queue antrian;
void createEmpty();
int IsEmpty();
int IsFull();
void Enqueue(int x);
void Dequeue();
void main()
{
int lagi;
int input;
createEmpty();
//mengisi queue
lagi = 1;
while (lagi == 1)
{
if ((IsEmpty() == 1) || (IsFull() == 0))
{
system("cls");
printf("Antrian masih tersedia.\n");
printf("Masukkan nilai: ");
scanf("%d",&input);
Enqueue(input);
printf("Tambah data (1/0)?");
scanf("%d",&lagi);
}
else if (IsFull() == 1)
{
printf("Antrian sudah penuh.\n");
lagi = 0;
}
}
//menampilkan isi stack
while (IsEmpty() == 0)
{
printf("%d ",antrian.data[antrian.HEAD]);
Dequeue();
}
return 0;
}
#include
#define max 5
typedef struct
{
int HEAD, TAIL; //untuk mencacah indeks dari stack
int data[max+1];
}Queue;
Queue antrian;
void createEmpty();
int IsEmpty();
int IsFull();
void Enqueue(int x);
void Dequeue();
void main()
{
int lagi;
int input;
createEmpty();
//mengisi queue
lagi = 1;
while (lagi == 1)
{
if ((IsEmpty() == 1) || (IsFull() == 0))
{
system("cls");
printf("Antrian masih tersedia.\n");
printf("Masukkan nilai: ");
scanf("%d",&input);
Enqueue(input);
printf("Tambah data (1/0)?");
scanf("%d",&lagi);
}
else if (IsFull() == 1)
{
printf("Antrian sudah penuh.\n");
lagi = 0;
}
}
//menampilkan isi stack
while (IsEmpty() == 0)
{
printf("%d ",antrian.data[antrian.HEAD]);
Dequeue();
}
return 0;
}
0 komentar:
Posting Komentar