Veri Yapıları ve Programlama

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

Emre Can Yılmaz

[email protected]

Ondokuz Mayıs Üniversitesi

2026

Günlük Hayattan Analoji

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

Yeni tabağı en üste koyarsınız.
Üstteki tabağı alırsınız.
Alttaki tabağa doğrudan ulaşamazsınız.

Bu davranış, yığının temel mantığını sezgisel olarak gösterir.

Yığın (Stack) Nedir?

Yığın, Son Giren İlk Çıkar ilkesine göre çalışan doğrusal bir veri yapısıdır.
İngilizce karşılığı LIFOdur: Last In, First Out.
Yığına ekleme ve çıkarma işlemleri aynı uçtan yapılır.
Bu uç, yığının tepesi olarak düşünülür.

Yığındaki Temel İşlemler

Push: Tepeye yeni eleman ekler.
Pop: Tepedeki elemanı çıkarır.
Peek: Tepedeki elemanı çıkarmadan okur.
isEmpty: Yığın boş mu diye bakar.
isFull: Yığın dolu mu diye bakar.

İşlem Akışını İzleyelim

İşlem	Yığının Durumu (üstten alta)
Başlangıç	boş
`push(10)`	10
`push(20)`	20, 10
`push(30)`	30, 20, 10
`pop()`	20, 10
`push(40)`	40, 20, 10

Burada son eklenen elemanın ilk çıkarıldığını doğrudan görüyoruz.

Yığın Nerelerde Kullanılır?

Fonksiyon çağrıları: En son çağrılan fonksiyon önce tamamlanır.
Geri alma işlemleri: En son yapılan işlem önce geri alınır.
Tarayıcı geçmişi: Son gidilen sayfadan geri dönülür.
Parantez denetimi: Son açılan parantez önce kapanmalıdır.
Derinlik öncelikli arama (DFS): Geri dönüş mantığında yığın yaklaşımı görülür.

Bağlı Liste ile Yığın: Düğüm Yapısı

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct stackNode {
    int veri;
    struct stackNode* onceki;
};

typedef struct stackNode* Node;

Node tepe = NULL;

Her düğüm bir veri ve bir bağlantı tutar.
tepe, yığının en üst düğümünü gösterir.
Yığın boşsa tepe == NULL olur.

Push İşleminin Mantığı

Yeni bir düğüm oluşturulur.
Yeni düğümün onceki alanı eski tepeyi gösterir.
tepe, yeni düğüme güncellenir.

Yeni eleman her zaman en üste gelir.

Push Kodu

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 İşleminin Mantığı

Önce yığın boş mu diye bakılır.
Tepedeki düğüm geçici bir işaretçide tutulur.
Veri alınır.
tepe, bir önceki düğüme kaydırılır.
Eski düğümün belleği serbest bırakılır.

Pop Kodu

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 ve isEmpty

int peek() {
    if (tepe == NULL) {
        printf("Hata: Yığın boş! (peek)\n");
        return INT_MIN;
    }

    return tepe->veri;
}

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

peek, tepede hangi değer olduğunu gösterir ama elemanı çıkarmaz.
isEmpty, yapının boş olup olmadığını kontrol eder.

`INT_MIN` Notu

Bu örnekte hata durumunu göstermek için INT_MIN döndürüyoruz.
Bu, başlangıç düzeyinde anlaşılır ve pratik bir çözümdür.
Ancak gerçek veri olarak da INT_MIN tutulmak istenirse, hata durumu ile gerçek veri karışabilir.
Daha güvenli tasarımlarda ek bir durum değeri ya da çıktı parametresi kullanılabilir.

Bağlı Liste Tabanlı Yığında `isFull` Meselesi

Bağlı liste tabanlı yığında genellikle sabit kapasite yoktur.
Bu yüzden çoğu zaman ayrı bir isFull() fonksiyonu yazılmaz.
Sınır, sistemin ayırabildiği fiziksel bellek kadardır.
Bellek ayrılamazsa push başarısız olur.

Örnek Kullanım (main)

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

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

    printf("Tepedeki eleman: %d\n", peek());
    pop();
    printf("Yeni tepe: %d\n", peek());

    pop();
    pop();

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

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

    return 0;
}

Zaman Karmaşıklığı

İşlem	Karmaşıklık
`push`	`O(1)`
`pop`	`O(1)`
`peek`	`O(1)`
`isEmpty`	`O(1)`

Hem bağlı liste hem de dizi tabanlı yığında, tepe üzerinden çalıştığımız için bu işlemler sabit zamanda yapılabilir.
Yığının temel gücü de burada ortaya çıkar.

Dizi ile Yığın: Temel Fikir

Elemanlar bir dizide tutulur.
top değişkeni son eklenen elemanın indisini gösterir.
Başlangıçta top = -1 olur.
push öncesinde doluluk, pop öncesinde boşluk kontrol edilir.

Dizi Tabanlı Yığında Taşma (Stack Overflow)

Dizi tabanlı yığında kapasite baştan belirlenir.
top == MAKS - 1 olduğunda yığın doludur.
Bu durumda yeni bir push denemesi başarısız olur.
Bu duruma stack overflow denir.

Yani burada sorun, yığının mantığında değil, ayrılmış kapasitenin dolmuş olmasındadır.

Dizi ile Yığın Kodu

#include <stdio.h>
#include <limits.h>

#define MAKS 100

int yigin[MAKS];
int top = -1;

int isEmptyArray() {
    return top == -1;
}

int isFullArray() {
    return top == MAKS - 1;
}

void pushArray(int sayi) {
    if (isFullArray()) {
        printf("Hata: Yığın dolu! (push)\n");
        return;
    }

    yigin[++top] = sayi;
}

int popArray() {
    if (isEmptyArray()) {
        printf("Hata: Yığın boş! (pop)\n");
        return INT_MIN;
    }

    return yigin[top--];
}

int peekArray() {
    if (isEmptyArray()) {
        printf("Hata: Yığın boş! (peek)\n");
        return INT_MIN;
    }

    return yigin[top];
}

Dizi ve Bağlı Liste Yaklaşımını Karşılaştıralım

Dizi tabanlı yığın
- Yapısı daha sadedir.
- Sabit kapasiteyle çalışır.
- isFull burada anlamlıdır.
Bağlı liste tabanlı yığın
- Kapasite daha esnektir.
- Her eleman için ek işaretçi alanı gerekir.
- Bellek ayırma ve serbest bırakma işlemleri vardır.

Her iki yaklaşımda da tepe üzerinden yapılan temel işlemler sabit zamanda yürür.

Alıştırmalar

Dizi tabanlı bir yığın yazıp push, pop, peek, isEmpty, isFull fonksiyonlarını test edin.
Yığın kullanarak bir metni ters çeviren C fonksiyonu yazın.
Bir ifadede (), {}, [] parantezlerinin doğru eşleşip eşleşmediğini kontrol eden algoritmayı tasarlayın.
Boş yığında INT_MIN dönmek yerine farklı bir hata yönetimi yaklaşımı düşünün.

Kapanış

Yığın, LIFO mantığıyla çalışan temel bir veri yapısıdır.
En sık kullanılan işlemleri push, pop ve peektir.
Aynı kavramı hem bağlı listeyle hem diziyle kurabiliriz.
Bu yapıyı farklı problemler üzerinde kullandıkça daha iyi kavrayacağız.