Baris boleh digambarkan sebagai struktur data linier bukan primitif mengikut susunan FIFO di mana elemen data dimasukkan dari satu hujung (hujung belakang) dan dipadamkan dari hujung yang lain (front end). Variasi lain dalam baris gilir adalah giliran pekeliling, giliran berlarutan dan giliran keutamaan.
Carta Perbandingan
| Asas untuk perbandingan | Giliran Linear | Giliran bergaris |
|---|---|---|
| Asas | Mengatur elemen data dan arahan dalam urutan berurut satu demi satu. | Mengatur data dalam corak bulat di mana unsur terakhir disambungkan ke elemen pertama. |
| Perintah pelaksanaan tugas | Tugas dilaksanakan mengikut urutan sebelum diletakkan (FIFO). | Perintah melaksanakan tugas boleh berubah. |
| Memasukkan dan pemadaman | Unsur baru ditambah dari hujung belakang dan dikeluarkan dari depan. | Pemasukan dan pemadaman boleh dilakukan di mana-mana jawatan. |
| Prestasi | Tidak cekap | Kerja lebih baik daripada baris gilir linear. |
Takrifan Giliran Linear
Antrian Linear adalah rasional yang pertama dalam senarai pertama yang diperintahkan. Ia dipanggil linier kerana ia menyerupai garis lurus di mana unsur-unsur diposisikan satu demi satu. Ia mengandungi koleksi homogen unsur-unsur di mana unsur-unsur baru ditambah pada satu hujung dan dipadamkan dari hujung yang lain. Konsep barisan boleh difahami oleh contoh antrian penonton yang menunggu di luar meja tiket untuk mendapatkan tiket teater. Dalam giliran ini, orang menyertai hujung belakang barisan untuk mengambil tiket dan tiket dikeluarkan di hujung depan barisan.
Terdapat beberapa operasi yang dilakukan dalam barisan
- Pertama giliran adalah diisytiharkan kepada sifar (iaitu kosong).
- Tentukan sama ada barisan kosong atau tidak.
- Tentukan jika giliran penuh atau tidak.
- Memasukkan elemen baru dari bahagian belakang (Enqueue).
- Memotong elemen dari bahagian hadapan (Dequeue).
Baris boleh dilaksanakan dalam dua cara
- Secara statik (menggunakan array)
- Secara dinamik (Menggunakan petunjuk)
Batasan baris gilir linear adalah bahawa ia mewujudkan senario di mana tiada elemen baru boleh ditambah dalam barisan walaupun giliran mengandungi ruang kosong. Situasi di atas digambarkan dalam angka yang diberikan di bawah. Di sini belakang menunjuk ke indeks terakhir sementara semua kotak masih kosong, tiada elemen baru boleh ditambah.
Definisi Giliran Pekeliling
Antrian bulat adalah varian baris gilir linear yang secara efektif mengatasi batas baris gilir linear. Dalam giliran pekeliling, elemen baru ditambah pada kedudukan pertama giliran jika yang terakhir diduduki dan ruang tersedia. Ketika datang ke barisan linear penyisipan dapat dilakukan hanya dari ujung belakang dan penghapusan dari ujung depan. Dalam giliran penuh selepas melakukan siri penghapusan berturut-turut dalam barisan timbul keadaan tertentu di mana tiada elemen baru boleh ditambah lagi walaupun ruang tersedia kerana keadaan underflow (Rear = max - 1) masih ada.
Giliran giliran pekeliling menghubungkan kedua hujung melalui penunjuk di mana unsur pertama muncul selepas elemen terakhir. Ia juga menjejaki bahagian depan dan belakang dengan melaksanakan beberapa logik tambahan supaya ia dapat mengesan unsur-unsur yang akan dimasukkan dan dihapuskan. Dengan ini, giliran pekeliling tidak menjana keadaan limpahan sehingga barisan penuh dalam sebenarnya.
Beberapa syarat diikuti dengan giliran pekeliling:
- Barisan hadapan harus menunjuk ke elemen pertama.
- Antrian akan kosong jika Front = Belakang.
- Apabila elemen baru ditambah, gilir bertambah dengan nilai satu (Belakang = Belakang + 1).
- Apabila elemen dipadamkan dari baris gilir, depan akan ditambah oleh satu (Front = Front + 1).
Perbezaan Kekunci Antara Giliran Baris dan Giliran Baris
- Antrian linear adalah senarai yang diperintahkan di mana elemen data diatur dalam urutan berurutan. Sebaliknya, giliran pekeliling menyimpan data dalam bentuk pekeliling.
- Giliran linear mengikuti perintah FIFO untuk melaksanakan tugas (elemen yang ditambahkan pada posisi pertama akan dipadamkan di kedudukan pertama). Sebaliknya, dalam giliran pekeliling, susunan operasi yang dilakukan pada elemen mungkin berubah.
- Penyisipan dan pemadaman unsur-unsur ditetapkan dalam baris gilir linier iaitu, tambahan dari hujung belakang dan penghapusan dari hujung depan. Sebaliknya, giliran pekeliling mampu memasukkan dan memadam unsur dari mana-mana titik sehingga ia tidak didiami.
- Antrean linear membuang ruang ingatan semasa barisan pekeliling membuat penggunaan ruang yang efisien.
Pelaksanaan baris gilir linear
Algoritma yang diberikan di bawah menggambarkan penambahan unsur dalam barisan:
Antrian memerlukan tiga pembolehubah data termasuk satu array untuk menyimpan barisan dan lain-lain untuk menyimpan kedudukan awal dan belakang awal -1.
masukkan (item, giliran, n, belakang) {jika (belakang == n) maka cetak "limpasan beratur"; lain {belakang = belakang + 1; giliran [belakang] = item; }} Algoritma yang diberikan di bawah menggambarkan pemadaman elemen dalam barisan:
delete_circular (item, baris gilir, belakang, depan) {jika (belakang == front) maka cetak "undercover beratur"; lain {front = front + 1; item = antrean [depan]; }} Pelaksanaan giliran pekeliling
Algoritma untuk mentafsir penambahan unsur dalam giliran pekeliling:
insert_circular (item, baris gilir, belakang, depan) {belakang = (belakang + 1) mod n; jika (depan == belakang) maka mencetak "barisan penuh"; lain {giliran [belakang] = item; }} Algoritma menerangkan pemadaman unsur dalam giliran pekeliling:
delete_circular (item, baris gilir, belakang, depan) {if (front == rear) kemudian cetak ("barisan kosong"); lain {front = front + 1; item = antrean [depan]; }} Kesimpulannya
Antrian linear adalah tidak cekap dalam beberapa kes di mana elemen diperlukan untuk beralih ke ruang kosong untuk melakukan operasi penyisipan. Itulah sebabnya ia cenderung membuang ruang penyimpanan sementara barisan pekeliling membuat penggunaan ruang penyimpanan yang sesuai kerana unsur-unsur itu ditambah di mana-mana jawatan jika ada ruang kosong.
