Kuyruklar

Bu yazı BLM212 Veri Yapıları dersinin kuyruk konusu için hazırlanmış bir çalışma dosyası. Ders notlarından yola çıkılarak yapay zekâ ile derlendi ve düzenlendi. Ortadaki dairesel kuyruk kendi enqueue ve dequeue'suyla sürülebiliyor — o bölümün iddiası, modülün boşalan hücreleri yeniden kullanılabilir kıldığı; front hâlâ ortalardayken rear'ın 5'ten 0'a sardığı o tek hamle ise bitmiş bir şemanın gösteremeyeceği şeyin ta kendisi.

Kuyruk nedir?

Kuyruk da kısıtlı bir doğrusal listedir; ama yığından farklı olarak iki ucu birden kullanır: veri rear'dan girer, front'tan çıkar. İlk giren ilk çıkar — FIFO. Veriler kuyruğa alındıkları sırayla işlenir.

Günlük hayattaki her sıra bir kuyruktur: market kasası, yazıcı sırası, işletim sisteminin görev sırası. Adalet gereken her yerde onu uygulayan şey FIFO'dur.

front

Kuyruğun başı — çıkış ucu. Silme buradan yapılır.

rear

Kuyruğun sonu — giriş ucu. Ekleme buradan yapılır.

FIFO

First In – First Out. Yığının LIFO'sunun tam tersi.

Sıra korunur

Yığın sırayı tersine çevirir, kuyruk korur. Kullanım alanlarındaki bütün fark buradan gelir.

Dört işlem

Dört temel işlem var: ikisi kuyruğu değiştirir, ikisi yalnızca okur. Bunlara create ve destroy eklenir.

enqueue

Kuyruğun sonuna bir eleman ekler. Yer yoksa overflow.

dequeue

Kuyruğun başından bir eleman siler ve döndürür. Kuyruk boşsa underflow.

queueFront

Baştaki elemanı okur, silmez.

queueRear

Sondaki elemanı okur, silmez.

createQueue

Baş yapısını front = null, rear = null ve count = 0 ile kurar.

destroyQueue

Tüm düğümleri ve baş yapısını sisteme geri verir.

Kuyruğu değiştiren iki işlemin de birer özel durumu var ve kuyruk kodundaki bütün zorluk bu ikisinden ibaret. enqueue'nunki boş kuyruk:

Algorithm enqueue (queue, item)
1 if (queue full) return false
2 allocate (newPtr)
3 newPtr->data = item
4 newPtr->next = null
5 if (queue->count is 0)              // boş kuyruğa ekleme
   1  queue->front = newPtr
6 else
   1  queue->rear->next = newPtr
7 queue->rear  = newPtr
8 queue->count = queue->count + 1
9 return true

Kuyruk boşsa front da yeni düğüme çevrilmelidir — yoksa kuyruğun başı hiçbir yeri göstermez. dequeue'nun özel durumu ise bunun ayna görüntüsü: son elemanın çıkması.

Algorithm dequeue (queue, item)
1 if (queue->count is 0) return false
2 item       = queue->front->data
3 deleteLoc  = queue->front
4 if (queue->count is 1)              // son eleman siliniyor
   1  queue->rear = null
5 queue->front = queue->front->next
6 queue->count = queue->count - 1
7 recycle (deleteLoc)
8 return true

Son eleman çıkarken rear da null yapılmalıdır; yoksa geriye sisteme iade edilmiş bir düğümü gösteren sarkık bir işaretçi kalır.

Geri kalan her şey rutin bağlı liste işidir. queueFront ile dequeue, silme kısmı dışında birebir aynıdır: önce kuyruk boş mu diye bakılır, boşsa false döner; değilse veri dataOut üzerinden geri iletilip true döndürülür.

Bağlı liste ile

Baş yapısı yığındakinden bir alan fazladır: front, rear ve count. Düğümler tek yönlü bağlıdır ve zincir daima front'tan rear'a doğru akar.

Geriye doğru bağ yoktur ve gerekmez de: silme front'tan yapılır, yani zaten bulunduğun yerden.

Dizi ve dairesellik

Kuyruğu diziyle gerçekleştirmek ilk bakışta kolay görünür — front ve rear birer indeks olur. Ama düz bir dizide kuyruk sağa doğru sürünür ve sol taraf bomboş dururken kendini dolu ilan eder.

Çözüm modüler aritmetik:

enqueue:  rear  = (rear  + 1) % maxSize
dequeue:  front = (front + 1) % maxSize

Son indekse gelindiğinde % değeri 0'a sarar; böylece soldaki boşalan hücreler yeniden kullanıma girer.

Geriye klasik bir tuzak kalır. Dairesel dizide front == rear hem tam boş hem de tam dolu durumunda oluşabilir — iki durum yalnızca indekslerden ayırt edilemez. Bu yüzden ayrı bir count alanı tutulur: count == 0 boş, count == maxSize dolu.

Denemeye değer: altı kez enqueue, sonra üç kez dequeue, sonra tekrar enqueue. rear'ın halkada 5'ten 0'a atladığını ve boşalan hücreleri yeniden kullandığını göreceksin — düz dizide mümkün olmayan şey buydu. Sınırlardayken düğmelere basmak da denemeye değer; sözde kodun ilk satırlarındaki iki kontrolün varlık sebebi orada görünür.

Kuyruk teorisi

Kuyruk teorisi, kuyrukların performansını tahmin etmek için kullanılan uygulamalı matematik ve bilgisayar bilimleri alanıdır. Veri yapısından çok, o veri yapısıyla modellenen gerçek dünyayı inceler.

single-server queue

Aynı anda yalnızca bir müşteriye hizmet verir — köşe başındaki büfe.

multi-server queue

Aynı anda birden fazla müşteriye hizmet verir — banka, postane.

multiqueues

Birden çok tek sunuculu kuyruk yan yana — market kasaları.

Terimleri tam olarak bilmek gerekiyor, çünkü tahminler bunlardan kuruluyor:

customer

Hizmete ihtiyacı olan herhangi bir kişi ya da şey — bir yazdırma işi de müşteridir.

service

İstenen sonucu elde etmek için gereken her türlü faaliyet.

arrival rate

Müşterilerin kuyruğa geliş sıklığı. Rastgele ya da düzenli olabilir.

service time

Bir müşteri isteğini tamamlamak için gereken ortalama süre.

queue time

Müşterilerin kuyrukta beklediği ortalama süre.

response time

queue time + service time — kuyruğa girişten sunucudan çıkışa kadar.

Kuyruk teorisinin işi bu örüntülerden üçünü tahmin etmektir: kuyruk süresi, ortalama kuyruk boyutu ve maksimum kuyruk boyutu. Tahminler iki faktöre dayanır — geliş hızı ve ortalama hizmet süresi. İdeal durumda müşteriler hizmet süresine uygun bir sıklıkta gelir; ama işler nadiren ideale uyar, bu yüzden bazen sunucu boşta kalır, bazen sıra birikir.

Bir kuyruk modeli kurulduktan sonra sistemde önerilen değişiklikler yapılmadan incelenebilir. "Ortalama servis süresini %15 azaltan bir otomasyon kursak kaç kişiye daha az ihtiyacımız olurdu?" ve "bir sunucu daha eklemeden bu düzen ne kadar sürdürülebilir?" birer kuyruk teorisi sorusudur.

Kategorize etme

Kategorize etme, verileri temel sırayı bozmadan yeniden düzenlemektir. Burada dikkatli olmak gerek: bu bir sıralama değildir. Sonuç sıralı bir liste değil, belirttiğin kurallara göre gruplanmış bir listedir.

Çözüm tek cümle: dört kategorinin her biri için bir kuyruk oluştur, sayıları okudukça uygun kuyruğa koy, sonunda kuyrukları sırayla yazdır. Bu bir multiple-queue uygulamasıdır.

Simülasyon

Kuyruk simülasyonu, kuyrukların performansı hakkında istatistik üretmek için kullanılan bir modelleme etkinliğidir. Ders örneği tek pencereli bir büfe.

Model

Bir pencere, bir çalışan, aynı anda tek müşteri. Günde 8 saat ⇒ 480 dakikalık model.

Zaman birimi

Aksiyonlar 1 dakikalık aralıklarla başlar ve durur.

Geliş

Ortalama 4 dakikada bir müşteri. 1–4 arası rastgele sayı: 4 ise müşteri geldi, değilse gelmedi.

Hizmet süresi

1–10 dakika arası, müşteri işleme alınırken rastgele belirlenir.

Her dakika

Sunucu meşgul mü boş mu? Boşsa sıradaki müşteri alınır; meşgulse bekleyenler kuyrukta kalır.

Dört yapı

queue head · queue node · mevcut müşteri durumu · simülasyon istatistikleri.

Simülasyonun amacı, gerçek büfeyi değiştirmeden "ne olurdu?" sorusunu cevaplamaktır. Çıktısı ortalama bekleme süresi ve maksimum kuyruk boyutu gibi istatistiklerdir — yani kuyruk teorisinin tahmin etmeye çalıştığı sayıların deneyle üretilmiş hâli.

Kendini sına

1 Q3 = createQueue
2 count = 0
3 loop (not empty Q1 and not empty Q2)
   1  count = count + 1
   2  dequeue (Q1, x)
   3  dequeue (Q2, y)
   4  if (y equal to count)
      1  enqueue (Q3, x)

-+*9+28*+4863  →  -+*9 10 *12 6 3  →  -+90 72 3  →  -162 3  →  159