TEKNIK QUEUE

Queue (Antrian) adalah suatu kumpulan data yang mana penambahan data / elemen hanya dapat dilakukan pada sisi belakang sedangkan penghapusan / pengeluaran elemen dilakukan pada sisi depan.

Karakteristik penting antrian sebagai berikut :

1. Elemen antrian yaitu item-item data yang terdapat di elemen antrian.
2. Head/front (elemen terdepan dari antrian ).
3. Tail/rear (elemen terakhir dari antrian ).
4. Jumlah elemen pada antrian (count).
5. Status/kondisi antrian.

Berbeda  Queue dengan Stack

prinsip yg digunakan dalam antrian adalah FIFO ( First In First Out ). Dengan kata lain, urutan keluar elemen akan sama dengan urutan masuknya. Sedangkan prinsip yg digunakan dalam Stack adalah Last In First Out.

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 InQuee (Insert Queue).
5. Menghapus elemen queue atau DeQueue (Delete Queue).  

Operasi dalam Queue

1. Create ( )
2. IsEmpty ( )
3. IsFull
4. Enqueue (data)
5. Dequeue()
6. Clear()
7. Tampil

Operasi-operasi pokok antrian sebagai berikut :

1. createQueue (Q), atau constructor menciptakan antrian kosong Q.
2. addQueue (Q, X) memasukkan elemen X sebagai elemen akhir di Q.
3. removeQueue (Q, X)atau mengambil elemen depan di antrian Q ke elemenX.

Operasi-0perasi Query tambahan yang dapat dilakukan adalah :

1. isEmptyQueue (Q), mengirim apakah antrian Q adalah kosong.
2. isFullQueue (Q), mengirim apakah antrian Q adalah penuh bila kapasitas antrian Q didefinisikan.
3. isOverflowQueue (Q), mengirim apakah antrian Q telah mengalamioverflow.
4. isUnderflowQueue (Q), mengirim apakah antrian Q mengalamiunderflow.

Meski Queue sangat sederhana, namun Queue merupakan kakas dasar penyelesaian masalah-masalah besar. penggunaan Queue yang utama adalah untuk simulasi fenomena antrian di dunia nyata, serta fenomena antrian di pengolahan data.

1. Simulasi antrian di dunia nyata, antara lain :

a)      Lalu lintas pesawat udara tinggal landas (take-off) dan pendaratan (landing).

b)      Antrian pembelian tiket di depan oket untuk bis, kereta api, bioskop.

c)       Antrian mobil di depan gerbang jalan tol.

d)      Antrian kendaraan di jalanan umum.

2. System produksi

• Barisan bahan atau komponen yang akan diproses suatu mesin.
• Barisan bahan atau komponen yang akan diproses suatu manusia

Ø  System komputer

                Pemrosesan banyak job (tugas) pada system multiprogramming.

Ø  System jaringan komputer

                                Pemrosesan banyak paket yang dating dari banyak koneksi pada suatu host, bridge, gateway dll.

Ø  Representasi Queue

                Representasi Queue dapat dilakukan dengan dua cara, yaitu :

1. Representasi sekuen
2. Representasi sekuen linear
1. DEQUEUE (DOUBLE ENDED QUEUE)

                DEQUEUE adalah suatu List Linier, yang penambahan dan penghapusan elemen-nya dapat dilakukan pada kedua sisi ujung List, tetapi tidak dapat dilakukan ditengah-tengah list.

Deque menggunakan dua pointer penunjuk yaitu :

1. LEFT   : petunjuk untuk elemen pada posisi kiri

            2.   RIGHT : petunjuk untuk elemen pada posisi kanan

Ada dua jenis Dequeue :

 

Input-Restricted-Deque

adalah deque yang operasi pemasukan elemen datanya hanya dapat dilakukan di satu ujung kanannya (RIGHT), tetapi dapat menghapus dari kedua ujungnya ( LEFT dan RIGHT).

 

Output-Restricted-Deque

adalah deque yang operasi pemasukan elemen datanya dapat dilakukan melalui kedua ujungnya (LEFT dan RIGHT), tetapi hanya dapat menghapus dari ujung kanannya(RIGHT).

Kondisi antrian yang menjadi perhatian adalah :

ü  Penuh

                Bila elemen diatrian mencapai kapasitas maksimum antrian.

ü  Kosong

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

Operasi-operasi pengaksesan tambahan yang dapat dilakukan adalah :

1.       headQueue (Q), atau Front (Q, X) mengirim elemen terdepan tanpa menghapus.

2.       tailQueue (Q), mengirim elemen tanpa menghapusnya.

Operasi- operasi pada dequeue antara lain:

v  InitDQ, menciptakan dequeue kosong.

v  InsertDQ, menyisipkan ekemen ke dequeue terdiri dari:

v  Menyisipkan ke ujung kiri

v  Menyisipkan ke ujung kanan

v  RemoveDQ, mengambil elemen dari  dequeue terdiri dari:

v  Menghilangkan elemen di ujung kiri

v  Menghilangkan elemen di ujung kanan

v  LeftDQ, mengrim elemen di ujung kiri.

v  RightDQ, mengrim elemen di ujung kanan.

v  IsEmptyDQ, mengirim true jika dequeue kosong.

v  SizeDQ, mengir im jumlah elemen di dequeue.

Implementasi Queue dengan Linear Array

Disebut juga queue dengan model fisik, yaitu bagian depan queue selalu menempati posisi pertama array.

Operasi‐operasi queue dengan linear array:

1.       Create

2.       Empty

3.       Full

4.       EnQueue

5.       DeQueue

6.       Clear