Queue
1.
Pendahuluan Kaidah utama dalam konsep 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. Gambar di bawah ini mengilustrasikan kerja sebuah queue:
2.
Deklarasi queue dalam program Sebuah queue di dalam program komputer
dideklarasikan sebagai sebuah tipe bentukan baru, di dalam Bahasa C, biasa
disebut struct. Sebuah struktur data dari sebuah queue setidaknya harus
mengandung dua tiga variabel, yakni variabel HEAD yang akan berguna sebagai
penanda bagian depan antrian, variabel TAIL yang akan berguna sebagai penanda
bagian belakang antrian dan ARRAY DATA dari yang akan menyimpan data-data yang
dimasukkan ke dalam queue tersebut. Berikut adalah syntax untuk mendeklarasikan
struktur data dari sebuah queue menggunakan Bahasa C:
typedef struct { int HEAD, TAIL; int data[max+1]; }
Queue;
dimana,
nilai MAX didefinisikan sebagai jumlah tumpukan maksimum yang dapat disimpan
dalam queue. Setelah strukutr data dari queue didefinisikan dengan syntax di
atas, maka setelah itu dapat dibuat variabel-variabel baru yang mengacu pada
tipe data Queue di atas, misalkan membuat sebuah variabel bernama antrian yang
bertipe Queue:
Queue antrian;
Dalam
tulisan ini, sebuah queue didefinisikan dengan array berukuran MAX + 1,
maksudnya adalah agar elemen array ke-0 tidak digunakan untuk menyimpan data,
melainkan hanya sebagai tempat „singgah‟ sementara untuk variabel HEAD dan
TAIL. Sehingga, jika HEAD dan TAIL berada pada elemen array ke-0, berarti queue
tersebut dalam kondisi kosong (tidak ada data yang disimpan). Berikut adalah
ilustrasi dari sebuah queue kosong dengan ukuran nilai MAX = 6:
3. Operasi-operasi dasar dalam queue 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.
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; }
Pada deklarasi prosedur enqueue di atas, prosedur memiliki
sebuah parameter formal yang bernama „x‟ yang bertipe integer. Parameter formal
„x‟ ini berguna untuk menerima kiriman nilai dari program utama (void main())
yakni berupa sebuah bilangan integer yang akan dimasukkan ke dalam queue.
Gambar di bawah ini mengilustrasikan proses enqueue ke dalam sebuah queue yang
masih kosong.
C.
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;
}
Ketika
posisi HEAD sudah melewati posisi TAIL (HEAD > TAIL), berarti sudah tidak
ada lagi data/ nilai di dalam queue tersebut, maka saat itu terjadi, HEAD dan
TAIL dikembalikan ke posisi ke-0. Gambar di bawah ini mengilustrasikan cara
kerja prosedur dequeue:
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; }
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; }
4.
Contoh program implementasi queue Berikut adalah contoh kode program dalam
Bahasa C yang mengimplementasikan konsep queue. Pada program ini, user akan
menginputkan data satu per satu, kemudian setelah selesai menginputkan data ke
dalam queue, maka program akan menampilkan semua isi queue.
|
|
|
