Yığıtlar

Önceki üç ders somut yerleşimleri anlattı: bitişik blok, büyüyen blok, bağlı düğümler. Bu ders farklı bir soru sorar — verinin nasıl saklandığı değil, hangi işlemlere izin verildiği.

Soyut Veri Tipi

Soyut veri tipi, bir yapının sunduğu işlemleri ve bu işlemlerin anlamını tanımlar; verinin bellekte nasıl durduğunu söylemez. Programlama Temelleri kursundaki arayüz– gerçekleştirim ayrımının veri yapılarındaki karşılığıdır.

Ayrımın değeri iki yönlüdür. Kullanan taraf, yalnızca sözleşmeye dayanarak kod yazar; gerçekleştiren taraf, sözleşmeyi bozmadan iç yapıyı değiştirebilir. Aynı soyut tip, farklı maliyet profilleriyle birden çok biçimde gerçeklenebilir.

Yığıt (stack), bu dersin konusu olan soyut veri tipidir ve tek bir kuralla tanımlanır: son eklenen eleman, ilk çıkan elemandır.

Yığıt İşlemleri

Dört işlem yeterlidir:

İşlem	Anlamı	Maliyet
it (push)	Tepeye eleman ekler	$O(1)$
çek (pop)	Tepedeki elemanı çıkarır ve döndürür	$O(1)$
tepe (peek)	Tepedekini çıkarmadan gösterir	$O(1)$
boş_mu	Yığıtın boş olup olmadığını söyler	$O(1)$

Listede olmayan işlemler de tanımın parçasıdır: yığıtta ortadaki bir elemana erişilemez, arama yapılmaz, gezinme yoktur. Kısıtlama bir eksiklik değil, tasarımın kendisidir — kısıtlı arayüz, yanlış kullanımı olanaksız kılar.

İki Gerçekleştirim

Aynı sözleşme iki farklı yapıyla karşılanabilir ve ikisi de tüm işlemleri sabit zamanda yapar.

Dinamik dizi ile: Tepe, dizinin sonudur. Ekleme sona ekleme, çıkarma sondan silmedir; ikisi de kaydırma gerektirmez. Amortize maliyet sabittir ve bitişik yerleşim sayesinde önbellek davranışı iyidir.

Bağlı liste ile: Tepe, listenin başıdır. Başa ekleme ve baştan silme sabit zamanlıdır. Yeniden ayırma hiç olmaz; buna karşılık düğüm başına işaretçi ek yükü ve dağınık yerleşim vardır.

Seçim ölçütü, önceki derslerin sonucunu tekrarlar: öngörülebilir tek işlem süresi gerekmiyorsa dinamik dizi, gerekiyorsa bağlı liste.

class Yigit:
    """Son giren ilk çıkar; dinamik dizi üzerine kurulu."""

    def __init__(self) -> None:
        self._veri: list = []

    def it(self, deger) -> None:
        self._veri.append(deger)

    def cek(self):
        if self.bos_mu():
            raise IndexError("boş yığıttan çekilemez")
        return self._veri.pop()

    def tepe(self):
        if self.bos_mu():
            raise IndexError("boş yığıtın tepesi yok")
        return self._veri[-1]

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

    def __len__(self) -> int:
        return len(self._veri)


y = Yigit()
for olcum in (12, 18, 7):
    y.it(olcum)

print(y.tepe(), len(y))      # 7 3
print(y.cek(), y.cek())      # 7 18
print(len(y), y.bos_mu())    # 1 False

Boş yığıttan çekmenin hata üretmesi, sözleşmenin parçasıdır. Sessizce boş değer döndürmek, Programlama Temelleri kursundaki boş değer sorununu çağıran tarafa taşırdı.

Neden Yığıt

Yığıt, “en son yarım kalan işe geri dön” biçiminde tanımlanabilen her problemin doğal yapısıdır.

Çağrı yığıtı. Bilgisayarlar Nasıl Çalışır kursunda kurulan çerçeve düzeni tam olarak budur: en son çağrılan fonksiyon en önce döner. Özyineleme derinliği, bu yığıtın doluluğuydu.

Geri alma. Bir düzenleyicide yapılan işlemler yığıta itilir; geri alma, tepedeki işlemi çeker.

Eşleşme denetimi. Açılan her parantez yığıta itilir, kapanan her parantez tepedekiyle karşılaştırılır.

Geri izleme. Denenmiş seçimlerin yığıtta tutulması, çıkmaza girildiğinde son karara dönmeyi sağlar.

Derine arama. Bu kursun son konusunda görüleceği gibi, çizgelerde derine arama bir yığıtla yürür — özyinelemeli yazımında bu yığıt, çağrı yığıtının kendisidir.

Örnek: Parantez Denetimi

Bir metindeki parantezlerin doğru eşleşip eşleşmediği, tek geçişte ve yığıtla sınanır:

ESLESME = {")": "(", "]": "[", "}": "{"}

def dengeli_mi(metin: str) -> bool:
    """Parantezlerin doğru sırayla açılıp kapandığını sınar."""
    yigit = Yigit()
    for karakter in metin:
        if karakter in "([{":
            yigit.it(karakter)
        elif karakter in ESLESME:
            if yigit.bos_mu() or yigit.cek() != ESLESME[karakter]:
                return False               # eşleşmeyen kapanış
    return yigit.bos_mu()                  # açık kalan varsa dengesiz


print(dengeli_mi("(12 + [18 - 7])"))       # True
print(dengeli_mi("(12 + [18 - 7)]"))       # False   — sıra bozuk
print(dengeli_mi("((12)"))                 # False   — açık kaldı
print(dengeli_mi("12)"))                   # False   — fazladan kapanış

Çözümün yığıt gerektirmesinin nedeni, iç içe geçmenin derinliğinin önceden bilinmemesidir: en son açılan parantez, ilk kapanması gerekendir. Aynı yapı, iç içe geçen her şey için geçerlidir — kod blokları, işaretleme etiketleri, ifade ayrıştırma.

Bu, önceki kursta anlatılan ayrıştırma aşamasının çekirdeğidir; dilbilgisi kurallarının iç içe geçmiş yapıları, bir yığıt üzerinde işlenir.

Örnek: İfade Değerlendirme

İkinci klasik kullanım, aritmetik ifadelerin değerlendirilmesidir. İşleçlerin işlenenlerden sonra yazıldığı son ek gösteriminde parantez gerekmez ve değerlendirme tek bir yığıtla yürür: sayı görülünce itilir, işleç görülünce iki değer çekilip sonuç geri itilir.

def son_ek_degerlendir(ifade: str) -> float:
    """Son ek gösterimindeki ifadeyi yığıtla hesaplar."""
    yigit = Yigit()
    for birim in ifade.split():
        if birim in "+-*/":
            sag = yigit.cek()
            sol = yigit.cek()
            if birim == "+": yigit.it(sol + sag)
            elif birim == "-": yigit.it(sol - sag)
            elif birim == "*": yigit.it(sol * sag)
            else: yigit.it(sol / sag)
        else:
            yigit.it(float(birim))
    return yigit.cek()


print(son_ek_degerlendir("12 18 +"))          # 30.0
print(son_ek_degerlendir("12 18 + 2 /"))      # 15.0   — (12 + 18) / 2
print(son_ek_degerlendir("12 18 7 - +"))      # 23.0   — 12 + (18 - 7)

İkinci çağrı, bu kurs boyunca kullanılan ortalama hesabının son ek gösterimidir. Çekme sırasının önemine dikkat edin: ilk çekilen değer sağ işlenendir, çünkü en son itilen odur. Çıkarma ve bölmede bu sıra karıştırılırsa sonuç sessizce yanlış çıkar.

Ara gösterimdeki (alışıldık) bir ifadeyi son ek gösterimine çevirmek de bir yığıt gerektirir; işleç önceliği, yığıtta bekleyen işleçlerin ne zaman çıkarılacağını belirler. Derleyicilerin ifade ayrıştırma aşaması bu düzenin genelleştirilmiş hâlidir.

Sınırlar

Yığıtın kısıtlı arayüzü, bazı soruların yanıtlanamamasını beraberinde getirir: kaç elemanın hangi değerde olduğu, ortadaki bir elemanın ne olduğu, elemanların sıralı olup olmadığı. Bu bilgiler gerekiyorsa yığıt yanlış seçimdir.

Sabit kapasiteli bir gerçekleştirimde ikinci bir sınır vardır: kapasite dolduğunda taşma oluşur. Bilgisayarlar Nasıl Çalışır kursundaki yığıt taşması, bu durumun çağrı yığıtındaki karşılığıydı.

Maliyet Tablosu

Yapı	Erişim	Arama	Ekleme	Silme
Dinamik dizi	$O(1)$	$O(n)$	sona $O(1)$ amortize	ortadan $O(n)$
Bağlı liste	$O(n)$	$O(n)$	başa $O(1)$	düğüm elde $O(1)$
Yığıt	yalnız tepe $O(1)$	—	$O(1)$	$O(1)$

Özet

• Soyut veri tipi, sunulan işlemleri ve anlamlarını tanımlar; yerleşimi belirtmez.
• Yığıt, son giren ilk çıkar kuralıyla tanımlanır ve dört işlemi sabit zamanlıdır.
• Kısıtlı arayüz bir eksiklik değil, yanlış kullanımı önleyen bir tasarım kararıdır.
• Dinamik dizi ve bağlı liste, yığıtı aynı maliyetlerle gerçekler; seçim, tek işlem süresi ve önbellek davranışına göre yapılır.
• Çağrı yönetimi, geri alma, eşleşme denetimi ve geri izleme yığıtla çözülen problem ailesidir.
• Boş yığıttan çekme hata üretir; sabit kapasiteli gerçekleştirimde taşma ikinci sınırdır.

Sonraki Adım

Bazı problemlerde beklenen davranış tersidir: ilk gelen ilk işlenmelidir — bir iş kuyruğunda, bir yazıcı sırasında, bir ağ tamponunda. Sonraki ders bu modeli ve sabit bellekle sürekli akış işlemeyi sağlayan halka arabelleği ele alacak.