4. queue (antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf ·...

22
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

Upload: trantu

Post on 11-Apr-2019

248 views

Category:

Documents


1 download

TRANSCRIPT

Page 1: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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

Page 2: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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 >

Page 3: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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)

Page 4: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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

Page 5: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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 :

Page 6: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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

Page 7: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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

Page 8: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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.

Page 9: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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.

Page 10: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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}

Page 11: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

11

{Deskripsi}

If IsQEmpty(Q) then

Head(Q) ← P

Tail(Q) ← P

else

Next(Tail(Q)) ← P

Tail(Q) ← P

endif

Page 12: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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}

Page 13: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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

Page 14: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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.

Page 15: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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.

Page 16: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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}

Page 17: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

17

P ← Head(Q)

Head(Q) ← Next(Head(Q))

if (Head(Q) = Nil) then

Tail(Q) ← Nil

endif

Next(P) ← Nil

Page 18: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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}

Page 19: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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)

Page 20: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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

Page 21: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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?

Page 22: 4. Queue (Antrian) - si.ilkom.unsri.ac.idsi.ilkom.unsri.ac.id/wp-content/uploads/2018/11/4.pdf · Queue (Antrian) 4.1. Definisi Queue (Antrian) adalah list linier yang : 1. Dikenali

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