Sebagai warga negara Indonesia, antrian bisa dibilang sudah menjadi bagian hidup sehari-hari. Dari berdesakan di terminal bus hingga menunggu giliran di kantor pelayanan publik, antrian selalu terlihat di mana saja. Hal yang sama juga bisa diterapkan pada sistem komputer atau bahkan dalam matematika.
Salah satu istilah matematika yang menggunakan sistem antrian adalah queue. Queue merupakan sebuah struktur data yang digunakan untuk menyimpan koleksi elemen atau data. Dalam ilmu matematika, queue ini dikenal sebagai model yang menggambarkan perilaku sistem antrian pada suatu tempat atau waktu tertentu.
Dalam queue, proses penambahan elemen hanya dapat dilakukan di ujung tail atau ekor, sementara penghapusan elemen hanya dapat dilakukan di ujung head atau kepala. Antrian ini memiliki konsep First In First Out (FIFO), artinya elemen yang pertama masuk ke dalam antrian akan menjadi elemen pertama yang keluar dari antrian.
Hanya elemen yang berada di depan antrian yang bisa diakses atau dihapus dalam sebuah sistem queue. Hal ini disebabkan karena elemen yang di dalam antrian tadi memiliki urutan tertentu atau biasa disebut prioritas. Sebagai contoh, dalam sistem antrian di toko bunga, pelanggan yang datang duluan akan mendapatkan pelayanan lebih dahulu daripada pelanggan yang datang kemudian.
Karakteristik Queue
Queue atau antrian adalah struktur data yang terdiri dari serangkaian elemen yang disusun dalam urutan tertentu. Di dalam queue, elemen baru atau data baru dimasukkan di sisi belakang antrian, sementara elemen lama atau data sudah terproses akan keluar melalui sisi depan antrian. Dengan kata lain, queue menerapkan konsep FIFO, First In First Out, yaitu elemen yang pertama masuk akan menjadi yang pertama keluar.
Selain karakteristik FIFO, terdapat beberapa karakteristik queue lainnya, seperti:
1. Limited Size
Queue memiliki batasan ukuran yang telah ditentukan. Jika sudah mencapai batasan tersebut, antrian tidak dapat menampung elemen baru dan akan menghasilkan error. Pembatasan ukuran ini berguna untuk menghindari terjadinya kelebihan memori dan memastikan performance program tetap optimal.
2. Access Restricted to Front and Rear End
Pengaksesan elemen dalam queue hanya bisa dilakukan pada bagian depan dan belakang antrian, yaitu elemen pertama dan elemen terakhir. Tidak ada metode untuk mengakses elemen di posisi tengah antrian secara langsung. Jadi, jika ingin mengambil elemen di tengah, kita harus mengeluarkan elemen pada sisi depan secara berkala hingga elemen yang diinginkan berada di posisi depan.
3. Suatu elemen hanya dapat menjadi bagian dari satu antrian
Elemen pada sebuah queue hanya dapat menjadi bagian dari satu antrian. Artinya, tidak ada elemen yang dapat dimasukkan ke dalam dua antrian yang berbeda secara sekaligus. Hal ini memastikan validitas dan konsistensi data yang ada di dalam queue.
4. Akses elemen dalam suatu antrian tidak dapat dilakukan secara acak (random)
Sebagaimana disebutkan pada poin kedua, pengaksesan elemen hanya dapat dilakukan pada bagian depan dan belakang. Oleh karena itu, pengaksesan elemen dalam sebuah antrian tidak dapat dilakukan secara acak atau random. Jika ingin mengambil elemen di posisi tertentu, harus dilakukan secara bergantian dari elemen pertama.
Dalam dunia pemrograman, queue adalah sebuah komponen penting yang digunakan dalam banyak aplikasi, seperti simulasi antrian, sistem operasi, bahkan dalam beberapa jenis game.
Implementasi Queue dengan Array
Array adalah salah satu cara umum untuk menerapkan queue. Dalam implementasi ini, queue diwakili oleh sebuah array satu dimensi. Setiap elemen dalam array merepresentasikan elemen pada antrian yang sesuai. Pada umumnya, operasi enqueue akan dilakukan pada akhir array, sedangkan operasi dequeue akan dilakukan pada elemen pertama yang berada pada array.
Keuntungan menggunakan array untuk implementasi queue terutama pada kecepatan akses elemen yang sangat cepat. Namun, kekurangan dari metode ini terletak pada ukuran array yang harus ditentukan pada saat pertama kali dibuat. Hal ini menyebabkan ukuran queue yang bisa ditampung terbatas, dan membutuhkan alokasi ulang memori apabila kapasitas maksimal sudah tercapai.
Implementasi Queue dengan Linked List
Linked list adalah salah satu metode lain yang dapat digunakan untuk implementasi queue. Dalam linked list ini, setiap elemen disimpan dalam bentuk simpul atau node. Setiap node memiliki data dan pointer ke simpul berikutnya dalam queue.
Keuntungan dari penggunaan linked list adalah ukuran queue yang dapat ditampung tidak terbatas, karena setiap node hanya akan dialokasikan ketika diperlukan. Namun, kekurangan dari metode ini adalah akses node mungkin memerlukan lebih banyak waktu dibandingkan dengan array, karena harus dilakukan traversal dari awal linked list hingga mencapai simpul yang diinginkan.
Implementasi Queue dengan Circular Buffer
Circular buffer merupakan metode lain yang dapat digunakan untuk implementasi queue. Dalam metode ini, queue diimplementasikan sebagai array satu dimensi dengan indeks yang diatur sedemikian rupa sehingga penambahan elemen ke queue selalu dilakukan pada indeks tertentu, dan dilakukan secara circular.
Keuntungan dari penggunaan circular buffer adalah meminimalkan alokasi ulang memori dan mempercepat akses elemen pada antrian. Namun, kekurangan dari metode ini adalah ukuran buffer harus didefinisikan pada saat pertama kali diinisialisasi, sehingga ukuran maksimal dari queue terbatas.
Implementasi Queue dengan Doubly Linked List
Doubly linked list adalah salah satu cara lain untuk mengimplementasikan queue. Dalam metode ini, tiap elemen disimpan dalam bentuk simpul dua arah. Setiap simpul memiliki pointer untuk mengakses simpul sebelum dan sesudahnya.
Keuntungan dari penggunaan doubly linked list adalah penggunaan konsep dua arah sehingga mempermudah dalam mengakses dan memanipulasi elemen dalam queue. Namun, kekurangan dari metode ini adalah alokasi memori yang lebih besar dan kompleksitas yang lebih tinggi dibandingkan dengan metode linked list.
Kegunaan Queue dalam Berbagai Bidang
Queue atau antrian memiliki banyak kegunaan dalam berbagai bidang. Salah satu yang paling umum adalah pada sistem antrian seperti ATM, restoran, atau penerbangan. Penggunaan queue di sini adalah untuk mengatur urutan antrean agar lebih rapi dan terkoordinasi. Hal ini juga membantu dalam mengurangi waktu tunggu bagi pelanggan yang mengantre. Selain itu, antrian memudahkan pembagian tugas dan pelayanan secara adil dan merata.
Queue juga berperan penting dalam dunia komputasi. Algoritma BFS atau breadth-first search memanfaatkan struktur data queue untuk mengeksplorasi graf dengan cara memproses simpul-simpul pada level yang sama dahulu, baru kemudian ke level selanjutnya. Queue pada algoritma BFS membantu dalam mencari jalur terpendek antara dua titik pada graf.
Pada sistem operasi, queue memiliki peran penting dalam mengatur proses yang melalui CPU. CPU hanya dapat menangani satu proses pada satu waktu. Oleh karena itu, ketika ada beberapa proses yang membutuhkan layanan CPU, OS akan menempatkannya pada antrian (queue) dan mengatur prioritasnya untuk dijalankan berdasarkan keadaan tertentu. Dengan demikian, penggunaan queue pada OS dapat mengoptimalkan penggunaan resource yang ada.
Pada dunia game development, queue juga memiliki banyak manfaat. Queue sering digunakan ketika memanipulasi orde dan waktu. Ketika ada banyak karakter atau objek dalam sebuah game, queue dapat digunakan untuk menentukan siapa yang harus melakukan tugas tertentu atau dimunculkan terlebih dahulu.
Selain itu, penggunaan queue pada game development dapat membantu meningkatkan efisiensi dan meminimalkan overhead yang tidak diperlukan.
Demikian Penjelasan dari pakguru.co.id, terima kasih sudah membaca.
