pascal tentang queue/antrian (materi kuliah semester 2)

QUEUE (ANTRIAN)

perhatikan antrian calon pembeli di sebuah warung makan, pada jam-jam tertentu, pembeli yang datang sangat sedikiyt dan dapat langsung dilayani, namun pada jam-jam makan, calon-calo pembeli akan berdatangan dan membentuk antrian. Setiap kali ada calon pembeli yang datang (menambahkan elemen), maka ia harus menempati posisi paling belakangdalam barisan antrian yang ada. Petugas warung hanya akan melayani calon pembeli yang paling

depan dari antrian. Jika sudah dilayani , maka pembeli tadi akan meninggalkan antrian(mengurangi elemen), dan orang-orang dibelakangnya akan bergerak maju. Jadi petugas warung tetap hanya akan melayani calon pembeli yang berada paling depan dalam antrian itu.

Pada kasus diatas penambahan elemen hanya dapat dilakukan di ujung belakang antrian, sedangkan penghapusan elemen hanya dapat dilakukan diujung depan antrian. Keadaan tersebut bisa disebut Queue (antrian0 atau FOFO- First In First Out.

11.1 Defenisi

Sebuah Queue bertipe t adalah sebuah barisan berhingga atas elemen-elemen bertipe T, bersama-sama dengan operasi berikut:

1.    Inisialisasi Queue menjadi kosong.

2.    Mencari tahu status Queue kosong atau tidak

3.    Mencari tahu status Queue peenuh atau tidak

4.    Mencari panjang Queue (jumlah elemen Queue)

5.    Jika Queue tidak pennuh, memesukan elemen baru sesudah elemen paling belakang.

6.    Mengambil nilai dari elemen Queue terdepan bila Queue tidak kosong.

7.    Menghapus elemen terdepan bila Queue tidak kosong.

Queue adalah kumpulan objek data yang tipenya sama, tersusun sebagai sebuah barisan linier dengan operasi menambahkan elemen selalu dilakukan di salah satu ujung barisan, dan operasi menghapus elemen dilakukan di ujung lainya. Queue merupakan bentuk khusus dari lish, yaitu lis linier sifat “masuk awal, keluar awal’ (FIFO list : First In First Out).

Karena sifat keluar masuknya elemen queue melalui kedua ujung queue, maka elemen-elemen pada kedua ujung barisan tersebut perlu diidentifikasikan. Elemen yang pertama kali masuk antrian disebut elemen depan (front/head of queue), sedangkan elemen yang terakhir kali masuk disebut elemen belakang (read/tail queue). Gambar berikut menunjukan model penyajian antrian dengan list linear.

 

11.2 operasi/Prosedure Standar Pada Queue

Queue merupakan struktur data dinamis, ketika program dijalankan, jumlah elemennya dapat berubah secaara dinamis sesuai keperluan. Berikut ini operasi-operasi stadar pada queue:

1.    Instalasi, merupakan procedure untuk membuat queue pada kondisi awal, yaitu queue yang masih kosong (belum mempunyai elemen).

2.    Inqueue, Insert Queue merupakan procedure untuk mamasukan sebuah elemen baru pada queue. Jumlah elemen queue akan bertambah satu dan elemen tersebut merupakan elemen belakang.

3.    Dequeue, Delete Queue merupakan prosedur untuk menghapus/mengambil sebuah elemen dari queue. Elemen yang diambil adalah elemen depan dan jumlah elemen queue akan berkurang satu.

Hal lain yang perlu diperhatikan dalam suatu struktur dinamis adalah jumlah elemen struktur data tersebut.operasi-operasi yang berhubungan dengan jumlah elemen suatu queue adalah:

1.    Size, yaitu operasi untuk mendapatkan banyaknya elemen Queue.

2.    Empty, yaitu prosedur untuk mengetahui apakah Queue dalam keadaan kosong atau tidak.dengan status ini maka dapat dicegah dilakukannya operasi DeQueue dari suatu queueu yang kosong.

3.    Full, merupakan prosedur untuk mengetahiu apakah queue penuh atau tidak. Prosedur ini hanya berlaku untuk queue yang jumlahnya terbatas.

11.3 Implementasi Queue dengan Array

Untuk mengimplementasikan queue dengan array dapat dipakai berbagai model. Sebagai gambaran modelyang dapat digunakan antara lain :

1.    Model fisik,sebuah array linier, dengan elemen depan dari queue selalu ditempatkan pada pertama dari elemen dari array dan seluruh elemen queue digser satu posisi kedepan setiap kali elemen depan dari queue diambil/dihapus.

2.    Sebuah array linier dengan indeks depan dan belakang selalu bergeser kea rah posisi terakhir dari array.

3.    Sebuah array melingkar dengan indeks depan dan belakang, serta sebuah posisi yang dibiarkan kosong.

4.    Sebuah array melingkar dengan indeks depan dan belakang, serta sebuah variable Boolean untuk menunjukan statuskosong/pemuh dari queue.

5.    Sebuah array melingjar dengan indeks depan dan belakang. Serta sebuah variabelintegerbuntuk counter yang menunjukan banyaknya dari elemen queue,

6.    Sebuah array melingkar dengan indeks  depan dan belakang,dan  nilai tertentu untuk untuk menunjukkan status kosong/penuh dari queue.

Model fidik merupakan model yang paling buruk karena memerlukan waktu yang lama untuk proses penggeseran seluruh elemen queue setiap kali ada operasi DeQueue. Kelemeahan ini diperbaiki oleh model ke-2, namun implementasi linier untuk kueue ini, masih memiliki kelemajhan dengan tidak terpakainya ruang array dari posisi pertama hingga posisi yang sebelum posisi yang ditempati elemen queue. Sementara itu, indeks depan dan belakang pasti akan mencapai posisi ruang terakhir dari array.

Implementasi dari array merupakan model yang tepat untuk mengatasi inefisiensi penggunaan model array pada model linier. Array dapat dipandang sebagai sebuah lingkaran. Apabila posisi terakhir pada array telah digunakan dan posisi pertama array tidak digunakan lagi, maka elemen queue berikutn ya dapat diletakkan mulai posisi pertama lagi. Untuk mengimplementasikan array melingkar dari sebuah array linier, posisi-posisi yang mengelilingi lingkaran diberi nomor dari 1 s/d maks, sama dengan indeks array linier. Pergeseran/kenaikan indeks dilakukan dengan operasi aritmatika modulo (pembagian bilangan bulat). Ketika nilai indeks melebihi maks, maka dimulai lagi dari 1. Operasi modulo mirip operasi pada sebuah jam, dengan angka 1 s/d 12, bila kita menggeser empat jam dari jam 10 maka kita akan mencapai jam 2.

Bila range index digunakan adalah 1..maks, maka pergeseranindeks ini dalam pascal dapat dilakukan dengan pernyataan berikut:

If index = maks then

Indeks := 1 else index := index+1;

Atau dengan operator berikut ini:

Indeks := (index mode maks)+1;

Untuk lebih memahami implementasi queue dengan array melingkar, berikut diilustrasikan penambahan dan penghapusan pada queue, dengan range indeks 1..maks=8.

Queue 1 adalah keadaan queue sebelum digunakan (setelah diinisialisasi). Nilai-nilai elemen array adalah sembarang nilai yang ada dalam memory.

Queue 2 adalah queue dengan 5 buah elemen, berasal dari queue 1 dan 5 kali operasi inqueue, yaitu menyisipkan data A, B, C, D dan E

Queue 3 adalah queue dengan sebuah elemen, berasal dari nqueue 2 dan adanya operasi dequeue empat kali berturut-turut, indeks d= indeks b=5.

Queue 4 adlah queue dengan tujuh elemen, berasal dari 3 queue dan memasukkan 6 buah elemen baru secara berurutan, yaitu F, G, H, I, J K, indeks d=5, indeks b=3.

Queue 5 adalah queue dengan delapan elemen (full), berasal dari queue 4 dan ditambahkan sebuah elemen baru, L indeks d=4, dan indeks b=4.

Queue 6 adalah queue dengan sebuah elemen, berasal dari queue 5 dan dilakukan operasi dequeue tujuh kali berturut-turut, indeks d=5, indeks b=4.

Queue 7 adalah queue kosong, berasal dari queue 6, dan sebuah operasi dequeue, indeks d=5. Dan indeks b=4.

Dari ilustrai tersebut masih terdapat hal yang membingungkan, yaitu pada queue 5 dan queue 7, indeks depan dan belakang pada queue tersebut menunjuk pada lokasi yang sama, tetapi status queuenya berbeda. Queue 5 menyatakan queue penuh, sedangkan queue 7 menyatakan queue kosong.