MATERI KELOMPOK 2

QUEUE ( ANTRIAN )

A.  Pengertian 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.

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 Queue dengan Stack

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.

Sedangkan 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.

Queue atau antrian banyak kita jumpai dalam kehidupan sehari-hari.

Contoh :

Ø  Antrian Mobil diloket Tol

Ø  Antrian mahasiswa saat melakukan pendaftaran

Ø  Antrian saat membeli tiket film di bioskop

Ø Antrian reservasi tiket kereta api

Ø Antrian saat mengisi BBM SPBU

Ø Antrian saat melakukan pengecekan tiket dan paspor saat chekin pesawat.

Contoh lain dalam bidang komputer adalah pemakaian sistem komputer berbagi waktu(time-sharing computer system) dimana ada sejumlah pemakai yang akan menggunakan sistem tersebut secara serempak.

Ø Antrian pada kasir pada sebuah bank. Ketika seorang pelanggan datang, akan menuju ke belakang dari antrian. Setiap pelanggan dilayani, antrian yang berada di depan akan maju. Jika kita ada di antrian kedua, maka kita akan menunggu antrian pertama melakukan prosesnya. Nah, ketika selesai proses dari antrian pertama dia akan pergi, dan giliran kita untuk maju untuk melakukan proses.

Ø Deklarasi Awal Queue

Ø Variabel yang akan digunakan adalah data (array sebagai tempat queue), head, tail.  Sama seperti Stack, Nilai dari head dan tail dimulai dari -1 yang menandakan queue kosong. sebagai contohnya kita akan membuat queue dengan data maksimal sebanyak 7 data.

Ø   

Ø Deklarasi awal variabel yang akan digunakan dalam queue

   Karakteristik Queue atau antrian

1. Adanya elemen antrian yaitu item – item data yang  terdapat di elemen antrian.

2. Adanya front (elemen terdepan antrian)

3. Adanya  tail (elemen terakhir)

4. Adanya  jumlah elemen pada antrian

5. Status antrian

   Kondisi antrian yang menjadi perhatian adalah :

1)   Penuh

Bila elemen di antrian  mencapai  kapasitas  maksimum  antrian. Pada kondisi ini, tidak mungkin dilakukan penambahan ke antrian. Penambahan elemen menyebabkan kondisi kesalahan Overflow.

2)   Kosong

Bila tidak ada elemen di antrian. Pada kondisi ini, tidak mungkin dilakukan pengambilan elemen dari antrian. Pengambilan elemen menyebabkan kondisi kesalahan Underflow.

   Representasi

Untuk mempermudah penulisan, di bawah ini isi queue tidak dituliskan secara bertumpuk,

tetapi dengan kesepakatan:

• elemen paling kanan adalah elemen yang ada pada ujung belakang (yang terakhir kali

masuk)

• queue yang dipakai bernama Q

• ADDQ(B,Q) berarti memasukkan elemen B ke dalam queue Q

• DELQ(B,Q) berarti mengambil elemen dari queue Q dan menaruhnya ke dalam variabel B

Operasi yang dilakukan	Isi Queue	Keterangan
Kondisi Awal	Kosong	-
ADDQ('A',Q)	A	-
ADDQ('B',Q)	AB	-
ADDQ('C',Q)	ABC	-
DELQ(Data,Q)	BC	Variabel Data berisi 'A'
ADDQ('D',Q)	BCD	-
DELQ(Data,Q)	CD	Data berisi 'B'
POP(Data,S)	D	Data berisi 'C'

   Operasi – operasi Queue

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

1.    Inisialisasi Queue

Inisialisasi queue adalah proses pemberian nilai 0 untuk field depan dan belakang dari queue dan juga pemberian nilai maks ke maks_queue yang menunjukan banyaknya maksimal data dalam queue. Karena dalam bahasa C elemen sebuah array dimulai dengan 0 maka proses inisialisasi nilai depan dan belakang bukan 0 tetapi -1 sehingga ketika ada proses penambahan elemen (enqueue) akan bernilai 0 sehingga elemen tersebut akan disimpan dalam elemen antrian pada posisi 0. Implementasi fungsi inisialisasi queue dalam bahasa C adalah :

void inisialisasi (TQueue *Q)
{
Q->maks_queue=maks;
Q->depan=-1;
Q->belakang=-1;
}
Cara pemanggilannya adalah :
Inisialisasi (&Q);

2.    Enqueue

Digunakan untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang. Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu.

Contoh : Seseorang membeli tiket melalui tempat pembayaran tiket yang disediakan.

3.    Dequeue

Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian. Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dengan 1. Penggeseran dilakukan dengan menggunakan looping.

Contoh : Setelah membeli tiket, langsung menuju tempat penungguan kereta, dengan sebelumnya petugas memeriksa cek tiket tersebut.

3.    IsEmpty()

Untuk memeriksa apakah Antrian sudah penuh atau belum. Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty. Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah. Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail.

Contoh : Petugas tiket Kereta melihat tidak ada lagi yang ingin membeli tiket kereta.

4.    IsFull

Untuk mengecek apakah Antrian sudah penuh atau belum. Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh.

   MANFAAT  QUEUE

1.    Digunakan sistem operasi untuk mengatur eksekusi task dalam suatu sistem untuk mencapai perlakuan yang adil ( queue seringkali disebut  waiting line ).

2.    Untuk mailbox dalam komunikasi antar proses.

3.    Untuk buffer dalam mekanisme printspooler, komunikasi data.

4.    Untuk simulasi dan modeling ( misalnya simulasi sistem pengendali lalu lintas udara) dalam memprediksi performansi.

5.    Simulasi antrian di dunia nyata, antara lain :

a.     Antrian pembelian tiket di depan loket untuk bis,kereta api, bioskop.

b.    Antrian mobil di depan gerbang jalan tol.

c.     Antrian kendaraan di jalanan umum.

6.    System produksi

a.     Barisan bahan atau komponen yang akan diproses suatu mesin.

b.    Barisan bahan atau komponen yang akan diproses suatu manusia

   Contoh program

PROGRAM QUEUE01;

uses wincrt;

const MAX=50;

type

larik = Array[0..MAX] of char;

RecQueue = RECORD

info : larik;

awal : integer;

akhir : integer;

END;

var

antri : RecQueue;

pilih,elm : char;

procedure init;

begin

antri.awal := 0;

antri.akhir := 0;

end;

function Isfull:boolean;

begin

if antri.akhir = MAX then

Isfull := true

else

Isfull := false;

end;

function IsEmpty:boolean;

begin

if antri.akhir = 0 then

Isempty := true

else

Isempty := false;

end;

procedure baca;

var i:integer;

begin

writeln('Isi queue sekarang : ');

for i := antri.awal to antri.akhir do

write(antri.info[i], ' ');

writeln('');

end;

procedure inQueue(elemen:char);

begin

if Isempty = true then

begin

antri.awal := 1;

antri.akhir:= 1;

antri.info[antri.awal] := elemen;

end

else if Isfull <> true then

begin

antri.akhir := antri.akhir + 1;

antri.info[antri.akhir]:=elemen;

end

else

writeln('Queue overflow...');

end;

function deQueue:char;

var isi:char;

i : integer;

begin

if Isempty <> true then

begin

isi := antri.info[antri.awal];

for i:=antri.awal to antri.akhir - 1 do

antri.info[i] := antri.info[i+1];

antri.akhir := antri.akhir - 1;

deQueue := isi;

end

else

writeln('Queue underflow...');

end;

BEGIN

CLRSCR;

writeln('--- Demo Queue dg Linear Array ---');

init;

repeat

writeln('OPERASI QUEUE dg Linear Array :');

writeln('[1] InQueue (Insert Queue)');

writeln('[2] DeQueue (Delete Queue)');

writeln('[3] Baca');

writeln('[4] Selesai...');

write(' Pilihan : ');

readln(pilih);

case pilih of

'1' : begin

write('Antrian Masuk : ');

readln(elm);

inQueue(elm);

end;

'2' :

 begin

 elm:=deQueue;

writeln(elm,' Keluar dr antrian');

end;

'3' : baca;

'4' : writeln('Wakarimasuta (?_?)');

else writeln('Salah pilih...');

end;

writeln('');

until (pilih = '4');

readln;

END.