Kuyruklar ve Çift Uçlu Kuyruklar

Yığıt, en son eklenene öncelik verir. Bazı problemlerde beklenen tam tersidir: bir iş kuyruğunda önce gelen önce işlenmeli, bir ağ tamponunda paketler geliş sırasını korumalıdır.

Kuyruk (queue), bu kuralı tanımlayan soyut veri tipidir: ilk giren, ilk çıkar.

Kuyruk İşlemleri

İşlem	Anlamı	Hedef maliyet
ekle (enqueue)	Sona eleman ekler	$O(1)$
al (dequeue)	Baştaki elemanı çıkarır ve döndürür	$O(1)$
ön (front)	Baştakini çıkarmadan gösterir	$O(1)$
boş_mu	Kuyruğun boş olup olmadığını söyler	$O(1)$

Yığıttan tek farkı, çıkarmanın hangi uçtan yapıldığıdır. Bu küçük fark, gerçekleştirimi belirgin biçimde zorlaştırır: yığıtta her iki işlem de aynı uçta olduğu için tek bir dizin yeterliyken, kuyrukta iki ucun ayrı ayrı izlenmesi gerekir.

Saf Dizi Gerçekleştiriminin Sorunu

Kuyruk bir dinamik diziyle kurulursa, sona ekleme ucuzdur ancak baştan almak tüm elemanların bir sıra sola kaydırılmasını gerektirir — $O(n)$. Bin elemanlık bir kuyrukta her al çağrısı bin kaydırma yapar.

Kaydırmadan kaçınmanın ilk fikri, baş dizinini ilerletmektir: eleman silinmez, yalnızca “artık kuyrukta değil” sayılır. Bu, al işlemini sabit zamanlı yapar ama yeni bir sorun üretir — dizinin başındaki alan boşalır ve hiç geri kazanılmaz. Sürekli çalışan bir kuyruk, kullanılmayan alanı sonsuza kadar büyütür.

Halka Arabellek

Çözüm, dizinin sonuna varıldığında başa dönmektir. Sabit kapasiteli bir bloğun uçları birbirine bağlanmış gibi düşünülür; bu yapıya halka arabellek (circular buffer) denir.

İki dizin tutulur: bas, sıradaki alınacak elemanı; son, sıradaki yazılacak yeri gösterir. İlerleme, kapasiteye göre kalan alınarak yapılır:

$$\text{yeni konum} = (\text{konum} + 1) \bmod \text{kapasite}$$

Kalan işleci, İşleçler dersinde tanıtılmıştı; buradaki kullanımı onun kanonik örneğidir.

class HalkaArabellek:
    """Sabit kapasiteli kuyruk; uçlara ulaşınca başa döner."""

    def __init__(self, kapasite: int) -> None:
        self._veri: list = [None] * kapasite
        self._kapasite = kapasite
        self._bas = 0
        self._sayi = 0

    def __len__(self) -> int:
        return self._sayi

    def dolu_mu(self) -> bool:
        return self._sayi == self._kapasite

    def bos_mu(self) -> bool:
        return self._sayi == 0

    def ekle(self, deger) -> None:
        if self.dolu_mu():
            raise OverflowError("arabellek dolu")
        son = (self._bas + self._sayi) % self._kapasite    # yazılacak konum
        self._veri[son] = deger
        self._sayi += 1

    def al(self):
        if self.bos_mu():
            raise IndexError("boş arabellekten alınamaz")
        deger = self._veri[self._bas]
        self._veri[self._bas] = None                       # referansı bırak
        self._bas = (self._bas + 1) % self._kapasite       # başa dön
        self._sayi -= 1
        return deger


kuyruk = HalkaArabellek(3)
kuyruk.ekle(12); kuyruk.ekle(18); kuyruk.ekle(7)
print(len(kuyruk), kuyruk.dolu_mu())        # 3 True

print(kuyruk.al(), kuyruk.al())             # 12 18
kuyruk.ekle(25); kuyruk.ekle(14)            # boşalan yerlere başa dönerek yazılır
print(len(kuyruk))                          # 3
print(kuyruk.al(), kuyruk.al(), kuyruk.al())   # 7 25 14

Kapasitesi üç olan arabellek, beş eleman taşımıştır: yeni elemanlar, boşalan konumlara başa dönülerek yazılmıştır. Hiçbir eleman kaydırılmamış, hiç yeniden ayırma yapılmamıştır.

Dolu arabellekte ekleme kararı bir tasarım seçimidir. Üç seçenek yaygındır: hata üretmek (yukarıdaki gibi), çağıranı bekletmek, ya da en eski elemanın üzerine yazmak. Üçüncüsü, yalnızca son $k$ ölçümün tutulduğu kayıt tamponlarında tercih edilir.

Bağlı Liste ile Kuyruk

Kapasite sınırı istenmiyorsa, baş ve son işaretçilerinin ikisini birden tutan bir bağlı liste kullanılır: sona ekleme son işaretçisiyle, baştan alma baş işaretçisiyle sabit zamanda yapılır.

Bedeli önceki derste tanımlanmıştı: düğüm başına işaretçi ek yükü ve dağınık yerleşim. Pratikte yaygın çözüm ikisinin birleşimidir — bağlı listenin düğümleri tek eleman değil, küçük bitişik bloklar taşır. Böylece hem sınırsız büyüme hem makul önbellek davranışı elde edilir.

Çift Uçlu Kuyruk

Çift uçlu kuyruk (deque), her iki uçtan ekleme ve çıkarmaya izin verir. Yığıt ve kuyruğun ikisini birden kapsar: yalnızca bir uç kullanılırsa yığıt, iki uç ayrı ayrı kullanılırsa kuyruk gibi davranır.

Halka arabellek, çift uçlu kuyruğu da doğal olarak destekler; baş dizini geriye doğru da döndürülebilir.

Tipik kullanımı, kayan pencere problemleridir: bir uçtan yeni ölçüm girer, diğer uçtan pencere dışında kalan çıkar. Programlama Temelleri kursunda tanıtılan kayan pencere kalıbının veri yapısı karşılığı budur.

Kullanım Alanları

• İş kuyrukları. Üretici–tüketici düzeninde işler sıraya alınır; sıra korunur.
• Tamponlama. Farklı hızda çalışan iki bileşen arasında halka arabellek kullanılır; Bilgisayarlar Nasıl Çalışır kursundaki aygıt iletişimi bu düzendedir.
• Enine arama. Bu kursun son konusunda görüleceği gibi, çizgelerde katman katman gezinme bir kuyrukla yürür.
• Zamanlama. İşletim sisteminin hazır süreç listesi, adil paylaşımda kuyruk düzenindedir.

Elemanların geliş sırasının değil önem sırasının belirleyici olduğu durumlarda, kuyruk yetmez; öncelik kuyruğu gerekir. O yapı, ağaçlar konusundaki yığın dersinde ele alınacaktır.

Kuyruk Uzunluğu Bir Ölçüttür

Bir kuyruk yalnızca veri yapısı değil, iki bileşen arasındaki hız farkının göstergesidir. Kuyruk uzunluğu sürekli artıyorsa, üretim hızı tüketim hızını aşıyor demektir.

Sınırsız kapasiteli bir kuyrukta bu durum uzun süre gizli kalır: bellek dolana kadar hiçbir belirti görünmez, sonra sistem birden çöker. Sınırlı kapasiteli kuyrukta ise sınıra ulaşıldığında karar vermek zorunludur — üreticiyi bekletmek, yeni işi reddetmek veya en eskisini düşürmek.

Üreticinin bekletilmesi, yavaşlığın kaynağa doğru yayılmasıdır ve geri basınç olarak adlandırılır. Bilgisayarlar Nasıl Çalışır kursunda aygıtlar arası iletişimde geçen bu kavram, dağıtık sistemlerde de aynı biçimde işler.

Bu nedenle üretim ortamında kuyruk uzunluğu izlenen bir ölçüttür: uzunluğun eğilimi, darboğazın nerede olduğunu doğrudan gösterir.

Maliyet Tablosu

Yapı	Baştan alma	Sona ekleme	Başa ekleme	Kapasite
Dinamik dizi (saf kuyruk)	$O(n)$	$O(1)$ amortize	$O(n)$	Sınırsız
Halka arabellek	$O(1)$	$O(1)$	$O(1)$	Sabit
Bağlı liste (baş + son)	$O(1)$	$O(1)$	$O(1)$	Sınırsız
Çift uçlu kuyruk	$O(1)$	$O(1)$	$O(1)$	Değişir

Özet

• Kuyruk, ilk giren ilk çıkar kuralıyla tanımlanır; yığıttan tek farkı çıkarmanın yapıldığı uçtur.
• Dizi üzerinde saf gerçekleştirimde baştan alma kaydırma gerektirir; baş dizinini ilerletmek ise kullanılmayan alan biriktirir.
• Halka arabellek, kalan işleciyle uçları birleştirir ve sabit kapasiteyle her iki işlemi sabit zamanlı yapar.
• Dolu arabellekte davranış — hata, bekleme veya üzerine yazma — bir tasarım kararıdır.
• Baş ve son işaretçili bağlı liste, sınırsız kapasiteli kuyruk verir; bedeli işaretçi ek yükü ve yerelliktir.
• Çift uçlu kuyruk her iki uca izin verir ve kayan pencere problemlerinin doğal yapısıdır.

Sonraki Adım

Buraya kadar sıralı erişim ve uçlardan işlem ele alındı. Sıralı bir veri kümesinde arama ise hâlâ doğrusal: bağlı listede ikili arama yapılamıyor, çünkü ortadaki elemana sıçranamıyor. Sonraki ders, bağlantılı yapıya katmanlar ekleyerek bu sıçramayı mümkün kılan olasılıksal bir çözümü ele alacak.