QUEUE

Ilustrasi

Contoh Antrian : Antrian printer, Antrian Tiket Bioskop, Antrian pada kasir sebuah bank

Ketika seorang pelanggan datang, akan menuju ke belakang dari antrian, setelah pelanggan dilayani, antrian yang berada di depan akan maju. Queue berguna untuk menyimpan pekerjaan yang tertunda.

PENGERTIAN

Queue (antrian) adalah struktur data dimana proses pengambilan dan penambahan elemen dilakukan pada ujung berbeda. Queue mengikuti konsep FIFO, FIFO (First In First Out) adalah elemen yang pertama masuk akan menjadi elemen pertama kali keluar.

QUEUE DAN STACK

Karakteristik yang membedakan queue (antrian) dari stack adalah cara menyimpan dan mengambil data dengan struktur First In First Out (FIFO). Hal ini berarti elemen pertama yang ditempatkan pada queue adalah yang pertama dipindahkan.

ENQUEUE

Enqueue : yaitu proses penambahan elemen pada queue.

Elemen ditempatkan pada ujung (tail)

DEQUEUE

Dequeue : yaitu proses pengambilan elemen pada queue.

Mimindahkan elemen dari kepala (head) sebuah queue

Penambahan dilakukan pada bagian belakang sedangkan Pengambilan dilakukan pada bagian depan (elemen yang pertama masuk)

ILUSTRASI

KARAKTERISTIK QUEUE

• Elemen antrian yaitu item - item data yang terdapat di elemen antrian
• Front
• Rear
• Jumlah elemen pada antrian (count)
• Status antrian

FRONT DAN REAR

Front : pointer bantu yang digunakan untuk menunjuk elemen yang paling depan

Rear : pointer bantu yang digunakan untuk menunjuk elemen yang paling belakang

KOSONG

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

GAMBAR PROSES QUEUE (ANTRIAN)

OPERASI PADA QUEUE

1.  Deklarasi
2. Inisialisasi
3. Cek Kosong
4. Cek Penuh
5. Penambahan
6. Pengambilan
7. Pengaksesan

DEKLARASI

Proses yang harus dilakukan pertama kali adalah deklarasi/menyiapkan tempat. Langkah yang harus dilakukan adalah: 

• Deklarasi class
• Deklarasi struktur data (menggunakan array atau linked list)
• Deklarasi pointer front dan rear
• Deklarasi variabel size untuk menyimpan besar array.
• Deklarasi variabel jumlah untuk mengetahui banyak item yang disimpan pada queue.

INISIALISASI

Merupakan proses pemberian nilai awal. 

Pada Array:

    1. Pembentukan obyek array beserta ukurannya.

        antrian = new int [10];

            (pembentukan obyek array yang memiliki 10 elemen, dan alamat obyek akan disimpan                 pada variabel bernama antrian)
    2. Pemberian nilai awal pada variabel front = 0 dan belakang = -1

        front = 0;

        rear = -1;

Pada Linked List:

Proses inisialisasi dilakukan dengan memberikan nilai awal pada variabel head, tail front dan rear dengan nilai null.

        head = tail = front = rear = null;

FUNGSI CREATE

Digunakan untuk membentuk dan menunjukan awal terbentuknya suatu Antrean/Queue

CEK KOSONG (IsEmpty)

Operasi yang digunakan untuk mengecek kondisi queue dalam keadaan kosong

Pada Array: menggunakan pengecekan pada variabel jumlah_item. Jika nilainya = 0 berarti queue dalam kondisi kosong

Pada linked list: dapat menggunakan pengecekan front atau rear jika nilainya null berarti queue kosong.

Operasi ini harus dapat mengembalikan nilai true jika queue kosong dan false jika sebaliknya

CEK PENUH (IsFull)

Operasi yang hanya dapat diterapkan pada queue yang menggunakan array

Operasi ini digunakan untuk mengecek kondisi queue dalam keadaan penuh

Caranya : Melihat nilai pada variabel jumlah item. Jika nilainya = size=1 (dimana size adalah ukuran array) maka dapat diindikasikan queue dalam kondisi penuh

Operasi ini harus dapat mengembalikan nilai true jika queue penuh dan false jika sebaliknya

FUNGSI ENQUEUE

Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu dilakukan pada elemen paling belakang

Penambahan elemen selalu menggerakan variabel tail dengan cara menambahkan tail terlebih dahulu

FUNGSI DEQUEUE

Digunakan untuk menghapus elemen terdepan (head) dari antrian, dengan cara:

Menggeser semua antrian kedepan dan mengurangi tail dengan 1. Penggeseran dilakukan dengan menggunakan looping

FUNGSI CLEAR

Untuk menghapus elemen - elemen antrian dengan cara membuat tail dan head = -1

Penghapusan elemen - elemen antrian sebenarnya tidak menghapus arraynya, namun hanya menggeser indeks pengaksesan-nya ke nilai -1 sehingga elemen - elemen antrian tidak lagi terbaca sehingga mengembalikan antrian seperti keadaan semula

JENIS - JENIS QUEUE

Secara umum ada 4 jenis struktur data queue, meliputi :

1. Simple queue
2. Circular queue
3. Priority queue
4. Double - ended queue (Dequeue)

1. SIMPLE QUEUE

Simple queue adalah struktur data queue paling dasar di mana penyisipan item dilakukan di simpul belakang (rear atau tail) dan penghapusan terjadi di simpul depan (front atau head)

2. CIRCULAR QUEUE

Pada circular queue, simpul terakhir terhubung ke simpul pertama. Queue jenis ini juga dikenal sebagai Ring Buffer karena semua ujungnya terhubung ke ujung yang lain. Penyisispan terjadi di akhir antrian dan penghapusan di depan antrian.

3. PRIORITY QUEUE

Priority queue adalah struktur data queue dimana simpul akan memiliki beberapa prioritas yang telah ditentukan. Simpul dengan prioritas terbesar akan menjadi yang pertama dihapus dari antrian. Sedangkan penyisipan item terjadi sesuai urutan kedatangannya.

Aplikasi priority queue antara lain algoritma jalur terpendek Dijkstra, algoritma prim, dan teknik kompresi data seperti kode Huffman

4. DOUBLE - ENDED QUEUE (DEQUEUE)

Dalam double - ended queue (dequeue), operasi penyisipan dan penghapusan dapat terjadi di ujung depan dan belakang dari queue

ANTRIAN BERPRIORITAS

Struktur data queue umumnya digunakan untuk mengelola thread dalam multithreading dan menerapkan sistem antrian prioritas pada program komputer. Dalam antrian yang telah dibahas sebelum, semua elemen yang masuk dalam antrian, dianggap mempunyai prioritas yang sama, sehingga elemen yang masuk lebih dahulu akan diproses lebih dahulu. Dalam praktek, elemen - elemen yang akan masuk dalam suatu antrian ada yang dikatakan mempunyai prioritas yang lebih tinggi dibanding yang lain. Antrian yang demikian ini disebut dengan antrian berprioritas (priority queue)

FUNGSI QUEUE

Berikut ini adalah beberapa fungsi queue yang paling umum dalam struktur data:

1. Queue banyak digunakan untuk menangani lalu lintas (traffic) situs web.
2. Membantu untuk mempertahankan playlist yang ada pada aplikasi media player
3. Queue digunakan dalam sistem operasi untuk menangani interupsi.
4. Membantu dalam melayani permintaan pada suatu sumber daya bersama seperti printer, penjadwalan tugas CPU, dll.
5. Digunakan dalam transfer data asinkronus misal pipeline, IO file, dan socket.

KELEBIHAN QUEUE

Kelebihan queue diantaranya :

• Data dalam jumlah besar dapat dikelola secara efisien
• Operasi seperti penyisipan dan penghapusan dapat dilakukan dengan mudah karena mengikuti aturan masuk pertama keluar pertama.
• Queue berguna ketika layanan tertentu digunakan oleh banyak konsumen
• Queue cepat untuk komunikasi antar - proses data.
• Queue cepat digunakan dalam implementasi struktur data lainnya.

KEKURANGAN QUEUE

Kelemahan struktur data queue adalah sebagai berikut:

• Operasi seperti penyisipan dan penghapusan elemen dari tengah cenderung banyak memakan waktu
• Dalam queue konvesional, elemen baru hanya dapat dimasukkan ketika elemen yang ada dihapus dari antrian
• Mencari elemen data pada struktur queue membutuhkan time complexity O(N)
• Ukuran maksimum antrian harus ditentukan sebelumnya