Antrian dapat digambarkan sebagai struktur data linier non-primitif mengikuti urutan FIFO di mana elemen data dimasukkan dari satu ujung (ujung belakang) dan dihapus dari ujung lainnya (ujung depan). Variasi lain dari antrian adalah antrian bundar, antrian berakhir ganda dan antrian prioritas.
Grafik perbandingan
| Dasar untuk perbandingan | Antrian Linier | Antrian Bundar |
|---|---|---|
| Dasar | Mengatur elemen data dan instruksi secara berurutan satu demi satu. | Mengatur data dalam pola lingkaran di mana elemen terakhir terhubung ke elemen pertama. |
| Urutan pelaksanaan tugas | Tugas dieksekusi agar ditempatkan sebelumnya (FIFO). | Urutan pelaksanaan tugas dapat berubah. |
| Penyisipan dan penghapusan | Elemen baru ditambahkan dari ujung belakang dan dihapus dari depan. | Penyisipan dan penghapusan dapat dilakukan di posisi apa pun. |
| Performa | Tidak efisien | Bekerja lebih baik daripada antrian linier. |
Definisi Antrian Linier
Antrian Linear secara rasional merupakan daftar urutan pertama dan keluar pertama . Ini disebut linier karena menyerupai garis lurus di mana elemen diposisikan satu demi satu. Ini berisi koleksi elemen yang homogen di mana elemen baru ditambahkan di satu ujung dan dihapus dari ujung lainnya. Konsep antrian dapat dipahami dengan contoh antrian penonton yang menunggu di luar loket tiket untuk mendapatkan tiket teater. Dalam antrian ini, orang tersebut bergabung dengan ujung belakang antrian untuk mengambil tiket dan tiket dikeluarkan di ujung depan antrian.
Ada beberapa operasi yang dilakukan dalam antrian
- Pertama, antrian diinisialisasi ke nol (yaitu kosong).
- Tentukan apakah antrian kosong atau tidak.
- Tentukan apakah antrian penuh atau tidak.
- Penyisipan elemen baru dari ujung belakang (Enqueue).
- Penghapusan elemen dari ujung depan (Dequeue).
Antrian dapat diimplementasikan dalam dua cara
- Statis (Menggunakan array)
- Secara dinamis (Menggunakan pointer)
Keterbatasan antrian linier adalah bahwa ia menciptakan skenario di mana tidak ada elemen baru dapat ditambahkan dalam antrian bahkan jika antrian berisi ruang kosong. Situasi di atas diilustrasikan dalam gambar di bawah ini. Di sini bagian belakang menunjuk ke indeks terakhir sementara semua kotak masih kosong, tidak ada elemen baru yang dapat ditambahkan.
Definisi Antrian Sirkular
Antrian sirkular adalah varian dari antrian linier yang secara efektif mengatasi batasan antrian linier. Dalam antrian melingkar, elemen baru ditambahkan di posisi paling pertama dari antrian jika yang terakhir ditempati dan ruang tersedia. Ketika datang ke antrian linier, penyisipan dapat dilakukan hanya dari ujung belakang dan penghapusan dari ujung depan. Dalam antrian penuh setelah melakukan serangkaian penghapusan berturut-turut dalam antrian muncul situasi tertentu di mana tidak ada elemen baru dapat ditambahkan lebih lanjut bahkan jika ruang tersedia karena kondisi underflow (Belakang = maks - 1) masih ada.
Antrian sirkular menghubungkan kedua ujung melalui pointer di mana elemen pertama muncul setelah elemen terakhir. Itu juga melacak bagian depan dan belakang dengan menerapkan beberapa logika tambahan sehingga bisa melacak elemen yang akan dimasukkan dan dihapus. Dengan ini, antrian melingkar tidak menghasilkan kondisi luapan sampai antrian penuh dalam keadaan sebenarnya.
Beberapa kondisi diikuti oleh lingkaran antrian:
- Depan harus menunjuk ke elemen pertama.
- Antrian akan kosong jika Depan = Belakang.
- Ketika elemen baru ditambahkan, antrian bertambah dengan nilai satu (Belakang = Belakang + 1).
- Ketika sebuah elemen dihapus dari antrian, bagian depan bertambah satu (Depan = Depan + 1).
Perbedaan Kunci Antara Antrian Linier dan Antrian Sirkular
- Antrian linier adalah daftar berurutan di mana elemen data disusun dalam urutan berurutan. Sebaliknya, antrian bundar menyimpan data dengan cara melingkar.
- Antrian linier mengikuti urutan FIFO untuk menjalankan tugas (elemen yang ditambahkan di posisi pertama akan dihapus di posisi pertama). Sebaliknya, dalam antrian melingkar, urutan operasi yang dilakukan pada suatu elemen dapat berubah.
- Penyisipan dan penghapusan elemen diperbaiki dalam antrian linier yaitu, penambahan dari ujung belakang dan penghapusan dari ujung depan. Di sisi lain, antrian bundar mampu menyisipkan dan menghapus elemen dari titik mana pun sampai kosong.
- Antrian linier menghabiskan ruang memori sementara antrian sirkular membuat penggunaan ruang yang efisien.
Implementasi antrian linier
Algoritme yang diberikan di bawah ini mengilustrasikan penambahan elemen dalam antrian:
Antrian membutuhkan tiga variabel data termasuk satu array untuk menyimpan antrian dan lainnya untuk menyimpan posisi awal depan dan belakang yaitu -1.
masukkan (item, antrian, n, belakang) {if (belakang == n) lalu cetak "antrian melimpah"; lain {belakang = belakang + 1; antrian [belakang] = item; }} Algoritma yang diberikan di bawah ini menggambarkan penghapusan elemen dalam antrian:
delete_circular (item, antrian, belakang, depan) {if (belakang == depan) lalu cetak "antrian underflow"; lain {depan = depan + 1; item = antrian [depan]; }} Implementasi antrian melingkar
Algoritme untuk menafsirkan penambahan elemen dalam antrian melingkar:
insert_circular (item, antrian, belakang, depan) {belakang = (belakang + 1) mod n; if (depan == belakang) lalu cetak "antrian penuh"; else {queue [belakang] = item; }} Algoritma menjelaskan penghapusan elemen dalam antrian melingkar:
delete_circular (item, antrian, belakang, depan) {if (depan == belakang) lalu cetak ("antrian kosong"); lain {depan = depan + 1; item = antrian [depan]; }} Kesimpulan
Antrian linier tidak efisien dalam kasus-kasus tertentu di mana elemen-elemen diharuskan bergeser ke ruang kosong untuk melakukan operasi penyisipan. Itulah sebabnya ia cenderung menyia-nyiakan ruang penyimpanan sementara antrian bundar membuat penggunaan ruang penyimpanan yang tepat karena elemen ditambahkan pada posisi apa pun jika ada ruang kosong.
