Kuyruk Veri Yapısı ile Yığın Arasındaki Farklar Nelerdir

Yığın ve Kuyruk Veri Yapılarına Giriş

Veri yapıları, bir programın verileri nasıl sakladığını ve bu verilere nasıl erişildiğini belirleyen temel yapı taşlarıdır. Doğru veri yapısını seçmek, kodun hem performansını hem de okunabilirliğini doğrudan etkiler. Bu yapılar arasında yığın (stack) ve kuyruk (queue), en sık karşılaşılan ve en çok karıştırılan iki kavramdır.

Her ikisi de veriyi sıralı bir şekilde tutar, her ikisinde de veri ekleme ve çıkarma işlemleri belirli kurallara bağlıdır, ve her ikisi de basit arayüzlere sahiptir. Ancak aralarındaki temel fark, verinin hangi sırayla dışarı çıkacağıdır. Bu makalede her iki yapının çalışma mantığını, bellek kullanımını, pratik kullanım alanlarını ve basit kod örneklerini ele alacağız.

Yığın (Stack) Veri Yapısı: LIFO Prensibi

Yığın, "Last In First Out" (LIFO) prensibiyle çalışır. Yani en son eklenen eleman, en önce çıkarılır. Bunu bir tabağın üzerine istiflenen tabaklara benzetebilirsiniz: en üste koyduğunuz tabağı, en önce o tabağı alırsınız.

Yığında iki temel operasyon vardır:

• Push: Yığının en üstüne yeni bir eleman ekler.
• Pop: Yığının en üstündeki elemanı çıkarır ve döndürür.

Bunlara ek olarak genellikle bir de Peek (veya Top) operasyonu bulunur; bu işlem en üstteki elemanı çıkarmadan sadece görüntülemeyi sağlar.

Yığın, bellekte genellikle bir dizi (array) veya bağlı liste (linked list) ile gerçekleştirilir. Dizi tabanlı implementasyonlarda eleman ekleme ve çıkarma işlemi dizinin sonunda yapılır, böylece kaydırma işlemine gerek kalmaz. Bu sayede Push ve Pop operasyonları O(1) zaman karmaşıklığına sahiptir.

Kuyruk (Queue) Veri Yapısı: FIFO Prensibi

Kuyruk ise "First In First Out" (FIFO) prensibiyle çalışır. Yani ilk eklenen eleman, ilk çıkarılır. Bu, bir markette kasa sırasına benzer: sıraya ilk giren kişi, ilk hizmet alır.

Kuyrukta temel operasyonlar şunlardır:

• Enqueue: Kuyruğun sonuna (tail) yeni bir eleman ekler.
• Dequeue: Kuyruğun başındaki (head) elemanı çıkarır ve döndürür.

Kuyruk da dizi veya bağlı liste ile gerçekleştirilebilir, ancak basit bir dizi kullanıldığında dequeue işlemi sonrası kalan elemanları kaydırmak gerekebilir, bu da O(n) karmaşıklığa yol açar. Bu nedenle verimli kuyruk implementasyonlarında genellikle dairesel dizi (circular buffer) veya bağlı liste tercih edilir; bu yöntemlerle hem enqueue hem dequeue işlemleri O(1) sürede gerçekleştirilebilir.

Temel Farklar: Yığın vs Kuyruk

Özellik	Yığın (Stack)	Kuyruk (Queue)
Çalışma prensibi	LIFO	FIFO
Ekleme işlemi	Push	Enqueue
Çıkarma işlemi	Pop	Dequeue
Erişim noktası	Tek uç (top)	İki uç (head ve tail)
Tipik kullanım	Geri izleme, çağrı yönetimi	Sıralı işleme, görev planlama

En önemli yapısal fark, yığının tek bir uçtan (üst/top) hem ekleme hem çıkarma yaparken, kuyruğun iki farklı uçtan (baş/head ve son/tail) çalışmasıdır. Bu durum, kuyruk implementasyonlarının yığına göre biraz daha fazla dikkat gerektirmesine neden olur; özellikle dizi tabanlı kuyruklarda başlangıç ve bitiş indekslerinin doğru yönetilmesi gerekir.

Yığının Pratik Uygulamaları

Yığın yapısı, "son yapılanı önce geri al" mantığının gerektiği her yerde karşımıza çıkar:

• Fonksiyon çağrı yönetimi (Call Stack): Bir program fonksiyon çağırdığında, çağrının dönüş adresi ve yerel değişkenleri bir çağrı yığınına (call stack) itilir. Fonksiyon bittiğinde bu bilgi yığından çıkarılır (pop edilir). İç içe fonksiyon çağrıları bu nedenle doğal olarak yığın mantığıyla yönetilir.
• Geri alma (Undo) işlevleri: Metin editörlerindeki veya tasarım araçlarındaki "geri al" özelliği, kullanıcının yaptığı her işlemi bir yığına ekler. Geri al komutu verildiğinde, en son yapılan işlem yığından çıkarılarak geri alınır.
• İfade değerlendirme ve parantez eşleştirme: Derleyiciler ve yorumlayıcılar, matematiksel ifadelerdeki parantezlerin doğru eşleşip eşleşmediğini kontrol ederken yığın kullanır. Açılan her parantez yığına itilir, kapanan parantez geldiğinde yığından bir eleman çıkarılır.
• Derinlik öncelikli arama (DFS): Graf ve ağaç yapılarında DFS algoritması, ziyaret edilecek düğümleri bir yığında tutarak (veya özyineleme yoluyla dolaylı olarak yığın kullanarak) en derin dala önce iner.

Kuyruğun Pratik Uygulamaları

Kuyruk yapısı ise "ilk gelen ilk işlenir" mantığının gerektiği senaryolarda tercih edilir:

• Görev yönetimi ve işlem planlama: İşletim sistemlerinde işlemci zamanlayıcıları, bekleyen görevleri genellikle kuyruk mantığıyla sıraya koyar ve işler.
• Mesaj kuyruğu sistemleri: Dağıtık sistemlerde servisler arası iletişimde mesajlar bir kuyrukta birikir ve gönderildikleri sırayla işlenir. Bu yaklaşım, sistemler arasında gevşek bağlılık (loose coupling) sağlar.
• Genişlik öncelikli arama (BFS): Graf algoritmalarında BFS, bir düğümün tüm komşularını önce ziyaret edip sonra bir alt seviyeye inerken kuyruk kullanır. Bu, en kısa yol problemlerinde sıkça tercih edilen bir yaklaşımdır.
• Yazıcı sıraları ve isteklerin işlenme sırası: Bir yazıcıya gönderilen belgeler, gönderilme sırasına göre işlenir; bu da doğal bir kuyruk senaryosudur.

Kod Örnekleri: Yığın Uygulaması

Aşağıda basit bir yığın implementasyonu, dizi tabanlı yaklaşımla gösterilmiştir:

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Yığın boş, pop işlemi yapılamaz")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Yığın boş, peek işlemi yapılamaz")
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

Burada pop ve peek işlemlerinde boş yığın kontrolü yapılması önemlidir; aksi halde çalışma zamanı hatası alınır. Python listelerinde append ve pop işlemleri listenin sonunda çalıştığı için bu implementasyon O(1) zaman karmaşıklığına sahiptir.

Kod Örnekleri: Kuyruk Uygulaması

Kuyruk implementasyonunda dizi sonundan kaydırma maliyetini önlemek için collections.deque gibi çift uçlu kuyruk yapıları tercih edilir:

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Kuyruk boş, dequeue işlemi yapılamaz")
        return self._items.popleft()

    def peek(self):
        if self.is_empty():
            raise IndexError("Kuyruk boş, peek işlemi yapılamaz")
        return self._items[0]

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

deque yapısı hem baştan hem sondan O(1) sürede ekleme/çıkarma yapılmasına izin verdiği için, normal bir Python listesine göre kuyruk implementasyonunda çok daha verimlidir. Normal bir listeyle pop(0) kullanmak, kalan tüm elemanların kaydırılmasını gerektirdiğinden O(n) maliyetlidir.

Hangisini Ne Zaman Kullanmalı?

Bir problemi çözerken hangi veri yapısını seçeceğinizi belirlemek için kendinize şu soruyu sorabilirsiniz: "Verinin işlenme sırası, ekleniş sırasıyla aynı mı, yoksa tersi mi olmalı?"

• Eğer en son eklenen veriye önce erişmeniz gerekiyorsa (geri alma, parantez kontrolü, özyinelemeli algoritmaların iteratif karşılıkları) → Yığın kullanın.
• Eğer veriler geldiği sırayla işlenmesi gerekiyorsa (görev kuyruğu, mesajlaşma sistemleri, sıraya giren istekler) → Kuyruk kullanın.

Basit bir karar kriteri olarak: adil ve sıralı işleme gerekiyorsa kuyruk, en güncel duruma hızlı geri dönüş gerekiyorsa yığın tercih edilmelidir.

Performans Karşılaştırması

Doğru implementasyon seçildiğinde hem yığın hem kuyruk temel operasyonlarında O(1) zaman karmaşıklığı sunar. Ancak bu performansın gerçek dünyada elde edilmesi, seçilen alt yapıya bağlıdır:

• Dizi tabanlı yığınlarda ekleme/çıkarma dizinin sonunda yapıldığı için ek maliyet oluşmaz.
• Dizi tabanlı kuyruklarda eğer baştan eleman çıkarılırken kaydırma yapılıyorsa, bu O(n) maliyete yol açar. Bu nedenle dairesel tampon veya bağlı liste tabanlı implementasyonlar tercih edilmelidir.
• Bellek kullanımı açısından, bağlı liste tabanlı implementasyonlar her eleman için ekstra işaretçi (pointer) alanı gerektirirken, dizi tabanlı implementasyonlar genellikle daha az bellek overhead'i sunar, ancak önceden boyut ayarlaması gerekebilir.

Performans farkları, küçük veri setlerinde gözle görülür olmayabilir; ancak yüksek frekanslı işlem gerektiren sistemlerde (örneğin mesaj kuyruğu sistemleri veya gerçek zamanlı görev planlayıcılar) doğru implementasyon seçimi kritik önem taşır.

Sık Sorular ve Hata Ayıklama

Stack overflow nedir? Yığına sınırsız şekilde eleman eklenmeye devam edilirse (örneğin sonsuz özyinelemeli bir fonksiyon çağrısında), yığının ayrılmış bellek alanı dolar ve program "stack overflow" hatası verir. Bu, özyinelemeli algoritmalar yazarken dikkat edilmesi gereken yaygın bir sorundur; taban durumu (base case) doğru tanımlanmazsa bu hatayla karşılaşılır.

Dequeue sırasında null pointer hataları neden olur? Boş bir kuyruktan eleman çıkarmaya çalışmak, implementasyona bağlı olarak null referans hatasına veya özel bir istisnaya yol açabilir. Bu nedenle dequeue ve pop işlemlerinden önce her zaman is_empty kontrolü yapılmalıdır; yukarıdaki kod örneklerinde bu kontrol açıkça gösterilmiştir.

Thread-safe implementasyonlar gerekli mi? Çok iş parçacıklı (multi-threaded) uygulamalarda birden fazla iş parçacığı aynı yığın veya kuyruğa aynı anda erişebilir. Bu durumda veri bozulmasını önlemek için kilitleme (locking) mekanizmaları veya dilin sunduğu thread-safe koleksiyon sınıfları kullanılmalıdır. Örneğin Python'da queue.Queue sınıfı, iş parçacıkları arası güvenli veri aktarımı için tasarlanmıştır.

Yaygın hata senaryoları: Boş yapı üzerinde işlem yapmaya çalışmak, kapasite sınırını aşmak (sabit boyutlu dizilerde) ve dairesel kuyruklarda baş/son indekslerinin yanlış hesaplanması, geliştiricilerin en sık karşılaştığı hatalardandır.

Özet ve İleri Konular

Yığın ve kuyruk, görünüşte benzer ama çalışma mantığı açısından tamamen farklı iki temel veri yapısıdır. Yığın LIFO prensibiyle çalışarak en son eklenen veriye öncelik tanırken, kuyruk FIFO prensibiyle en önce eklenen veriye öncelik tanır. Her ikisi de doğru implementasyonla O(1) zaman karmaşıklığında temel operasyonlar sunar, ancak kuyruk implementasyonunda dizinin baştan kaydırılması gibi performans tuzaklarına dikkat edilmelidir.

Bu iki temel yapıyı öğrendikten sonra, her iki uçtan da ekleme ve çıkarma işlemine izin veren çift uçlu kuyruk (deque – double-ended queue) kavramını incelemek faydalı olacaktır. Deque, hem yığın hem kuyruk davranışını tek bir yapıda birleştirerek daha esnek çözümler sunar ve birçok modern dilin standart kütüphanesinde hazır olarak bulunur. Bunun yanında öncelik kuyruğu (priority queue) gibi, elemanların eklenme sırasından bağımsız olarak önceliklerine göre işlendiği gelişmiş yapılar da, algoritma tasarımında sıkça karşılaşacağınız konular arasındadır.