ANTRIAN ( QUEUE ) NAMA KELOMPOK : 1.EKA PRIHANTORO 2.FATKHUL ELEKTRIK PSH 3.RIZKY GUMILANG CR
• Jenis struktur data antrian sering digunakan untuk menstimulasikan keadaan dunia nyata. Antrian banyak dijumpai dalam kehidupan sehari-hari. Misal : antrian registrasi mahasiswa, tiket kereta api dan lain-lain. • Pengertian Antrian : Adalah suatu kumpulan data yang mana penambahan data / elemen hanya dapat dilakukan pada sisi belakang sedangkan penghapusan / pengeluaran elemen dilakukan pada sisi depan. • Berbeda dg stack, prinsip yg digunakan dalam antrian adalah FIFO ( First In First Out ) • Dengan kata lain, urutan keluar elemen akan sama dengan urutan masuknya.
• Dalam antrian tidak semuanya dilakukan secara FIFO murni, contoh yg relevan dalam bidang komputer adalah Time-sharing Computer System, dimana ada sejumlah penakai ( user ) yg menggunakan sistem tsb secara serempak. Karena sistem ini biasanya menggunakan processor, dan sebuah memory utama. Jika processor sedang dipakai oleh seorang user, maka user yang lain harus antri sampai gilirannya. • Antrian ini tidak akan dilayani secara FIFO murni tetapi biasanya didasarkan pada suatu prioritas tertentu. • Antrian yang memasukkan unsur prioritas dinamakan dengan ANTRIAN PRIORITAS ( PRIORITY QUEUE )
Implementasi Antrian dengan menggunakan Array Keluar
Masuk
A B C
Depan
Belakang
Tambahkan 2 elemen baru yaitu ‘D’ dan ‘E’ ke dalam antrian Keluar
A B C
Depan
D E
Belakang
Masuk
Hapus / keluarkan 1 elemen dari antrian Keluar
B C
Depan
D E
Masuk
Belakang
Deklarasi Antrian dengan Menggunakan ARRAY : CONST Maks_elemen = 6 ; TYPE antrian = array [1 .. Maks_elemen] of char ; VAR Q : Antrian ; Depan, belakang : byte ; x : char ; dimana x adalah elemen yg akan dimasukkan ke dalam antrian
• Keadaan awal suatu antrian Depan = 1 Antrian ( Q )
Belakang = 0 Blk = Blk + 1
• Untuk melakukan operasi pada antrian dapat dilakukan dg beberapa cara : • Cara 1 : 1. Operasi penambahan elemen ke dalam antrian : a. Belakang := Belakang + 1; misal. Tambahkan 1 elemen baru (x) = ‘A’ Belakang := Belakang + 1 := 0 + 1 := 1 Antrian (Q) Depan = 1 Belakang = 1
• B. Q[Belakang]:=x; Q[1]:= ‘A’
Antrian (Q) Depan = 1 Belakang = 1 A
ex. Tambahkan 1 elemen baru (x)= ‘B’ Belakang := Belakang + 1 := 1 + 1 Antrian (Q) := 2 Depan = 1 Belakang = 2 B A
C. Q[Belakang]:=x; Q[2]:= ‘B’ Tambahkan 4 elemen baru (x)= ‘B’ , ‘C’ , ‘D’ , ‘E’ , ‘F’ Masukkan elemen ‘C’ Belakang:=3 , depan:=1 Masukkan elemen ‘D’ Belakang:=4 , depan:=1 Masukkan elemen ‘E’ Belakang:=5 , depan:=1 Masukkan elemen ‘F’ Belakang:=6 , depan:=1 Antrian (Q) F
Kondisi terakhir
E
Belakang = 6
D C B A
Depan = 1
ANTRIAN PENUH JIKA BELAKANG = MAKS_ELEMEN
Jumlah elemen yg ada dalam antrian = Belakang – Depan + 1
2. Operasi penghapusan elemen dari antrian Rumus yg digunakan : Y := Q[depan] ; Depan := Depan + 1 ; example : - Hapus/keluarkan 1 elemen dari antrian Y := Q[Depan]; Y := Q[1]; Y := ‘A’;
C B
C B
Belakang = 3
A
Depan = 1
C
Belakang = 3 Depan = 2
Belakang = 3 Depan = 1
Depan := Depan + 1; := 1 + 1; := 2 B
- Hapus/keluarkan lg utk 2 elemen berikutnya dr antrian yaitu keluarkan elemen ‘B’ Depan = 2+1=3 , Belakang = 3 ‘C’ Depan = 3+1=4 , Belakang = 3 C
Belakang = 3 , Depan=3
keluarkan ‘B’
keluarkan ‘C’
Antrian kosong = Depan > Belakang Kelemahan cara 1 : elemen baru tdk bisa ditambahkan lagi, karena nilai belakang = maks_elemen (antrian penuh) walaupun masih ada tempat / lokasi antrian yg kosong.
• Cara II Array yg bergeser 1. Operasi penambahan elemen kedalam antrian a. Belakang := Belakang + 1 ; b. Q[Belakang] := x ; 2. Operasi pengurangan elemen dari antrian a. Y :=Q[Depan] atau Y:Q[1]; b. for K:=1 to belakang-1 DO pengulangan u pergeseran Q[K] := Q[K+1]; elemen Antrian (Q)
C B
Belakang = 3 Depan = 1
• 2) Operasi penghapusan elemen pd antrian Y:=Q[depan]; if depan=maks_elemen then depan:=1 else depan:=depan+1;
- Hapus/keluarkan 1 elemen dari antrian a.
Y := Q[Depan]; Y := Q[1]; Y := ‘A’;
For K:=1 to belakang-1 := 1 to 3-1 := 1 to 2 K=1 Q[K]:= Q[K+1] Q[1]:=Q[2] :=‘B’ K=2 Q[K]:=Q[K+1] Q[2]:=Q[3] Q[2]:=‘C’ Belakang:=belakang-1 = 3-1 = 2
C B
C B
C B
Belakang = 3 Depan = 1
Belakang = 3 Depan = 1
Belakang = 2 Depan = 1
• Kelemahan cara 2 : Untuk data yang banyak maka harus banyak terjadi proses pergeseran atau untuk jumlah elemen yg besar akan memerlukan waktu yg lama untuk melakukan pergeseran elemen. ex : 1000 elemen menjadi 999 pergeseran
• 1). Operasi penambahan & penghapusan elemen procedure TAMBAH ; if belakang < maks_elemen then belakang := belakang + 1 ; Q[belakang] := x ; else writeln (‘Full Queue’); end; procedure HAPUS ; Y:=Q[depan]; depan:=depan + 1 for K:=1 to belakang-1 DO Q[K] := Q[K+1]; end;
pd antrian
Gambarkan keadaan antrian untuk melakukan operasi penambahan & penghapusan elemen ( elemen no. ujian ). Diasumsikan keadaan awal antrian=kosong, dan antrian tsb dpt menampung maks_elemen = 4, dg operasi : a) tambahkan 3 elemen pd antrian (31001, 31002, 31003 ) b) hapus 1 elemen dr antrian c) tambah 1 elemen dr antrian (31004) d) tambahkan 1 elemen berikutnya (31005)
