Makalah Queue

MAKALAH QUEUE

ALGORITMA DAN STRUKTUR DATA

 

Oleh   : Irwan Darmawan ( 140403020021 )

UNIVERSITAS KANJURUHAN MALANG

SISTEM INFORMASI 2014

 

KATA PENGANTAR

Puji syukur saya panjatkan ke hadirat Tuhan Yang Maha Esa, karena dengan karunianya penulis dapat menyelesaikan makalah yang berjudul “Queue” ini. Tujuan penulisan makalah ini adalah untuk menyelesaikan tugas mata kuliah  Algoritma dan Struktur Data.

Saya menyadari bahwa makalah ini masih jauh dari sempurna, oleh karena itu kritik dan saran dari semua pihak yang bersifat membangun selalu saya harapkan demi kesempurnaan makalah ini.

Akhir kata, saya sampaikan terima kasih kepada semua pihak yang telah berperan serta dalam penyusunan makalah ini dari awal sampai akhir. Semoga Tuhan Yang Maha Esa senantiasa meridhoi segala usaha kita. Aamiin.

Hormat Saya,

 

. 10

 

BAB I

PENDAHULUAN

A.   Latar Belakang

Dalam kehidupan sehari-hari kita pasti pernah menjumpai atau melakukan yang nama antrian, misal saat mengantri di loket kereta, di teller bank, di rumah sakit, dll. Kita pasti melakukan yang namanya antrian. Oleh karena itu di sini akan dibahas tentang antrian di pemrograman java yang tujuannya memudahkan dan membantu kita pada kehidupan sehari-hari.

B.   Rumusan Masalah

Dari uraian latar belakang di atas dapat ditarik rumusah masalah yaitu :

1.       Apakah Queue itu ?

2.       Bagaimana implementasi Queue dengan Linear Array ?

3.       Bagaimana implementasi Queue dengan Circullar Array ?

C.   Tujuan

Tujuan dari pembuatan makalah ini adalah :

1.       Queue adalah !

2.       Implementasi Queue dengan Linear Array adalah !

3.       Implementasi Queue dengan Circullar Array adalah !

BAB II

PEMBAHASAN

A.   QUEUE / ANTRIAN

 

Secara harfiah queue dapat diartikan sebagai antrian. Queue merupakan kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head). Berbeda dengan stack yang bersifat LIFO maka queue bersifat FIFO (First In First Out), yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir. Berikut ini adalah gambaran struktur data queue.

Elemen yang pertama kali masuk ke dalam queue disebut elemen depan (front/head of queue), sedangkan elemen yang terakhir kali masuk ke queue disebut elemen belakang (rear/tail of queue). Perbedaan antara stack dan queue terdapat pada aturan penambahan dan penghapusan elemen. Pada stack, operasi penambahan dan penghapusan elemen dilakukan di satu ujung. Elemen yang terakhir kali dimasukkan akan berada paling dekat dengan ujung atau dianggap paling atas sehingga pada operasi penghapusan, elemen teratas tersebut akan dihapus paling awal, sifat demikian dikenal dengan LIFO. Pada queue, operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu dilakukan melalui salah satu ujung, menempati posisi di belakang elemen-elemen yang sudah masuk sebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan. Sifat yang demikian dikenal dengan FIFO.

Operasi‐operasi standar pada queue adalah: 

1.       Membuat queue atau inisialisasi.

2.       Mengecek apakah queue penuh.

3.       Mengecek apakah queue kosong.

4.       Memasukkan elemen ke dalam queue atau InQueue (Insert Queue).

5.       Menghapus elemen queue atau DeQueue (Delete Queue).

 

B.   Implementasi Queue dengan Linear Array

Disebut juga queue dengan model fisik, yaitu bagian depan queue selalu menempati posisi pertama array. Queue dengan linear array secara umum dapat dideklarasikan sebagai berikut:

Const MaxQueue = {jumlah}; Type TypeQueue = byte; Var Queue : Array[1..MaxQueue] of TypeQueuel Head, Tail   : Byte;

Operasi‐operasi queue dengan linear array:

1.       Create

Procedure create berguna untuk menciptakan queue yang baru dan kosong yaitu dengan cara memberikan nilai awal (head) dan nilai akhir (tail) dengan nol (0). Nol menunjukan bahwa queue masih kosong.

Procedure Create; Begin Head := 0; Tail := 0; End;

2.       Empty

Function empty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah tail bernilai nol atau tidak, jika ya maka kosong.

Function Empty : Boolean; Begin If Tail = 0 then Empty := true Else Empty := False; End;

3.       Full

Function Full : Boolean; Begin If Tail = MaxQueue then Full := true Else Full := False End;

4.       EnQueue

Procedure EnQueue berguna untuk memasukkan 1 elemen ke dalam queue.

Procedure Enqueue(Elemen : Byte); Begin If Empty then Begin Head := 1; Tail := 1; Queue[head] := Elemen; End Else If Not Full then Begin Inc(Tail); Queue[tail] := Elemen; End; End;

5.       DeQueue

Procedure DeQueue berguna untuk mengambil 1 elemen dari Queue, operasi ini sering disebut juga SERVE. Hal ini dilakukan dengan cara memindahkan semua elemen satu langkah ke posisi di depannya, sehingga otomatis elemen yang paling depan akan tertimpa dengan elemen yang terletak dibelakangnya.

Procedure DeQueue; Var I : Byte; Begin If Not Empty then Begin For I := Head to Tail‐1 do Queue[I] := Queue[I+1]; Dec(Tail); End; End;

6.       Clear

Procedure clear berguna untuk menghapus semua elemen dalam queue dengan jalan mengeluarkan semua elemen tersebut satu per satu sampai kosong dengan memanfaatkan procedure DeQueue.

Procedure Clear; Begin While Not Empty then DeQueue; End;

C.   Implementasi Queue dengan Circular Array

Salah satu variasi array adalah array melingkar (circular array), artinya array dapat diakses mulai dari sembarang indeks (indeks awal) ke arah indeks terakhir (maksimum array), lalu memutar ke indeks pertama hingga kembali ke indeks awal. Circular array adalah array yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika array tersebut masih kosong. Jumlah data yang dapat ditampung oleh array ini adalah besarnya ukuran array dikurangi 1. Misalnya besar array adalah 8, maka jumlah data yang dapat ditampung adalah 7.

Dengan circular array, meskipun posisi terakhir telah terpakai, elemen baru tetap dapat ditambahkan pada posisi pertama jika posisi pertama dalam keadaan kosong. Jika akhir=MAX dan awal=1, nilai head dan tail mencapai maksimum, maka akan dikembalikan ke posisi awal. Operasi-operasi yang terdapat pada circular array tidak jauh berbeda dengan operasi pada linear array.

Operasi‐operasi queue dengan circular array:

1.       Create

Procedure Create; Begin Head := 1; Tail := MaxQueue; End;

2.       Empty

Function Empty : Boolean; Begin If (Tail Mod Max_Queue ) + 1  = Head then Empty := true Else Empty := False; End;

3.       Full

Function Full : Boolean; Var X : 1 .. Max_queue; Begin X := (Tail Mod Max_queue)+1; If (x Mod Max_queue) + 1 = head then Full := True; Else Full := False; End;

4.       EnQueue

Procedure EnQueue (Elemen : TypeElemen); Begin If Not Full Then Begin Tail := (Tail Mod Max_queue) + 1 ; Queue[Tail] := Elemen; End; End;

5.       DeQueue

Procedure Dequeue; Begin If Not Empty then Head := (Head Mod Max_queue) + 1; End

BAB III

PENUTUP

Alhamdulilahi Robbil ‘Alamin, makalah ini telah selesai dibuat. Diharapkan penulis makalah ini akan bermanfaat bagi pembaca, Terima Kasih diucapkan kepada semua pihak. Assalamu’alaikum Wr. Wb.