Sıra, ilkel olmayan doğrusal veri yapısı olarak tanımlanabilir, veri öğelerinin bir uçtan (arka uç) yerleştirildiği ve diğer uçtan (ön uç) silindiği FIFO sırasını izler. Kuyruğun diğer varyasyonları, dairesel kuyruk, iki kat sona ermiş kuyruk ve öncelik sırasıdır.
Karşılaştırma Tablosu
| Karşılaştırma için temel | Doğrusal Sıra | Dairesel Kuyruk |
|---|---|---|
| Temel | Veri öğelerini ve komutları art arda sırayla düzenler. | Verileri, son elemanın birinci elemana bağlı olduğu dairesel düzende düzenler. |
| Görev yürütme sırası | Görevler daha önce yerleştirildikleri sırada yürütülür (FIFO). | Bir görevi yürütme sırası değişebilir. |
| Ekleme ve silme | Yeni eleman arka uçtan eklenir ve önden çıkarılır. | Yerleştirme ve silme, herhangi bir pozisyonda yapılabilir. |
| performans | Yetersiz | Doğrusal sıradan daha iyi çalışır. |
Linear Queue'un tanımı
Doğrusal bir sıra rasyonel olarak ilk sırada yer alan listede ilk sıradadır. Buna doğrusal denir, çünkü elemanların birbiri ardına yerleştirildiği düz bir çizgiye benzer. Bir ucuna yeni elemanların eklendiği ve diğer ucundan silindiği elementlerin homojen bir koleksiyonunu içerir. Kuyruk kavramı, tiyatro biletini almak için bilet tezgahının dışında bekleyen seyircilerin bir kuyruğu örneği ile anlaşılabilir. Bu sırada kişi, bileti almak için sıranın arka ucuna katılır ve bilet kuyruğun ön ucunda düzenlenir.
Kuyrukta gerçekleştirilen birkaç işlem var.
- İlk önce sıra sıfıra başlatılır (yani boş).
- Sıranın boş olup olmadığını belirleyin.
- Kuyruğun dolu olup olmadığını belirleyin.
- Yeni elemanın arka uçtan sokulması (Enqueue).
- Elemanın ön uçtan silinmesi (Dequeue).
Sıra iki şekilde uygulanabilir
- Statik (Dizileri kullanma)
- Dinamik olarak (İşaretçileri kullanma)
Doğrusal sıranın sınırlaması, sıra boş alanları içerse bile sıraya hiçbir yeni öğenin eklenemeyeceği bir senaryo oluşturmasıdır. Bu yukarıdaki durum, aşağıda verilen şekilde gösterilmiştir. Burada, tüm kutular hala boş iken arka, son dizine işaret ediyor, yeni bir eleman eklenemiyor.
Dairesel Sıranın Tanımı
Dairesel bir sıra, doğrusal sıranın sınırlamasını etkili bir şekilde aşan doğrusal sıranın bir değişkenidir. Dairesel kuyruğunda, en son işgal edilirse ve boşluk varsa, yeni eleman sıranın ilk konumuna eklenir. Doğrusal sıraya gelince, ekleme yalnızca arka uçtan ve ön uçtan silinerek gerçekleştirilebilir. Sıradaki bir dizi art arda silme işleminin gerçekleştirilmesinden sonra tam bir sırada, alt alan koşulu (Arka = maks - 1) hala mevcut olduğu için mevcut alan olsa bile yeni eleman eklenemediği belli bir durum ortaya çıkar.
Dairesel kuyruk, iki ucu, ilk elemanın son elemandan sonra geldiği bir işaretçi ile birleştirir. Ayrıca, eklenmesi ve silinmesi gereken unsurları izleyebilmesi için fazladan bir mantık uygulayarak ön ve arka kısımları izler. Bununla, dairesel sıra, tam olarak dolana kadar taşma koşulunu oluşturmaz.
Dairesel kuyruğu izleyen bazı koşullar:
- Ön, birinci elemana işaret etmelidir.
- Ön = Arka ise kuyruk boş olacaktır.
- Yeni bir eleman eklendiğinde sıra bir değer artar (Arka = Arka + 1).
- Bir öğe kuyruktan silindiğinde, ön bir artırılır (Ön = Ön + 1).
Doğrusal Kuyruk ve Dairesel Kuyruk Arasındaki Temel Farklılıklar
- Doğrusal sıra, veri öğelerinin sıralı düzende düzenlendiği sıralı bir listedir. Buna karşın, dairesel sıra, verileri dairesel biçimde saklar.
- Doğrusal sıra, görevi yürütmek için FIFO sırasını izler (ilk konumda eklenen öğe ilk konumda silinecek). Tersine, dairesel sırada, bir eleman üzerinde gerçekleştirilen işlemlerin sırası değişebilir.
- Elementlerin yerleştirilmesi ve silinmesi, lineer sırada sabitlenir, yani, arka taraftan eklenir ve ön taraftan silinir. Öte yandan, dairesel sıra, kullanılmayana kadar herhangi bir noktadan öğeyi ekleme ve silme yeteneğine sahiptir.
- Doğrusal sıra bellek boşluğunu boşa harcar, dairesel sıra ise boş alanı verimli kullanır.
Doğrusal sıranın uygulanması
Aşağıda verilen algoritma, sıradaki öğelerin eklenmesini gösterir:
Sıra, kuyruğu saklamak için bir dizi, diğeri ise -1 olan ön ve arka başlangıç konumunu saklamak için üç veri değişkenine ihtiyaç duyar.
eklemek (madde, sıra, n, arka) {if (rear == n) sonra "sıra taşması" yazdır; başka {rear = arka + 1; sıra [arka] = madde; }} Aşağıda verilen algoritma, sıradaki öğelerin silinmesini gösterir:
delete_circular (öğe, sıra, arka, ön) {if (rear == front) sonra "sıra altını" yazdır; başka {front = front + 1; item = kuyruk [ön]; }} Dairesel kuyruğun uygulanması
Elemanın dairesel sıraya eklenmesini yorumlayan bir algoritma:
insert_circular (öğe, sıra, arka, ön) {rear = (rear + 1) mod n; eğer (ön == arka) sonra "kuyruk dolu"; else {kuyruk [arka] = madde; }} Algoritma, dairesel sıradaki öğenin silinmesini açıklar:
delete_circular (öğe, sıra, arka, ön) {if (front == rear) sonra yazdır ("sıra boş"); başka {front = front + 1; item = kuyruk [ön]; }} Sonuç
Doğrusal sıra, bazı durumlarda yerleştirme işlemini gerçekleştirmek için elemanların boş alanlara kayması gereken durumlarda verimsizdir. Depolama alanını boşaltma eğiliminde olmasının nedeni budur, dairesel sıra boş bir alan varsa, elemanlar herhangi bir pozisyonda eklendikçe uygun depolama alanını kullanır.
