QUEUE (ANTREAN)
Pengertian Queue /Antrean
Secaraharfiah queue dapatdiartikansebagaiantrean. Queue merupakankumpulan data denganpenambahan data hanya dapat dilakukanmelaluisatusisi, yaitubelakang (tail) danpenghapusan data hanyamelaluisisidepan (head). queuebersifat FIFO(First In First Out), yaitu data yang pertamamasukakankeluarterlebihdahuludan data yang terakhirmasukakankeluarterakhir. Berikutiniadalahgambaranstruktur data queue.
Elemen yang pertama kali masukkedalam queue disebutelemendepan (front/head of queue), sedangkanelemen yang terakhir kali masukke queue disebutelemenbelakang (rear/tail of queue).
Aturan penambahan dan penghapusan elemen pada queue, yaitu pada penambahan elemen selalu di lakukan melalui salah satu ujung, menempati posisi di belakang elemen-elemen yang sudah masuks ebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan.
Operasi-operasi dasar dari sebuah queue adalah :1.Enqueue : proses penambahanelemen di posisibelakang
2.Dequeue : proses pengambilanelemen di posisidepan
Selain operasi dasar di atas, ada pula operasi-operasi lain yang dapat dilakukan terhadap sebuah queue yaitu :
1.CREATE (Q) Operator yang menunjukkan suatu antrean hampa Q.
Berarti : Noel (Q) = 0
Front (Q) & Rear (Q) = tidak terdefinisi
2.ISEMPTY (Q) Operator yang menunjukkan apakah antrean Q hampa.
Operand
: tipe data antrean
Hasil
: tipe data boolean
ISEMPTY (CREATE (Q)) = True
3.INSERT (E, Q) Operator yang menginsert elemen E ke dalam antrean Q.
E ditempatkan di bagian belakang antrean.
Hasil : antrean yang lebih besar.
REAR (INSERT (E, Q)) = E
ISEMPTY (INSERT (E, Q)) = False
4.REMOVE (Q)Operator yang menghapus elemen bagian depan dari antrean Q.
Hasil : antrean yang lebih pendek.
Pada setiap operasi, Noel (Q) berkurang 1 dan elemen ke-2 menjadi elemen terdepan.
Jika Noel (Q) = 0 maka Q = hampa
Remove (Q) = kondisi error (underflow condition)
Remove (Create (Q)) = kondisi error (underflow condition)
Jikaadaelemenbaru yang akanmasukpadagambar (a), makaiaakandiletakkandisebelahkanan F (gambar (b)). Jikaadaelemen yang akandihapus, maka A akandihapuslebihdulu (gambar (c)).
Contoh deklarasi antrian :
Const max = 5
Varantrian : array [1..max] of char;
Belakang, depan : integer; x : char;
Dengan menggunakan array, maka overflow dapat terjadi jika antrian telah penuh, sementara masih ingin menambah elemen kedalam antrian. Dengan mengabaikan adany aoverflow, maka penambahan elemenbaru yang dinyatakanolehvar x dapat diimplementasikan denganstatemen :
belakang := belakang + 1;
antrian [belakang] := x;
Operasi penghapusan bisadi implementasikan dengan ;
x := antrian [depan];
depan := depan + 1;
Padagambar (a) posisidepan = 1 danbelakang = 0. Padagambar (b) keadaan setelah penambahan empat buah elemen dimana posisi depan = 1 dan belakang = 4. Pada gambar(c) keada ansetelah penghapusan duabuahel emen dimanaposisidepan = 3 danbelakang =4. Padagambar (d) keadaansetelahpenambahanduabuahelemendiamanaposisidepan =3 danbelakang = 5.
Jikaakanditambahelemenbaru, makanilaibelakangharusditambahsatumenjadi 6.Sedangkanlarikantriantersebuthanyaterdiridari 6 elemensehinggatidakbisaditambahlagimeskipunsebenarnyalariktersebutmasihkosong di duatempat.Olehkarenaitudilakukandenganmetodapenggeserandimanajikaadaelemen yang dihapus, makasemuaelemen lain digesersehinggaantrianselaludimulaidaridepan = 1.
x := antrian [1];
for i := 1 to belakang-1 do
begin
antrian [ i] := antrian [i +1];
end;
Pada gambar (a) posisi depan = 1 dan belakang = 0. Pada gambar (b) keadaan setelah penambahan empat buah elemen di mana posisi depan = 1 dan belakang = 4. Padagambar(c) keadaan setelah penghapusan dua buah elemen dimana posisi depan = 1 dan belakang= 2. Pada gambar (d) keadaan setelah penambahan dua buah elemen di mana posisi depan =1 dan belakang = 4.Cara penggeseran elemen tidak efisien untuk larik berukuran besar.Oleh karena itu dilakukan dengan larik yang menyimpan elemen antrian sebagai larik memutar (circular).
b. Dengan Menggunakan Circular Array
Salah satuvariasi array adalah array melingkar (circular array), artinya array dapat diakses mulai dari sembarang indeks (indeksawal) kearah indeks terakhir (maksimum array), lalu memutar ke indeks pertama hingga kembali ke indeks awal. Circular array adalah array yang dibuatseakan-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, makajumlah 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 nilai head dan tail mencapai maksimum, maka akan dikembalikan keposisiawal. Queue dengan circular array dapat dibayangkan sebagaiberikut :
Aturan-aturandalam queue yang menggunakan circular array adalah :
- Proses penghapusan dilakukan dengan cara nilai depan (front) ditambah 1 : depan = depan + 1.
- Proses penambahan elemen sama dengan linear array yaitu nilai belakang ditambah 1 : belakang = belakang + 1.
- Jika depan = maka s dan ada elemen yang akan dihapus, maka nilai depan = 1.
- Jika belakang = maks dan depan tidak 1 maka jika ada elemen yang akan ditambahkan ,nilai belakang=1
- Jika hanya tinggal 1 elemen di queue (depan = belakang), dan akan dihapus maka depan di isi 0 dan belakang di isi dengan 0 (queue kosong).
Front dan Tail akanbergerakmaju, jika ;
- Untuk penambahan.
- Tail sudah mencapai elemen terakhir array akan memakai elemen pertama array yang telah dihapus.
- Untuk pengahapusan.
- Front telah mencapai elemen terakhir array, maka akan menuju elemen pertama jika antrian masih berisi elemen.
Keunggulan representasi circular adalah seluruh kapasitas antrian bisa terpakai seleruhnya.Berdasarkan ilustrasi sebelumnya dapat disusun prosedur untuk menambah dan menghapus elemen antrian sebagai berikut ini :
Constmax_elemen = 5;
Type antri = array [1..max_elemen] of char;
Varantrian :antri;
depan, belakang : integer;
Nilai awal untuk depan dan belakang masing-masing 0.
Depan := 0; Belakang := 0;
Proses dequeue hanya bisa dilakukan jika queue dalam keadaan tidak kosong.Ada beberapa kondisi yang harus diperhatikan ketika dequeue elemen queue yaitu :
- Kondisi ketika posisi depan sama dengan posisi belakang (queue hanya memiliki 1elemen) maka nilai depan dan belakang di isi dengan 0 (queue kosong).
- Jika posisi depan sama dengan posisi maks_queue maka posisi depan berpindah ke 1.
- Selain itu, posisi depan ditambah dengan 1 : depan = depan + 1
Impelementasinya dalam bahasa Pascal adalah :
function dequeue (var q : antri) : char;
begin
if (depan=0) and 9belakang=0) then then
write (‘ antriankososng’);
else
begin
dequeue := q [depan];
ifdepan = max_elemen then
depan := 1
else
depan := depan + 1;
end;
end;
DEQUE (Queue Ganda atau Double Queue)
Suatu linear list, yang penambahan dan penghapusan elemen dapatdilakukan pada kedua sisi ujung list, tetapi tidak dapat dilakukanditengah-tengah list.
Deque (menggunakan array sirkular)Menggunakan 2 pointer/penunjuk :
1. LEFT : sisi kiri dari deque
2. RIGHT : sisi kanan dari deque
Asumsi : elemen deque berurut dari kiri ke kanan.
Contoh : Menggambarkan 2 buah deque, masing-masing berisi 4elemen, yang ditempatkan di dalam sebuah Array dengan 8 lokasimemori.
2 variasi deque, yaitu :
- Deque Input Terbatas : Pemasukan elemen pada satu ujung list, penghapusan elemen pada kedua ujung list.
- Deque Output Terbatas : Pemasukan elemen pada kedua ujung list, penghapusan elemen pada salah satu ujung list.
Antrean Berprioritas
Himpunan elemen, yang setiap elemennya telah diberikan sebuah prioritas, dan urutan proses penghapusan elemen adalah berdasarkan aturan berikut :
- Elemen yang prioritasnyalebihtinggi, diproses lebih dahulu dibandingkan dengan elemen yang prioritasnya lebih rendah.
- Dua elemen dengan prioritas yang sama, diprosesse suai dengan urutannya sewaktu dimasukkan kedalam antrean berprioritas.
Terimakasih sudah datang dan membaca artikel kami
Sertakan link sumber untuk menghargai karya cipta orang lain :)
