Queue (Antrian)

3. Queue (Antrian)
3.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

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
Next : address >

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)
3.2. Traversal pada Queue
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.
3.3. Search pada Queue
Pada Queue, elemen yang diproses hanyalah elemen pada pertama dan terakhir. Maka hampir tidak pernah dilakukan search.

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 :

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



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


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.

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.



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

Deskripsi
If IsQEmpty(Q) then
Head(Q) ← P
Tail(Q) ← P
else
Next(Tail(Q)) ← P
Tail(Q) ← P
endif



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


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


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.

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.


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



P ← Head(Q)
Head(Q) ← Next(Head(Q))
if (Head(Q) = Nil) then
Tail(Q) ← Nil
endif
Next(P) ← Nil

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


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)


Bagian Deklarasi dari algoritma pada Queue :
Deklarasi
type InfoType = … {Sebuah type terdefinisi}
type Address pointer to ElmtQ
type ElmtQ = record
Next : Address >
type Queue = record Tail : Address>
{Deklarasi Nama Peubah}
Q : Queue
P : Address
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?


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.

untuk mendowndloadnya silahkan klik pada menu diatas atau disini..