--- title: 'Kuyruklar ve Çift Uçlu Kuyruklar' source: 'https://academia.sh/tr/kurslar/veri-yapilari/kuyruklar' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:57+00:00' license: 'CC BY-SA 4.0' --- # Kuyruklar ve Çift Uçlu Kuyruklar İlk giren ilk çıkar modeli, halka arabellekle sabit bellekte kuyruk, çift uçlu kuyruk ve kullanım alanları. 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. ```python 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.