4. queue (antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf ·...
TRANSCRIPT
1
4. Queue (Antrian) 4.1. Definisi
Queue (Antrian) adalah list linier yang :
1. Dikenali elemen pertama (Head) dan elemen terakhirnya (Tail)
2. Aturan penyisipan dan penghapusan elemennya disefinisikan sebagai berikut :
- Penyisipan selalu dilakukan setelah elemen terakhir
- Penghapusan selalu dilakukan pada elemen pertama
3. Satu elemen dengan elemen lain dapat diakses melalui informasi Next
2
Struktur data ini banyak dipakai dalam informatika
misalnya untuk merepresentasi :
1. Antrian job dalam sistem operasi
2. Antrian dalam dunia nyata
Maka secara lojik, sebuah Queue dapat digambarkan
sebagai list linier yang setiap elemennya adalah :
Type ElmtQ = record
<Info : InfoType,
Next : address >
3
dengan InfoType terdefinisi yang menentukan
informasi yang disimpan pada setiap elemen
queue, dan address adalah “alamat” dari
elemen
Selain itu alamat elemen Pertama (Head) dan elemen
terakhir (Tail) dicatat.
Maka jika Q adalah Queue dan P adalah Address,
penulisan untuk Queue adalah :
Head(Q)
Tail(Q)
Next(P)
Info(P)
4
Pada queue, jarang sekali dilakukan traversal, karena keunikan Queue justru pada operasi yang hanya menyangkut elemen pertama dan terakhir. Namun dibutuhkan traversal misalnya untuk mencetak isi Antrian.
4.3. Search pada Queue Pada Queue, elemen yang diproses hanyalah
elemen pada pertama dan terakhir. Maka hampir tidak pernah dilakukan search.
4.2. Traversal pada Queue
5
3.4. Operasi dan fungsi dasar pada
Queue.
a. Test Queue kosong
Mengetahui bahwa Queue kosong atau tidak
sangat penting, sebab semua operasi akan
dilakukan berdasarkan kosong atau tidaknya
suatu Queue. Realisasi algoritma dari definisi
fungsional ini adalah sebuah fungsi yang
melakukan test terhadap Queue sebagai berikut :
6
function IsQEmpty (Q : Queue) → Boolean
{ TEST Queue kosong : Mengirim true, jika
antrian kosong, false jika antrian tidak kosong}
{Deklarasi}
{Deskripsi}
return ((Head(Q) = Nil) and (Tail(Q) = Nil))
7
b. Pembuatan Queue kosong
Membuat Queue kosong diperlukan untuk memulai memakai Queue. Realisasi algoritma dari definisi fungsional ini adalah sebuah prosedur yang melakukan inisialisasi Queue sebagai berikut :
Procedure CreateEmptyQ (Output Q : Queue)
{K. Awal : sembarang,
K. Akhir : sebuah queue Q yang kosong terbentuk
Proses : Membuat queue kosong }
{Deklarasi}
{Deskripsi}
Head(Q) ← Nil
Tail(Q) ← Nil
8
c.Penambahan sebuah elemen pada
Queue
Penambahan selalu dilakukan pada ekor,
dan karena alamat ekor diketahui maka
prosesnya sederhana, yaitu hanya
InsertLast.
Berikut ini akan diberikan skema prosedur
penyisipan tersebut.
9
Realisasi algoritma dari definisi fungsional ini
adalah salah satu dari dua buah prosedur
yang melakukan penambahan elemen
Queue sebagai berikut :
Prosedur pertama menambahkan suatu
Elemen Queue yang diketahui alamatnya
dan yang kedua menambahkan suatu nilai
Elemen queue yang diberikan.
10
procedure InsertQ@ (Input/Output Q : Queue Input P : address)
{K.Awal : Queue mungkin kosong, P terdefinisi (berarti terdefinisi informasinya, Next (P) = Nil
K.Akhir : P menjadi elemen Tail dari Q dan Tail yang baru adalah P
Proses : Insert sebuah elemen beralamat P pada Tail dari antrian Q }
{Deklarasi}
11
{Deskripsi}
If IsQEmpty(Q) then
Head(Q) ← P
Tail(Q) ← P
else
Next(Tail(Q)) ← P
Tail(Q) ← P
endif
12
procedure InsertQ(Input/Output Q : Queue
Input E : InfoType)
{K.Awal : Queue mungkin kosong, E
terdefinisi
K.Akhir : Elemen Tail dari Q yang baru
bernilai E
Proses : Insert sebuah elemen nilai pada
Tail dari antrian Q }
{Deklarasi}
13
{Deskripsi}
Alokasi (P)
Info (P) ← E
If IsQEmpty(Q) then
Head(Q) ← P
Tail(Q) ← P
else
Next(Tail(Q)) ← P
Tail(Q) ← P
endif
14
d. Penghapusan Elemen Pada QueuE
Penghapusan elemen pada queue selalu
dilakukan pada elemen pertama, hanya saja perlu
diperhitungkan bahwa mungkin queue menjadi
kosong akibat terjadinya penghapusan. Jika
queue menjadi kosong, maka harga Tail harus
diganti. Jika akibat penghapusan queue tidak
kosong, maka elemen terakhir tidak berubah.
15
Berikut adalah skema penghapusan tersebut.
Prosedur pertama melakukan penghapusan
ElmtQ yang berada di Head danyang dicatat
adalah alamatnya, yaitu P. Prosedur yang kedua
menghapus elemen Head dari queue dan
menyimpannya pada suatu elmtQ serta
membebaskan alamat yang tadinya dipakai oleh
elemen Head tersebut.
16
procedure DeleteQ@(Input/Output Q : Queue
Output P : address)
{K.Awal : Queue tidak kosong
K.Akhir : P bukan lagi elemen dari Q, P ≠ Nil,
Next(P) = Nil
Proses : Menghapus elemen Head dari antrian,
antrian tidak boleh kosong dan
mungkin menjadi kosong }
{Deklarasi}
{Deskripsi}
17
P ← Head(Q)
Head(Q) ← Next(Head(Q))
if (Head(Q) = Nil) then
Tail(Q) ← Nil
endif
Next(P) ← Nil
18
procedure DeleteQ(Input/Output Q : Queue Output E : InfoType)
{K.Awal : Queue tidak kosong
K.Akhir : Jika P adalah Head(Q). P bukan lagi elemen dari Q, P ≠ Nil, Next(P) = Nil
Proses : Menghapus elemen Head dari antrian, antrian tidak boleh kosong dan mungkin menjadi kosong }
{Deklarasi}
{Deskripsi}
19
P ← Head(Q)
E ← Info(Head(Q))
Head(Q) ← Next(Head(Q))
if (Head(Q) = Nil) then
Tail(Q) ← Nil
endif
Next(P) ← Nil
Dealokasi(P)
20
Bagian Deklarasi dari algoritma pada Queue :
{Deklarasi}
type InfoType = … {Sebuah type terdefinisi}
type Address pointer to ElmtQ
type ElmtQ = record
<Info : InfoType,
Next : Address >
type Queue = record <Head : Address,
Tail : Address>
{Deklarasi Nama Peubah}
Q : Queue
P : Address
21
Soal-Soal
1. Mengapa cara penyusunan elemen pada Queue
sering disebut tersusun secara FIFO?
2. Mengapa pada Queue Traversal dan Search
jarang dilakukan?
3. Penghapusan elemen pada Queue selalu
dilakukan pada elemen yang paling depan,
bagaimana jika terpaksa harus menghapus
elemen yang paling belakang?
22
4. Buatlah sebuah fungsi untuk menghitung jumlah
elemen queue yang ganjil, jika diketahui sebuah queue
dengan elemen bertype integer.
5. Buatlah fungsi/prosedur untuk mencetak elemen queue
yang genep
6. Buatlah juga fungsi untuk menghitung rata-rata elemen
queue yang ganjil
7. Buatlah sebuah fungsi untuk mengirimkan elemen
pertama queue
8. Buatlah sebuah fungsi untuk mengirimkan elemen
queue yang maksimum jika diketahui elemen queue
terurut membesar dan bertype integer