Pencarian

TUGAS TUGAS KULIAH

KUMPULAN TUGAS TUGAS KULIAH

TUGAS STRUCTUR DATA

Monday 20 January 2014




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;
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.















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 :-)

 



Blogger news

Powered by Blogger.

Pages

Blogroll

Most Reading

AWAS