MAKALAH QUEUE
(ANTRIAN)
Diajukan Sebagai Salah Satu Syarat
Untuk
Memenuhi Tugas Mata Kuliah Struktur Data
Disusun Oleh :
Nama
Kelompok : Wahyu Kristiani (14.11.0026_ SI)
Feri
Wiyanto
Takdir
Bangkit
Mikael
QUEUE
(ANTRIAN)
Pengertian Queue (Antrian)
Queue
/ Antrian adalah suatu kumpulan data yang mana penambahan elemen hanya bisa
dilakukan pada satu ujung (disebut dengan sisi belakang atau rear) dan
penghapusan atau pengambilan elemen dilakukan lewat ujung lain (disebut dengan
sisi depan atau front).
Antrian
menggunakan prinsip Pertama Masuk Pertama Keluar – First In First Out (FIFO).
Dengan kata lain urutan masuk sama dengan urutan keluar. Antrian banyak
dijumpai dalam kehidupan sehari-hari. Mobil-mobil yang mengantri digerbang tol
untuk membeli karcis tol; orang-orang yang mengantri di loket untuk membeli
karcis film juga membentuk antrian.
Pada
antrian kita tidak menentukan batasan seberapa banyak antrian itu akan berakhir
tapi jika kita menggunakan array untuk mengimplementasikan queue/ tumpukan kita
harus membatasi jumlah antrian yang dapat masuk. Ini dikarenakan array memiliki
batasan (upperbound) yang menjadi penghambat jika kita menggunakan antrian.
Oleh sebab itu kita akan mengimplementasikan antrian ini dengan menggunakan
link list.
Dengan menggunakan link list tepatnya Single Link List maka
elemen dapat dimasukkan secara tidak terbatas. Kita menggunakan Header Single
Link List yang seperti Stack pada
posisi Header dapat kita pergunakan untuk menyimpan informasi mengenai
banyaknya elemen dalam Queue.
Notasi
Pada Queue
Notasi yang dapat
digunakan didalam Queue Q adalah :
1. FRONT(Q) menunjukkan posisi terdepan dari suatu antrian. Contoh jika kita mempunyai antrian Q =
[A,B,C,D,E] maka FRONT(Q) = A.
2. REAR(Q) menunjukkan posisi terakhir dari suatu antrian. Contoh jika kita mempunyai antrian Q =
[A,B,C,D,E] maka REAR(Q) = E.
3. NOEL(Q) menunjukkan jumlah elemen di
dalam Antrean Q. Contoh jika kita mempunyai antrian Q = [A,B,C,D,E] maka
NOEL(Q) = 5
Deklarasi
Queue Dalam Link List
Pendeklarasian
Queue di dalam link list sama seperti kita mendeklarasikan link
list.
Menggunakan pointer sebagai variabel yang menunjuk ke elemen antrian
selanjutnya.
Deklarasi Queue menggunakan Linked List
di dalam Pascal :
Type
Queue = ^Simpul
Simpul =
Record
Info
: Char;
Next
: Queue;
End;
Var
Head,
Tail : Queue;
Max :
Byte;
Link
list yang kita gunakan ialah jenis Header Single Link List. Kita
menggunakan jenis link list ini karena pada bagian header
dapat kita manfaatkan
untuk menyimpan informasi mengenai banyaknya elemen dalam
Antrian
(NOEL(Q)).
Operasi
Dasar Pada Queue
Ada 4 operasi dasar yang dapat dilakukan pada struktur data
antrian, yaitu:
1.
CREATE(Q)
CREATE(Q) adalah suatu
operator yang digunakan untuk membentuk dan menunjukkan suatu antrian hampa.
Contoh :
NOEL(CREATE(Q))
= 0 FRONT(CREATE(Q)) = Tidak Terdefinisi REAR(CREATE(Q)) = Tidak Terdefinisi
Berikut
ini merupakan procedure CREATE simpul pada Pascal :
Procedure
CREATE(Var Head, Tail : Queue);
Begin
New(Head);
Head^.Info
:= 0;
Head^.Next
:= Head;
Tail :=
Head;
End;
2. ISEMPTY(Q)
ISEMPTY(Q) adalah operator yang menentukan apakah antrian Q
hampa atau tidak. ISEMPTY(Q) di terapkan di dalam pascal menjadi sebuah
function yang bertipe boolean sehingga hasil dari function ini akan bernilai
True jika antrian dalam keadaan kosong / hampa (NOEL(Q) = 0) dan akan bernilai
False jika antrian dalam keadaan terisi / tidak kosong (NOEL(Q) > 0). Contoh:
ISEMPTY(CREATE(Q)) =
True
Berikut ini merupakan procedure ISEMPTY simpul pada Pascal :
Function
ISEMPTY(Head : Queue);
Begin
ISEMPTY :=
(Head^.Next = Head);
End;
3. INSERT(E,Q)
INSERT(E,Q) adalah
operator yang digunakan untuk memasukkan elemen E pada antrian Q di posisi
depan dari antrian. Hasil dari operator ini adalah antrian yang lebih panjang.
Berikut ini merupakan
procedure INSERT simpul pada Pascal :
Procedure
INSERT(Elemen : Byte; Var Head, Tail : Queue);
Var
Temp : Queue;
Begin
New(Temp);
Temp^.Info
:= Elemen;
Temp^.Next
:= Head;
Tail :=
Temp;
Inc(Head^.Info);
End;
4. REMOVE(Q)
REMOVE(Q) adalah
operator yang menghapus elemen bagian depan dari antrian Q. Hasilnya merupakan
antrian yang lebih pendek. Pada setiap operasi ini, harga dari NOEL(Q)
berkurang satu, dan elemen kedua dari Q menjadi elemen terdepan. Jika NOEL(Q) =
0, maka REMOVE(Q) memberikan suatu kondisi erroe, yakni suatau UNDERFLOW.
Contoh :
REMOVE(CREATE(Q)) = UNDERFLOW.
Berikut ini merupakan procedure REMOVE
simpul pada Pascal :
Procedure REMOVE(Var Head : Queue);
Var Temp : Queue;
Begin
If
Not (ISEMPTY(Head)) Then Begin
Temp :=
Head^.Next; Head^.Next := Temp^.Next; Dispose(Temp); Dec(Head^.Info);
End;
End;
Untuk memahami
pengertian antrian sekaligus penerapan operator-operator queue dan
notasi-notasinya perhatikan ilustrasi berikut :
CREATE(Q) = Membuat Antrian Baru
FRONT(Q)
= Tidak Terdefinisi
=
Q REAR(Q) =
Tidak Terdefinisi
NOEL(Q)
= 0
ISEMPTY(Q) = Apakah Antrian dalam keadaan kosong ?
|
FRONT(Q)
= Tidak Terdefinisi
|
TRUE
|
= Q REAR(Q) =
Tidak Terdefinisi
|
|
NOEL(Q)
= 0
|
REMOVE(Q) = Mengeluarkan elemen terdepan dari dalam antrian.
FRONT(Q) = Tidak
Terdefinisi
UNDERFLOW !!! =
Q REAR(Q)
= Tidak Terdefinisi
NOEL(Q)
= 0
INSERT(1,Q)
= Memasukkan elemen 1 kedalam antrian.
|
FRONT(Q) = 1
|
1
|
= Q REAR(Q) =
1
|
|
NOEL(Q)
= 1
|
INSERT(2,Q)
= Memasukkan elemen 2 kedalam antrian.
|
FRONT(Q) = 1
|
1 2
|
= Q REAR(Q) =
2
|
|
NOEL(Q)
= 2
|
INSERT(3,Q)
= Memasukkan elemen 3 kedalam antrian.
|
FRONT(Q) = 1
|
1 2 3
|
= Q REAR(Q) =
3
|
|
NOEL(Q)
= 3
|
REMOVE(Q) = Mengeluarkan elemen terdepan dari dalam antrian.
|
FRONT(Q) = 2
|
2 3
|
= Q REAR(Q) =
3
|
|
NOEL(Q)
= 2
|
INSERT(4,Q) = Memasukkan elemen 3 kedalam antrian.
|
FRONT(Q) = 2
|
2 3 4
|
= Q REAR(Q) =
4
|
|
NOEL(Q)
= 3
|
ISEMPTY(Q)
= Apakah Antrian dalam keadaan kosong ?
|
FRONT(Q) =
Tidak Terdefinisi
|
FALSE
|
= Q REAR(Q) =
Tidak Terdefinisi
|
|
NOEL(Q)
= 0
|
Untuk
operasi-operasi selanjutnya menggunakan prinsip yang sama seperti ilustrasi
diatas ini.
Jenis-jenis Antrian
Selain
antrian yang telah kita bahas di atas, masih ada dua tipe antrian lagi yang
penggunaannya juga banyak di dalam kehidupan sehari hari atau dalam dunia
komputer itu sendiri, diantaranya adalah :
1.
DEQUE
DEQUE adalah antrian
dimana elemennya bisa masuk dan keluar lewat kedua ujungnya (berbeda dengan
queue yang hanya bisa masuk lewat ujung belakang dan keluar lewat ujung depan).
Biasanya DEQUE disajikan dengan menggunakan Double link list yang memiliki dua
buah pointer yang menunjuk ke posisi sebelumnya dan sesudahnya. Gambar ini
menunjukkan struktur umum dari sebuah DEQUE.
|
|
|
|
|
FRONT(Q)
|
|
|
REAR(Q)
|
|
||||||||||
Keluar
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Masuk
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Masuk
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Keluar
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Gambar
Struktur Umum DEQUE
DEQUE juga mempunyai dua jenis variasi
yaitu :
a.
boleh dilakukan
pada kedua ujung list Deque input terbatas : suatu deque yang membatasi
pemasukkan elemen hanya pada satu ujung dari list, sementara penghapusan elemen
boleh dilakukan pada kedua ujung list.
b.
Deque output terbatas : merupakan kebalikan dari deque
input terbatas yaitu suatu deque yang membatasi penghapusan elemen hanya pada
satu ujung dari list, sementara pemasukkan elemen
2. ANTRIAN BERPRIORITAS
Antrian berprioritas
adalah suatu queue yang setiap elemennya telah diberikan sebuah prioritas, dan
urutan proses penghapusan elemen adalah berdasarkan aturan berikut :
a. Elemen yang prioritasnya lebih tinggi,
diproses lebih dahulu dibandingkan dengan elemen yang prioritas lebih rendah.
b. Dua elemen dengan prioritas yang sama,
diproses sesuai dengan urutan mereka sewaktu dimasukkan ke dalam priority
queue.
Salah satu contoh
antrian berprioritas ini adalah sistem berbagi waktu (time sharing system),
dimana program yang mempunyai prioritas tinggi akan dikerjakan lebih dahulu dan
program-program yang berprioritas sama akan membentuk antrian yang biasa.
program
animation_queue;
uses wincrt;
const max_elemen =10;
type antri = array [1..max_elemen] of char;
var
antrian : antri;
q : antri;
d : char;
isi : antri;
uses wincrt;
const max_elemen =10;
type antri = array [1..max_elemen] of char;
var
antrian : antri;
q : antri;
d : char;
isi : antri;
depan, belakang,
pilih : integer;
elemen : char;
procedure kotak;
var
i: integer;
begin
gotoxy(20,15);
for i:= 1 to max_elemen * 4 + 1 do
write('-');
gotoxy(20,16);
for i:= 1 to max_elemen do
write('| ');
writeln('|');
gotoxy(20,17);
for i:= 1 to max_elemen * 4 +1 do
write('-');
gotoxy(8,16);writeln('<---- br="" out="">
gotoxy(22+max_elemen*4+1,16);
writeln('<---- br="" in="">
end;
procedure letakkan(x: char; r:integer);
begin
gotoxy(18+4*r,16);
write(x);
end;
function kosong(q: antri): boolean;
begin
kosong:=(depan=belakang)
end;
procedure tambah(var antrian: antri;x:char);
begin
if belakang=max_elemen then belakang:=1
else belakang:=belakang+1;
if not (kosong(antrian)) then
begin
antrian[belakang]:=x;
letakkan(x,belakang);
end
else
begin
gotoxy(40,9);
write('OVERFLOW');
repeat
{menunggu sampai ada tombol ditekan}
until keypressed;
gotoxy(40,9);
write(' ':30);
belakang:=belakang-1;
if belakang=0 then
belakang:=max_elemen
end
end;
function qkosong(q:antri):boolean;
begin
qkosong:= (depan = belakang);
end;
procedure Dequeue(var q:antri; ed:char);
begin
if not(qkosong(q)) then
begin
if depan = max_elemen then depan :=1
else depan := depan+1;
ed := isi[depan];
end;
end;
procedure tampil(q: antri);
var i,awal : integer;
begin
CLRSCR;
writeln('Queue to Data');
if depan = max_elemen then awal :=1
else awal := depan +1;
for i:=awal to belakang do
writeln(i:3,' ':5,isi[i],' ');
READLN;
end;
function hapus(var antrian: antri):char;
begin
if depan=max_elemen then
depan:=1
else
begin
depan:=depan+1;
hapus:=antrian[depan]
end
end;
{program utama}
begin
clrscr;
kotak;
depan:=0;
belakang:=0;
repeat
for pilih:=5 to 9 do
begin
gotoxy(40,pilih);write(' ':39);
end;
gotoxy(1,1);
writeln(' MENU ');
writeln('===================');
writeln;
writeln(' 1. Add a New Element (Enqueue)');
writeln(' 2. Vanish An Element (Dequeue) ');
writeln(' 3. FINISH and EXIT');
writeln;writeln;
writeln(' YOURS CHOICE:');
writeln;
write ('-------THANK YOU FOR USING THIS PROGRAM---------');
writeln;
write (' THE PROGRAM CREATED BY ');
writeln;
write (' RAHMAD KURNIAWAN ');
writeln;
write (' http://rahmad.co.nr ');
writeln;
repeat
gotoxy(22,9);writeln(' ');
gotoxy(22,9);readln(pilih);
until (pilih>=1) and(pilih<=3);
case pilih of
1 : begin
gotoxy(40,4);
writeln ('--------------');
gotoxy(40,5);
writeln('ADD AN ELEMENT');
gotoxy(40,6);
writeln('---------------');
gotoxy(40,8);
write('ENTER AN ELEMENT:');
readln(elemen);
tambah(antrian,elemen);
end;
2 : begin
if not(kosong(antrian)) then
begin
Dequeue(q,d);
tampil(q);
end
else
begin
gotoxy (30,9);
writeln ('UNDER FLOW');
elemen:=readkey;
gotoxy (30,9);write (' ':30);
end
end
end;
until pilih=3
end.---->---->
elemen : char;
procedure kotak;
var
i: integer;
begin
gotoxy(20,15);
for i:= 1 to max_elemen * 4 + 1 do
write('-');
gotoxy(20,16);
for i:= 1 to max_elemen do
write('| ');
writeln('|');
gotoxy(20,17);
for i:= 1 to max_elemen * 4 +1 do
write('-');
gotoxy(8,16);writeln('<---- br="" out="">
gotoxy(22+max_elemen*4+1,16);
writeln('<---- br="" in="">
end;
procedure letakkan(x: char; r:integer);
begin
gotoxy(18+4*r,16);
write(x);
end;
function kosong(q: antri): boolean;
begin
kosong:=(depan=belakang)
end;
procedure tambah(var antrian: antri;x:char);
begin
if belakang=max_elemen then belakang:=1
else belakang:=belakang+1;
if not (kosong(antrian)) then
begin
antrian[belakang]:=x;
letakkan(x,belakang);
end
else
begin
gotoxy(40,9);
write('OVERFLOW');
repeat
{menunggu sampai ada tombol ditekan}
until keypressed;
gotoxy(40,9);
write(' ':30);
belakang:=belakang-1;
if belakang=0 then
belakang:=max_elemen
end
end;
function qkosong(q:antri):boolean;
begin
qkosong:= (depan = belakang);
end;
procedure Dequeue(var q:antri; ed:char);
begin
if not(qkosong(q)) then
begin
if depan = max_elemen then depan :=1
else depan := depan+1;
ed := isi[depan];
end;
end;
procedure tampil(q: antri);
var i,awal : integer;
begin
CLRSCR;
writeln('Queue to Data');
if depan = max_elemen then awal :=1
else awal := depan +1;
for i:=awal to belakang do
writeln(i:3,' ':5,isi[i],' ');
READLN;
end;
function hapus(var antrian: antri):char;
begin
if depan=max_elemen then
depan:=1
else
begin
depan:=depan+1;
hapus:=antrian[depan]
end
end;
{program utama}
begin
clrscr;
kotak;
depan:=0;
belakang:=0;
repeat
for pilih:=5 to 9 do
begin
gotoxy(40,pilih);write(' ':39);
end;
gotoxy(1,1);
writeln(' MENU ');
writeln('===================');
writeln;
writeln(' 1. Add a New Element (Enqueue)');
writeln(' 2. Vanish An Element (Dequeue) ');
writeln(' 3. FINISH and EXIT');
writeln;writeln;
writeln(' YOURS CHOICE:');
writeln;
write ('-------THANK YOU FOR USING THIS PROGRAM---------');
writeln;
write (' THE PROGRAM CREATED BY ');
writeln;
write (' RAHMAD KURNIAWAN ');
writeln;
write (' http://rahmad.co.nr ');
writeln;
repeat
gotoxy(22,9);writeln(' ');
gotoxy(22,9);readln(pilih);
until (pilih>=1) and(pilih<=3);
case pilih of
1 : begin
gotoxy(40,4);
writeln ('--------------');
gotoxy(40,5);
writeln('ADD AN ELEMENT');
gotoxy(40,6);
writeln('---------------');
gotoxy(40,8);
write('ENTER AN ELEMENT:');
readln(elemen);
tambah(antrian,elemen);
end;
2 : begin
if not(kosong(antrian)) then
begin
Dequeue(q,d);
tampil(q);
end
else
begin
gotoxy (30,9);
writeln ('UNDER FLOW');
elemen:=readkey;
gotoxy (30,9);write (' ':30);
end
end
end;
until pilih=3
end.---->---->
Daftar
Pustaka
1. http://www.fery-wiyanto.blogspot.com
2.
Modul Praktikum Struktur Data –
IT045329
No comments:
Post a Comment
Hay,,
yang mampir ke Blog saya wajib Koment ya,,
hehehe :-)