Quee (Antrian)

QUEUE
(ANTRIAN)
eue (antrian) adalah barisan elemen yang apabila elemen ditambah maka
ahannya berada di posisi belakang (rear) dan jika dilakukan pengambilan elemen
n di elemen paling depan (front). Oleh karena itu, queue bersifat FIFO (first in
.
ntoh : epan=1 Belakang=4
5 6 7 9
erasi-operasi dasar dari sebuah queue adalah :
nqueue : proses penambahan elemen di posisi belakang
Dequeue : proses pengambilan elemen di posisi depan
lain operasi dasar di atas, ada pula operasi-operasi lain yang dapat dilakukan
sebuah queue yaitu :
Operasi pemeriksaan queue kosong (fungsi kosong)
Operasi pemeriksaan queue penuh (fungsi penuh).
Operasi inisialisasi queue (fungsi inisialisasi) Adapun presentasi queue dapat dilakukan dengan 2 car
Dengan menggunakan array statis
Operasi-operasi yang dapat dilakukan dalam queue yan
array statis adalah :
1.1. Pendeklarasian sebuah queue
Setiap queue memiliki elemen-elemen (field) b
belakang, elemen antrian, dan maksimal elemennya.
Adapun pendeklarasian queue dalam bahasa C adala
#define maks 5
struct TQueue{
int depan,belakang;
int maks_queue;
int antrian[maks];
};
TQueue Q,Queue,Q2;//deklarasi variable ber

1.2. Inisialisasi Queue
Inisialisasi queue adalah proses pemberian nilai
belakang dari queue dan juga pemberian nilai
menunjukan banyaknya maksimal data dalam queue
Karena dalam bahasa C elemen sebuah array dim
inisialisasi nilai depan dan belakang bukan 0 tetapi
penambahan elemen (enqueue) akan bernilai 0 se
disimpan dalam elemen antrian pada posisi 0.

Implementasi fungsi inisialisasi queue dalam bahasa
void inisialisasi(TQueue *Q)
{
Q->maks_queue=maks;
Q->depan=-1;
Q->belakang=-1;
}

Cara pemanggilannya adalah :
Inisialisasi(&Q);
1.3. Fungsi Kosong
Fungsi kosong digunakan untuk memeriksa apakan keadaa
memiliki elemen. Fungsi kosong didapatkan dengan memeriksa
dari queue. Jika field belakang bernilai 0 maka berarti queue k
tidak 0 maka berarti queue mempunyai elemen.
Implementasi dalam bahasa C agak berbeda karena elemen array
sehingga pemeriksaan nilai belakang dilakukan dengan mem
dengan nilai -1. Jika nilai belakang bernilai -1 maka queue koson
lebih dari -1 berarti queue tidak kosong (false). Sehingga impleme
bahasa C adalah :
int kosong(TQueue Q)
{
if (Q.belakang==-1)
return 1;
else
return 0;
}
Cara pemanggilannya adalah :
if(kosong(Q))// jika queue Q kosong
……

1.4. Fungsi Penuh
Fungsi penuh berguna untuk memeriksa apakah suatu queue telah
ini diperlukan ketika proses enqueue. Fungsi ini akan bernilai b
field belakang sama dengan nilai maks_queue jika tidak sama
queue belum penuh.
Dalam bahasa C perbandingan yang dilakukan adalah bukan deng
tetapi dengan nilai maks_queue-1 karena elemen array dalam ba
dari posisi 0. Implementasi dalam bahasa C adalah :
int penuh(TQueue Q)
{
if(Q.belakang==Q.maks_queue-1)
return 1;
else
return 0;
}
Cara pemanggilannya adalah :
If(!penuh(Q)) //if queue Q tidak(!) penuh 1.5. Operasi Enqueue
Proses enqueue adalah proses untuk penambahan di posi
Penambahan ini dilakukan jika kondisi queue tidak penuh. Jika ke
kosong, maka field depan dan belakang bernilai 1 tetapi jika sudah
elemen maka yang nilai belakang harus bertambah 1. Kemudia
disimpan di array pada posisi belakang.
Implementasi dalam C harus melakukan penyesuaian karena ele
dimulai dari 0 sehingga ketika queue masih kosong pemberian nil
belakang adalah 0 bukan 1. Untuk lebih jelasnya perhatikan potonga
bawah ini :
void enqueue(TQueue *Q, int data)
{
if(!penuh(*Q))
{
if(empty(*Q)
{
Q->depan=0;
Q->belakang=0;
}
else
Q->belakang++;

Q->antrian[Q->belakang]=data;
}
else
printf("Queue Telah Penuh\n");
}
Cara penggunaannya :
int data=7
enqueue(&Q,data);
1.6. Operasi Dequeue
Operasi dequeue adalah proses pengambilan elemen queue. Tentunya elemen
yang diambil selalu dari elemen pertama (1). Setelah elemen pertama diambil,
maka akan diperlukan proses pergeseran elemen data setelah elemen data yang
diambil (dari posisi ke-2 sampai posisi paling belakang), dan kemudian posisi
belakang akan dikurangi 1 karena ada data yang diambil.
Implementasi dalam bahasa C dilakukan dengan pengambilan elemen pada
posisi 0, sehingga fungsi dequeue-nya menjadi :
int dequeue(TQueue *Q)
{
int data,i;
if(!kosong(*Q))
{
data=Q->antrian[Q->depan];
for(i=0;i<=Q->belakang-1;i++)
Q->antrian[i]=Q->antrian[i+1];
Q->belakang--;
return data;
}
else
{
printf("Queue Kosong.\n");
return 0;
}
}
Cara penggunaan fungsi tersebut adalah :
int data;
data=dequeue(&Q); //ambil data dari dequeue pada queue Q
printf(“%d”,data);
2. Dengan menggunakan linked list.
Proses penyimpanan elemen queue dalam linked list mirip dengan operasi pada single
linked list yang menggunakan penyimpanan tambah akhir dan hapus awal.
Contoh :
DepanBelakang
45915NULL

Operasi-operasi yang dapat dilakukan dalam queue yang menggunakan representasi
linked list adalah :
2.1. Pendeklarasian sebuah queue
Setiap queue memiliki elemen-elemen (field) berupa posisi depan, posisi
belakang, elemen antrian, dan posisi penunjuk ke elemen berikutnya. Berikut ini
adalah pendeklarasian queue yang disimpan dalam bentuk linked list.
typedef struct TQueue *PQueue;
typedef struct TQueue{
int data;
PQueue berikutnya;
};
PQueue depan,belakang; //depan dan belakang queue adalah pointer

2.2. Inisialisasi Queue
Proses inisialisasi queue yang disimpan dalam bentuk linked list adalah dengan
memberikan nilai NULL ke pointer depan dan belakang yang menandakan
bahwa pointer depan dan belakang belum menunjuk ke 1 elemen apapun.
Implementasi dalam bahasa C adalah :
void inisialisasi(PQueue *depan, PQueue *belakang)
{
*depan=NULL;
*belakang=NULL;
}
Cara penggunaannya adalah :
Inisialisasi(&depan,&belakang);
2.3. Fungsi Kosong
Fungsi ini berguna untuk memeriksa apakah suatu
Fungsi ini berguna ketika proses dequeue yaitu
diambil, maka harus diperiksa dulu apakah memili
akan mempunyai nilai benar jika depan atau belaka
Implementasinya dalam bahasa C adalah :
int kosong(PQueue depan)
{
if(depan==NULL)
return 1;
else
return 0;
}
Cara penggunaannya adalah :
If(kosong(awal))
……..

2.4. Fungsi Penuh
Fungsi ini berguna untuk memeriksa apakah m
menyimpan data elemen queue. Oleh karena itu la
dengan membuat suatu elemen baru di memori
tersebut berhasil berarti memori belum penuh dan
gagal dibuat berarti memori sudah penuh. Jangan l
baru yang tadi dibuat agar kondisi memori kembal
penambahan elemen baru.
Implementasinya dalah bahasa C adalah :
int penuh()
{
PQueue baru;
baru=(PQueue)malloc(sizeof(TQueue));
if(baru!=NULL)
{
free(baru);
return 0;
}
else
return 1;
}
Cara penggunaannya adalah :
If(!penuh()) // jika memori penuh
……..
2.5. Operasi Enqueue
Proses enqueue dalam queue linked list adalah dengan menambahkan elemen
baru ke posisi paling belakang (sambungkan field berikutnya dari field belakang
ke posisi pointer baru). Setelah itu, pointer penunjuk belakang harus berpindah
ke posisi baru tersebut. Proses ini seperti proses penambahan di belakang pada
single linked list.
Implementasinya dalam bahasa C adalah :
void enqueue(PQueue *depan, PQueue *belakang, int data)
{
PQueue baru;
if(!penuh())
{
baru=(PQueue)malloc(sizeof(baru));
baru->data=data;
baru->berikutnya=NULL;
if(kosong(*depan))
{
*depan=baru;
*belakang=baru;
}
else
{
(*belakang)->berikutnya=baru;
*belakang=baru;
}
}
else
printf("Memori Kosong\n");
}

Cara penggunaannya adalah :
Enqueue(&depan,&belakang,5);//memasukan angka 5 ke posisi akhir
2.5. Operasi Enqueue
Proses enqueue dalam queue linked list adalah dengan menambahkan elemen
baru ke posisi paling belakang (sambungkan field berikutnya dari field belakang
ke posisi pointer baru). Setelah itu, pointer penunjuk belakang harus berpindah
ke posisi baru tersebut. Proses ini seperti proses penambahan di belakang pada
single linked list.
Implementasinya dalam bahasa C adalah :
void enqueue(PQueue *depan, PQueue *belakang, int data)
{
PQueue baru;
if(!penuh())
{
baru=(PQueue)malloc(sizeof(baru));
baru->data=data;
baru->berikutnya=NULL;
if(kosong(*depan))
{
*depan=baru;
*belakang=baru;
}
else
{
(*belakang)->berikutnya=baru;
*belakang=baru;
}
}
else
printf("Memori Kosong\n");
}

Cara penggunaannya adalah :
Enqueue(&depan,&belakang,5);//memasukan angka 5 ke posisi akhir
QUEUE DENGAN CIRCULAR ARRAY

Jika kita menggunakan array untuk queue seperti di atas, maka ketika ada proses
pengambilan (dequeue) ada proses pergeseran data. Proses pergeseran data ini pasti
memerlukan waktu apalagi jika elemen queue-nya banyak. Oleh karena itu solusi agar
proses pergeseran dihilangkan adalah dengan metode circular array.
Queue dengan circular array dapat dibayangkan sebagai berikut :

Depan=1 Belakang=4
5 6 7 9
Atau agar lebih jelas, array di atas dapat dibayangkan ke dalam bentuk seperti
lingkaran di bawah ini.
1
5
5
4962
7
3
depan = 1
belakang = 4

Aturan-aturan dalam queue yang menggunakan circular array adalah :
1. Proses penghapusan dilakukan dengan cara nilai depan (front) ditambah 1 :
depan=depan + 1.
2. Proses penambahan elemen sama dengan linear array yaitu nilai belakang ditambah 1 :
belakang=belakang + 1.
3. Jika depan = maks dan ada elemen yang akan dihapus, maka nilai depan = 1.
4. Jika belakang = maks dan depan tidak 1 maka jika ada elemen yang akan
ditambahkan, nilai belakang=1
5. Jika hanya tinggal 1 elemen di queue (depan = belakang), dan akan dihapus maka
depan diisi 0 dan belakang diisi dengan 0 (queue kosong). Contoh :
Untuk mempermudah, elemen dari queue bertipe karakter.
No Operasi Status Queue
1 2 3 4 5
1. Inisialisasi Depan = 0

Belakang = 0
2. Enqueue A, B, E Depan = 1
A B C
Belakang = 3
3. Dequeue menghasilkan Depan = 2
B C
nilai A Belakang = 3
4. Enqueue D, E Depan = 2
B C D E
Belakang = 5
5. Dequeue 2 kali Depan = 4
D E
menghasilkan B, dan C Belakang = 5
6. Enqueue F Depan = 4
F D E
Belakang = 1
7. Enqueue G, H Depan = 4
F G H D E
Belakang =3
8. Dequeue menghasilkan Depan = 5
F G H E
D Belakang=4
9. Dequeue menghasilkan Depan = 1
F G H
E Belakang = 3
10. Dequeue 2 kali Depan = 3
H
menghasilkan F dan G Belakang = 3
11. Dequeue menghasilkan Depan = 0

H Belakang = 0

1515151515
AEEEF
24B24B24DB24D24D
CCC
333333

erasi 1 Operasi 2 Operasi 3 Operasi 4 Operasi 5 Operas

151515151 FEFF
G24G24G24242
HHHH
33333

erasi 7 Operasi 8 Operasi 9 Operasi 10 Operasi 11 Operasi-operasi yang dapat terjadi dalam queue yang menggunakan circular array
ah :
Pendeklarasian Queue
Setiap queue memiliki elemen-elemen (field) berupa posisi depan, posisi belakang,
elemen antrian, dan maksimal elemennya.
Adapun pendeklarasian queue dalam bahasa C adalah :
#define maks 5
struct TQueue{
int depan,belakang;
int maks_queue;
int antrian[maks];
};
TQueue Q,Queue,Q2;//deklarasi variable bertipe TQueue
Inisialisasi Queue
nisialisasi queue adalah proses pemberian nilai 0 untuk field depan dan belakang dari
queue dan juga pemberian nilai maks ke maks_queue yang menunjukan banyaknya
maksimal data dalam queue.
Karena dalam bahasa C elemen sebuah array dimulai dengan 0 maka proses
nisialisasi nilai depan dan belakang bukan 0 tetapi -1 sehingga ketika ada proses
penambahan elemen (enqueue) akan bernilai 0 sehingga elemen tersebut akan
disimpan dalam elemen antrian pada posisi 0.
mplementasi fungsi inisialisasi queue dalam bahasa C adalah
void inisialisasi(TQueue *Q)
{
Q->maks_queue=maks;
Q->depan=-1;
Q->belakang=-1;
}
Cara pemanggilannya adalah :
Inisialisasi(&Q); 3. Fungsi Kosong
Suatu queue yang menggunakan circular array dapat dikatakan kosong jika nilai y
menunjuk posisi depan atau belakang mempunyai nilai 0.
Implementasi dalam bahasa C, perbandingan posisi depan atau belakang dilaku
bukan dengan angka 0 tetapi angka -1 karena angka 0 menunjukan elemen pert
dari array. Sehingga source code fungsi pemeriksaan apakah queue kosong adalah
int kosong(TQueue Q)
{
if (Q.belakang==-1)
return 1;
else
return 0;
}
Cara pemanggilannya :
If(kosong(Q)) // jika Queue Q kosong
......

4. Fungsi Penuh
Suatu queue akan disebut penuh jika terjadi 2 hal yaitu jika nilai depan mempun
nilai 1 dan posisi belakang sama dengan maks_queue atau jika posisi depan s
dengan posisi belakang +1. Jika salah satu dari 2 hal tersebut terjadi maka fu
penuh mempunyai nilai true dan jika tidak terjadi 2 hal tersebut maka fungsi bern
false.
Implementasi dalam bahasa C agar beda karena posisi awal array bukan 1 tapi 0
posisi terakhir data adalah maks_queue-1 bukan maks_queue. Sehingga fungsi
akan seperti di bawah ini :
int penuh(TQueue Q)
{
if(
((Q.depan==0)&&(Q.belakang==Q.maks_queue-1))
||
((Q.depan==Q.belakang+1))
)
return 1;
else
return 0;
}
Cara pemanggilannya adalah :
If(!penuh(Q)) // jika queue Q tidak (!) penuh 5. Operasi Enqueue
Proses enqueue data hanya bisa dilakukan jika queue tidak kosong. Ada beb
yang harus diperhatikan ketika akan melakukan enqueue pada circul
diantaranya adalah : Kondisi ketika queue masih kosong. Jika ini terjadi, maka posisi d
belakang bernilai 0. Ketika ketika nilai belakang sama dengan maks_queue, maka posisi
adalah 0. Ini terjadi ketika posisi depan lebih besar dari 0 (pe
dequeue). Ketika nilai belakang masih lebih kecil dari maks_queue ma
belakang ditambah 1 : belakang=belakang+1;
Dari ketentuan-ketentuan di atas dapat diimplementasikan dalam bahasa
mengganti beberapa hal yaitu posisi perbandingan/pengisian dengan nilai
dengan perbandingan/pengisian dengan nilai -1 dan perbandingan den
maks_queue diganti dengan maks_queue-1. Itu disebabkan karena dalam
array dimulai dari 0. Dengan hal tersebut implementasi operasi Enqueue-n
sebagai berikut :
void enqueue(TQueue *Q, int data)
{
if(!penuh(*Q))
{
if(Q->depan==-1)
{
Q->depan=0;
Q->belakang=0;
}
else
if(Q->belakang==Q->maks_queue-1)
Q->belakang=0;
else
Q->belakang++;

Q->antrian[Q->belakang]=data;
}
else
printf("Queue Telah Penuh\n");
}
Cara penggunaannya adalah :
Enqueue(&Q,5);//menambahkan elemen 5 ke dalam queue Q 6. Operasi Dequeue
Proses dequeue hanya bisa dilakukan jika queue dalam keadaan tidak ko
beberapa kondisi yang harus diperhatikan ketika dequeue elemen queue yai Kondisi ketika posisi depan sama dengan posisi belakang (qu
memiliki 1 elemen) maka nilai depan dan belakang diisi dengan
kosong). Jika posisi depan sama dengan posisi maks_queue maka po
berpindah ke 1. Selain itu, posisi depan ditambah dengan 1 : depan=depan+1
Ketika kita mengimplementasikannya dalam bahasa C, maka ada beberap
harus diganti adalah semua pengisian/perbandingan dengan angka 1 digant
(karena elemen array dalam bahasa C adalah 0), serta k
perbandingan/pengisian dengan nilai 0 diganti dengan -1 dan perbandingan
dengan nilai maks_queue diganti dengan maks_queue-1. Impelementasi
bahasa C adalah :
int dequeue(TQueue *Q)
{
int data,i;
if(!kosong(*Q))
{
data=Q->antrian[Q->depan];
if(Q->depan==Q->belakang)//jika hanya 1 elemen
{
Q->depan=-1;
Q->belakang=-1;
}
else
if(Q->depan==Q->maks_queue-1)
Q->depan=0;
else
Q->depan++;
return data;
}
else
{
printf("Queue Kosong.\n");
return 0;
}
}
Cara pemanggilannya adalah :
int data;
data=dequeue(&Q); //ambil data dari dequeue pada queue Q