Veri Yapıları ve Programlama

9 - Yığın (Stack) Veri Yapısı

Emre Can Yılmaz

[email protected]

Ondokuz Mayıs Üniversitesi

2025

Sunum Genel Bakış

• Öğrenme Hedefleri
  • Yığın (Stack) kavramını tanımlama
  • Yığın veri yapısını dizi ve bağlı liste kullanarak implementasyon yöntemlerini anlama
  • Push, Pop, Peek gibi temel yığın işlemlerini öğrenme
  • Gerçek hayatta yığın kullanım örneklerine hâkim olma

Yığın (Stack) Nedir?

• Tanım: Yığın, Son Giren İlk Çıkar (LIFO - Last-In-First-Out) ilkesini izleyen doğrusal bir veri yapısıdır.
• Bu ilkeye göre yığına eklenen son eleman, çıkarılacak ilk eleman olur.

Günlük Hayattan Analoji

Bir tabak yığını düşünün:

• Yeni tabağı en üste koyarsınız (push).
• Üstteki tabağı alırsınız (pop).
• Alttaki tabağa ulaşmak için üstteki tabakları kaldırmanız gerekir.

Yığındaki Temel İşlemler

1. Push: Yığının üstüne yeni bir eleman eklemek
2. Pop: Yığının üstündeki elemanı çıkarmak
3. Peek: Üstteki elemanı çıkarmadan okumak
4. IsEmpty: Yığının boş olup olmadığını sorgulamak
5. IsFull: Yığının dolu olup olmadığını sorgulamak (çoğu zaman implementasyona bağlı)

LIFO Görselleştirme

• 3 numaralı eleman en son eklendiği halde (push), ilk o çıkarılır (pop).
• Bu, yığınların temel ilkesi olan LIFO (Son Giren İlk Çıkar) mantığıdır.

Yığın Uygulamaları

• Fonksiyon Çağrı Yığınları (Call Stack)
• Geri Alma (Undo) Mekanizmaları
• Tarayıcı Geçmişi
• Parantez Eşleştirme
• Derinlik Öncelikli Arama (DFS)

Yığına dair bu örnekler, yığının yaygın kullanım alanlarının ne kadar geniş olduğunu gösterir.

Bağlı Liste ile Yığın Implementasyonu: Genel Yaklaşım

• Tepe (top) İşaretçisi: Yığının en üst elemanını takip eder.
• Yığın boşken tepe işaretçisi NULL gösterir.
• Push/pop operasyonlarında tepe işaretçisi güncellenir.

Push İşlemi: Adımlar

1. Yeni düğüm için bellek ayır (malloc).
2. Yeni düğümün onceki işaretçisini eski tepeye bağla.
3. tepe işaretçisini yeni düğüme güncelle.

void push(int sayi) {
    Node yeniDugum = (Node)malloc(sizeof(struct stackNode));
    if (yeniDugum == NULL) {
        printf("Hata: Bellek ayrılamadı! (push)\n");
        return;
    }
    yeniDugum->veri = sayi;
    yeniDugum->onceki = tepe;
    tepe = yeniDugum;
    printf("%d yığına eklendi (push).\n", sayi);
}

Pop İşlemi: Adımlar

1. Yığın boş mu kontrol et (tepe == NULL).
2. Yığının tepesindeki düğümü geçici işaretçiyle tut.
3. Tepe elemanının verisini al.
4. tepe işaretçisini bir önceki düğüme kaydır.
5. Belleği serbest bırak (free).

int pop() {
    if (tepe == NULL) {
        printf("Hata: Yığın boş! (pop)\n");
        return INT_MIN;
    }
    Node temp = tepe;
    int cikarilanVeri = temp->veri;
    tepe = tepe->onceki;
    free(temp);
    printf("%d yığından çıkarıldı (pop).\n", cikarilanVeri);
    return cikarilanVeri;
}

Peek İşlemi

int peek() {
    if (tepe == NULL) {
        printf("Hata: Yığın boş! (peek)\n");
        return INT_MIN;
    }
    printf("Yığının tepesindeki eleman (peek): %d\n", tepe->veri);
    return tepe->veri;
}

• Yığının üstündeki elemanı görüntülemeden almak (pop etmeksizin) için kullanılır.

Kontrol İşlevleri: isEmpty ve isFull

int isEmpty() {
    return (tepe == NULL);
}

int isFull() {
    // Bağlı liste yığında gerçek sınır fiziksel bellekle sınırlıdır.
    return 0;
}

Örnek Kullanım (main)

int main() {
    printf("--- Yığın İşlemleri Başlangıç ---\n");
    printf("Başlangıçta yığın boş mu? %s\n", isEmpty() ? "Evet" : "Hayır");

    push(10);
    push(20);
    push(30);

    peek(); // 30
    pop();  // 30 çıkarılır
    peek(); // 20

    pop();  // 20
    push(40);

    peek(); // 40
    pop();  // 40
    pop();  // 10

    printf("Yığın boş mu? %s\n", isEmpty() ? "Evet" : "Hayır");

    pop();  // Hata (yığın boş)
    peek(); // Hata (yığın boş)

    return 0;
}

Kodun tam hali: https://gist.github.com/ecylmz/87c4ca535e0c832165c91d26f1c7dd1a

Dizi (Array) ile Yığın İmplementasyonu Neler Değişir?

1. Bir dizi (array) kullanılır ve bir top indisi yığının konumunu işaretler.
2. Dizi dolduğunda push işlemi başarısız olabilir (isFull kontrolü).
3. Yine pop, peek, isEmpty gibi işlemler benzer mantıkla çalışır ancak top indisiyle yönetilir.

Alıştırmalar

1. Dizi Tabanlı Yığın Yazımı: push, pop, peek, isEmpty, isFull fonksiyonlarını dizi kullanarak tasarlayın.
2. Metin Tersine Çevirme: Yığın kullanarak bir metni (string) tersine çeviren C fonksiyonu yazın.
3. Parantez Eşleştirme: Yığın kullanarak bir ifadedeki (, {, [ parantezlerinin doğru açılıp kapanıp kapanmadığını kontrol eden algoritmayı tasarlayın.

Teşekkürler ve Soru-Cevap

• Her türlü soru veya geri bildirimi paylaşabilirsiniz.
• Bu sunumda yığının (stack) ne olduğu, nasıl çalıştığı ve temel uygulamaları ele alındı.
• Uygulamaları deneyerek ve çeşitli örnekleri inceleyerek yığın konusundaki uzmanlığınızı artırabilirsiniz.