Queue Queue (antrian) adalah kumpulan data yang penambahan elemennya dilakukan pada suatu ujung (bagian belakang) dan penghapusannnya dilakukan pada ujung yang lain (bagian depan). Prinsip ini biasa juga disebut dengan First In First Out (masuk pertama keluar pertama). Dengan kata lain urutan keluar suatu elemen data urutannya sama dengan urutan masuknya.
Implementasi Queue dengan Array Seperti dijelaskan sebelumnya, queue adalah kumpulan data. Untuk mengimplementasikan kumpulan data biasanya kita menggunakan array. Array dapat digunakan untuk menyimpan data dan dengan dua variabel yang berisi nilai index kepala dan ekor queue. Dua index penunjuk ini berguna ketika akan dilakukan penambahan dan penghapusan. Pada gambar 1 dapat dilihat struktur queue dengan dua penunjuk.
Gambar 1. Queue
Pada queue dikenal dua operasi dasar yaitu penambahan dan penghapusan. Penambahan akan mengubah nilai dari ekor. Pada saat data ditambahkan, nilai ekor akan menuju index berikutnya (jika tidak penuh) lalu mengisi data pada tempat tersebut. Jika terjadi penghapusan maka data yang akan dihapus adalah data yang ditunjuk oleh index kepala. Hal ini memperjelas penggunaan FIFO dalam queue. Jika kita mengimplementasikan queue dengan array penambahan data terbatas pada ukuran array yang digunakan. Hal lain yang harus diperhatikan adalah pada saat penghapusan data. Pada saat penghapusan data, harus terdapat pemeriksaan apakah queue kosong. Jika kosong maka penghapusan dibatalkan karena tidak mungkin menghapus data dari queue yang sudah kosong. Cara pertama yang dapat dilakukan untuk mengimplementasikan queue dengan array adalah sebagai berikut. Ketika terjadi penambahan data maka index ekor akan ditambah dengan satu dan array dengan index tersebut akan diisikan dengan data. Ketika terjadi Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 1
penghapusan nilai index kepala akan ditambahkan dengan satu. Ilustrasi penambahan dan penguranagan dapat dilihat pada gambar 2.
Gambar 2. Ilustrasi Cara Pertama
Pada Gambar 2 dapat dilihat bahwa data pada kepala queue tidak dihapus, hanya penunjuknya saja yang digeser ke index berikutnya. Kode program secara lengkap dapat dilihat pada Program 1. Program 1. Implementasi Cara Pertama 1 2 3 4 5 6 7 8 9 10 11 12 13 14
program array_queue1; uses crt; const max = 100; type antri = array[1..max] of char; var antrian : antri; depan,belakang : integer; i : integer;
procedure tambah(c : char); Begin if (belakang = max) then Begin
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 2
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
Writeln('Queue penuh!'); exit; end; writeln('Tambah: ',c); belakang := belakang + 1; antrian[belakang] := c; end; procedure hapus; Begin if (depan > belakang) then Begin Writeln('Queue kosong!'); exit; end; writeln('Hapus: ',antrian[depan]); depan := depan + 1; end; procedure tampil_queue; var i : integer; Begin writeln; writeln('Data pada antrian sekarang:'); for i:= depan to belakang do Begin Writeln(antrian[i]); end; end; procedure press_any_key_to_continue; Begin writeln('Press any key to continue!'); writeln; readkey; end;
Begin clrscr; belakang := 0; depan := 1; tambah('a'); tambah('b'); tambah('c'); tambah('d');
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 3
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
tambah('e'); tambah('f'); tambah('g'); tambah('h'); press_any_key_to_continue; tampil_queue; press_any_key_to_continue; hapus; hapus; hapus; press_any_key_to_continue; tampil_queue; press_any_key_to_continue; end.
Cara pertama kurang efisien dalam penggunaan memori. Blok memori data yang sudah terhapus tidak dapat digunakan lagi. Sehingga blok memori yang dapat digunakan untuk menyimpan data menjadi semakin berkurang setiap terjadi penghapusan data. Untuk memecahkan masalah tersebut dilakukan pergeseran setiap terjadi penghapusan data. Ketika data dihapus maka seluruh item array dari index kepala + 1 hingga ekor akan dipindahkan ke index sebelumnya. Dengan cara ini, nilai array dengan index kepala akan tertimpah oleh nilai sebelumnya (terhapus). Pada teknik ini tidak terjadi perubahan penunjuk kepala pada saat penghapusan data. Pada saat penambahab, yang terjadi sama dengan cara sebelemunya. Gambar 3 menunjukan ilustrasi penghapusan cara kedua.
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 4
Gambar 3. Ilustrasi penghapusan cara kedua
Pada cara kedua tersebut dapat dilihat tidak ada pemborosan memori. Sehingga masalah pada cara pertama sudah terselesaikan. Kode program secara lengkap dapat dilihat pada Program 2. Program 2. Implementasi Cara Kedua 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
program array_queue2; uses crt; const max = 100; type antri = array[1..max] of char; var antrian : antri; depan,belakang : integer; i : integer;
procedure geser; var i : integer; Begin if (belakang > 1) then Begin for i:= 1 to belakang - 1 do Begin antrian[i] := antrian[i+1]; end; end; end;
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 5
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
procedure tambah(c : char); Begin if (belakang = max) then Begin writeln('Queue penuh!'); exit; end; writeln('Tambah: ',c); belakang := belakang + 1; antrian[belakang] := c; end; procedure hapus; Begin if (belakang = 0) then Begin writeln('Queue kosong!'); exit; end; writeln('Hapus: ',antrian[depan]); geser; belakang := belakang - 1; end; procedure tampil_queue; var i : integer; Begin writeln; writeln('Data pada antrian sekarang:'); for i:= depan to belakang do Begin writeln(antrian[i]); end; end; procedure press_any_key_to_continue; Begin writeln('Press any key to continue!'); writeln; readkey; end;
Begin clrscr; belakang := 0; depan := 1;
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 6
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
tambah('a'); tambah('b'); tambah('c'); tambah('d'); tambah('e'); tambah('f'); tambah('g'); tambah('h'); press_any_key_to_continue; tampil_queue; press_any_key_to_continue; hapus; hapus; hapus; press_any_key_to_continue; tampil_queue; press_any_key_to_continue; end.
Ketika data yang terdapat pada queue masih sedikit, cara kedua tidak akan mendatangkan masalah. Namun ketika data sudah berjumlah besar akan terjadi kelambatan pada saat penghapusan data. Sebagai contoh ketika data yang berada pada array sudah berjumlah 1000 data. Maka ketika terjadi penghapusan diperlukan 99 pemindahan data. Cara yang ketiga yang digunakan adalah dengan menggunakan array melingkar. Dengan cara penambahan maupun penghapusan data mirip dengan cara pertama namun dengan ketentuan berbeda pada penentuan kepala dan ekor. Pada saat penambahan di kedua cara sebelumnya jika nilai index ekor sudah mencapai nilai maximum maka disimpulkan bahwa queue telah penuh. Pada cara ini, nilai index ekor sudah mencapai nilai maximum nilai ekor akan melakukan pemeriksaan pada index pertama dari array. Jika bukan merupakan kepala maka index ekor merupakan nilai index pertama array. Pada saat penghapusan, yang terjadi adalah sebaliknya. Ketika data pada index array paling awal dihapus, akan dilakukan pemeriksaan apakah data pada nilai index ekor merupakan data terakhir atau bukan. Jika bukan maka penunjuk kepala akan menunjuk kepada index array terakhir. Gambar 4 menunjukan ilustrasi penambahan dan penghapusan.
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 7
Gambar 4. Ilustrasi Cara Ketiga
Dengan cara ini permasalahan cara petama dan kedua dapat diselesaikan. Kode program secara lengkap dapat dilihat pada Program 3.
Program 3. Implementasi Cara Ketiga 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
program array_queue3; uses crt; const max = 10; type antri = array[1..max] of char; var antrian : antri; depan,belakang : integer; i : integer; jumlah : integer;
procedure tambah(c : char); var tmp : integer; Begin if (jumlah = 10) then Begin Writeln('Queue penuh!'); exit;
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 8
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
end; writeln('Tambah: ',c); if (belakang = max) then Begin tmp := belakang; belakang := 1; End Else belakang := belakang + 1; antrian[belakang] := c; jumlah := jumlah + 1; end; procedure hapus; Begin writeln('Hapus: ',antrian[depan]); if (jumlah = 0) then Begin Writeln('Queue kosong'); exit; End Else Begin if (depan = max) then depan := 1 Else depan := depan + 1; end; jumlah := jumlah - 1; end; procedure tampil_queue; var i : integer; Begin writeln; writeln('Data pada antrian sekarang:'); i:= depan; Repeat Begin Writeln(antrian[i]); if (i = max) then i := 1 Else i := i + 1; end; until (i = belakang+1);
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 9
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
end; Procedure press_any_key_to_continue; Begin writeln('Press any key to continue!'); writeln; readkey; end;
Begin clrscr; belakang := 0; depan := 1; jumlah := 0; tambah('a'); tambah('b'); tambah('c'); tambah('d'); tambah('e'); tambah('f'); tambah('g'); tambah('h'); press_any_key_to_continue; tampil_queue; press_any_key_to_continue; hapus; hapus; hapus; press_any_key_to_continue; tampil_queue; press_any_key_to_continue; tambah('i'); tambah('j'); tambah('k'); tambah('l'); tambah('m'); tambah('n'); tambah('o'); press_any_key_to_continue; tampil_queue; press_any_key_to_continue;
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 10
117 118
end.
Implementasi Queue dengan pointer Implementasi dengan array memiliki keterbatasan jumlah data yang dapat disimpan pada queue. Jika dilihat penjelasan sebelumnya strutktur queue dapat diimplememntasikan sebagai struktrur linked list dengan perlakukan khusus. Sebelumnya telah dijelaskan untuk memanipulasi dibutuhkan dua penunjuk. Maka pada linked list juga terdapat kebutuhan yang sama. Penunjuk pertama akan menunjuk kepada kepala list (merupakan kepala dari queue) dan penunjuk yang kedua menunjuk kepada item terakhir pada list (merupakan ekor dari queue). Linked list yang digunakan bisa linked list satu arah maupun dua arah. Pada pembahasan ini akan diimplementasikan dengan linked list satu arah. Struktur queue dapat dilihat pada Gambar 5.
Gambar 5. Struktur Queue dengan Linked List
Pada saat inisialisasi pointer kepala dan ekor akan menunjuk ke nil. Ini menunjukan bahwa queue masih kosong. Pada saat penambahan, cara yang dilakukan sama seperti penambahan linked list satu arah untuk data terakhir hanya ditambah dengan penentuan pointer ekor. Pada saat penghapusan caranya sama pula dengan cara penghapusan linked list data pertama. Kode program secara lengkap dapat dilihat pada Program 4.
Program 4. Implementasi Queue dengan Pointer 1 2 3 4 5 6
program pointer_queue; uses crt; type item = ^simpul; {tipe data ini digunakan untuk menunjuk 1 item queue} simpul = record {record ini digunakan untuk struktur item queue} berikut : item; data : char;
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 11
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
var
end; kepala ekor
: item; : item;
{ Procedure untuk menambah data ke queue. parameter: dt : char -> data yang akan ditambahkan } procedure tambah(dt : char); var baru : item; Begin writeln('TAMBAH: ',dt); {buat data baru, set penunjuk berikut ke nil, dan isi data dengan karakter yang ingin ditambahkan} baru := new(item); baru^.berikut := nil; baru^.data := dt; {jika queue masih kosong, set data baru sebagai kepala dan ekor} if (kepala = nil) then Begin kepala := baru; ekor := baru; End Else {jika queue sudah terisi, simpan data baru di tempat yang paling akhir dan set sebagai ekor} Begin ekor^.berikut := baru; ekor := ekor^.berikut; end; end; { Procedure untuk menghapus data dari queue. } procedure hapus; var curr : item; Begin {jika ekor bernilai nil maka artinya queue kosong} if (ekor = nil) then Begin writeln('Queue kosong!'); exit; end;
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 12
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
{jika data merupakan data terakhir, langsung hapus data tersebut} if (kepala = ekor) then Begin Writeln('HAPUS: ',ekor^.data); Dispose(ekor); ekor := nil; End {jika data bukan merupakan data terakhir,set kepala ke data berikutnya, hapus data kepala sebelumnya} Else Begin Writeln('HAPUS: ',kepala^.data); curr := kepala; kepala := kepala^.berikut; Dispose(curr); end; end;
{ Procedure } procedure var curr Begin {set curr
yang digunakan untuk menampilkan semua data yang ada pada queue. tampil_semua; : item; penunjuk ke kepala} := kepala;
{tuliskan nilai data dari awal hingga akhir} while (curr <> nil) do Begin write(curr^.data,' '); curr := curr^.berikut; end; writeln; end;
Begin {set kepala dan ekor untuk menunjuk ke nil} kepala := nil; ekor := nil; clrscr; {contoh penggunaan procedure} tambah('a');
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 13
102 103 104 105 106 107 108 109 110 111 112 113 114
tambah('b'); tambah('c'); tambah('d'); tambah('e'); tambah('f'); tampil_semua; hapus; hapus; hapus; hapus; tampil_semua; readkey; end.
Queue Berprioritas
Pusat Pengembangan Pendidikan – Universitas Gadjah Mada 14
