Struktur Data Queue

 

Flowchart Strutur Data Queue

Pengertian Queue

Queue adalah struktur data linier yang menerapkan prinsip operasi dimana elemen data yang masuk pertama akan keluar lebih dulu. Prinsip ini dikenal dengan istilah FIFO (First In, First Out).

Contoh nyata dalam kehidupan sehari-hari yang dapat menggambarkan struktur data queue adalah barisan orang yang menunggu untuk membeli tiket di gedung bioskop.

Orang yang baru datang akan bergabung dengan barisan dari ujung dan orang yang berdiri di depan akan menjadi yang pertama mendapatkan tiket dan meninggalkan barisan. Demikian pula dalam struktur data queue, data yang ditambahkan terlebih dahulu akan meninggalkan antrian terlebih dahulu.

Berikut ini adalah ilustrasi dari queue

Pada gambar di atas, karena elemen 1 ditambahkan ke antrian lebih dulu daripada 2, maka 1 adalah elemen yang pertama dihapus dari antrian. Hal ini mengikuti aturan operasi FIFO.

Dalam istilah pemrograman, menempatkan item dalam struktur data queue disebut enqueue, sedangkan operasi menghapus item dari queue disebut dequeue.

Kita dapat mengimplementasikan queue dalam bahasa pemrograman apa pun seperti C, C++, Java, Python atau C#, dengan spesifikasi yang hampir sama.

Jenis-jenis Queue

Secara umum ada 4 jenis struktur data queue, meliputi:

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. Penyisipan terjadi di akhir antrian dan penghapusan di depan antrian.

3. Priority Queue

Priority Queue adalah strruktur 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.

Fungsi dan Kegunaan Queue

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

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

Kelebihan Queue

Kelebihan queue di antarnya:

• 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 dapat 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 konvensional, 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

flowchart queue program