A. Pengertian Queue
Queue pada struktur data atau antrian
adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada
suatu ujung disebut dengan sisi belakang (rear),
dan penghapusan (pengambilan elemen) dilakukan lewat ujung lain (disebut dengan
sisi depan atau front).
Pada
stack atau tumpukan menggunakan
prinsip “Masuk terakhir keluar pertama” atau dengan sebutan LIFO (Last In First Out), maka pada Queue atau antrian prinsip yang
digunakan adalah “Masuk pertama keluar pertama” atau dengan sebutan FIFO (first In Fisrt Out).
Queue atau antrian banayak kita jumpai
dalam kehidupan sehari-hari, sebagai contoh yang dapat diambil: antrian mobil
di loket Tol, antrian mahasiswa mendaftar, dan masih banyak lagi contoh
lainnya.
Contoh
lain dalam bidang komputer adalah pemakaian sistem komputer berbagi waktu (time sharing computer system) dimana ada
sejumlah pemakai yang akan menggunakan sistem tersebut secara serempak.
Pada
Queue atau antrian terdapat satu buah
pintu masuk disuatu ujung dan satu buah pintu keluar diujung satunya dimana
membutuhkan variabel Head dan Tail (depan/front, belakang/rear).
1. Karakteristik Queue
Ø Elemen antrian
Ø Front (elemen
terdepan antrian)
Ø Tail (elemen
terakhir)
Ø Jumlah elemen pada antrian
Ø Status antrian
2. Operasi-Operasi Queue
Ø EnQueue:
Masukkan data ke dalam antrian.
Ø DeQueue:
Mengeluarlan data terdepan dari antrian
Ø Clear:
Menghapus seluruh antrian
Ø IsEmpty:
Memeriksa apakah antriang kosong atau tidak
Ø IsFull:
Memeriksa apakah antrian penuh atau tidak
Contoh pengambaran operasi Queue dalam sehari-hari:
a. EnQueue: Seseorang membeli tiket melalui tempat
pembayaran tiket yang disediakan.
b. DeQueue: Setelah membeli tiket, langsung menuju tempat
penungguan kereta, dengan sebelumnya petugas memeriksa cek tiket tersebut.
c. Clear: Pembeli tiket tersebut telah terhapus dari
antrian karena sudah melewati pembayaran administrasi tersebut.
d. IsEmpty: Petugas tiket kereta melihat tidakk ada lagi
yang ingin membeli tiket kereta.
e. IsFull: Petugas tiket kereta melihat masih ada pembeli
tiket kereta.
B. Kondisi Antrian yang Menjadi Perhatian
1. Penuh
Bila elemen pada antrian mencapai kapasitas maksimum
antrian, maka tidak mungkin dilakukan penambahan ke antrian. Penambahan elemen
menyebabkan kondisi kesalahan overflow.
2. Kosong
Bila tidak ada elemen pada antrian, maka tidak mungkin
dilakukan pengambilan elemen dari antrian. Pengambilan elemen menyebabkan
kondisi kesalahan overflow.
C. Perbedaan Queue dan Stack
Ø Sementara Queueu memakai sistem FIFO (First
In First Out), yang apabila kita menghapus atau mengeluarkan data, maka
data yang pertamalah yang akan terhapus atau keluar terdahulu dan data yang
teerakhir akan terhapus atau keluar terakhir.
Ø Sedangkan Stack memakai sistem LIFO (Last
In First Out) apabila kita menghapus atau keluar data, maka data yang
terakhirlah yang akan terhapus atau keluar terlebih dahulu.
D. Contoh Program
|
#include<stdio.h>
#include<iostream>
#include<conio.h>
#define
MAX 8
using
namespace std;
typedef
struct
{
int data[MAX];
int head;
int tail;
}queue;
queue
antrian;
void
Create()
{
antrian.head=antrian.tail=-1;
}
int
IsEmpty()
{
if (antrian.tail==-1)
return 1;
else
return 0;
}
int
IsFull()
{
if (antrian.tail==MAX-1)
return 1;
else
return 0;
}
int
Enqueue (int data)
{
if (IsEmpty()==1)
{
antrian.head=antrian.tail=0;
antrian.data[antrian.tail]=data;
printf("% sudah
dimasukkan", antrian.data[antrian.tail]);
}
else
if (IsFull()==0)
{
antrian.tail++;
antrian.data[antrian.tail]=data;
printf("% sudah
dimasukkan", antrian.data[antrian.tail]);
}
}
int
Dequeue()
{
int i;
int e=antrian.data[antrian.head];
for (i=antrian.head;
i<=antrian.tail-1; i++)
{
antrian.data[i]=antrian.data[i+1];
}
antrian.tail--;
return e;
}
void
Clear()
{
antrian.head=antrian.tail=-1;
printf("CLEAR");
}
void
Tampil()
{
if (IsEmpty()==0)
{
for(int i=antrian.head;
i<=antrian.tail; i++)
{
printf("% ",
antrian.data[i]);
}
}
else
printf("data kosong!\n");
}
main
()
{
int pil;
int data;
Create();
do
{
cout << endl;
cout <<
"\n========================================="<<endl;
cout << "\n Program Queue "<<endl;
cout <<
"\n========================================="<<endl;
cout << "\n 1.
Enqueue ="<<endl;
cout << "\n 2.
Dequeue ="<<endl;
cout << "\n 3. Tampil ="<<endl;
cout << "\n 4. Clear ="<<endl;
cout << "\n 5. Exit ="<<endl;
cout <<
"\n========================================="<<endl;
cout << "\n Masukkan
Pilihan : "; cin >> pil;
switch(pil)
{
case 1:
cout << "\n Masukkan
Data : "; cin >> data;
Enqueue(data);
break;
case 2:
Dequeue();
break;
case 3:
Tampil();
break;
case 4:
Clear();
break;
case 5:
break;
}
getch();
}
while(pil!=5);
return 0;
}
|
Hasil Running:
Sumber:
