Yığınlar - Stack Veri Yapısı

Stack Nedir?

Stack (yığın), elemanların yalnızca bir uçtan eklenip çıkarılabildiği ve "Son Giren İlk Çıkar" (LIFO — Last In First Out) prensibine göre çalışan soyut bir veri yapısıdır (Abstract Data Type — ADT). Soyut veri yapısı demek, stack'in ne yapılacağını tanımlayıp nasıl yapılacağını dikte etmemesi demektir. Push, pop, peek gibi operasyonlar arayüzü oluşturur; arka planda bir dizi veya bağlı liste kullanılması ise implementasyon tercihidir. Dışarıdan bakıldığında davranış tamamen aynıdır.

Stack'in en temel kuralı şudur: ekleme ve çıkarma işlemleri yalnızca tepeden (top) yapılabilir. Ortadan veya alttan eleman çekmek stack tanımına aykırıdır. Bu kısıtlama ilk bakışta dezavantaj gibi görünse de, aslında stack'i güçlü kılan tam da bu disiplindir. Fonksiyon çağrıları, geri alma (undo) sistemi, parantez dengesi kontrolü ve derinlik öncelikli arama gibi pek çok problem bu disipline doğal olarak uyar.

En bilindik gerçek hayat örneği üst üste dizilmiş tabaklardır: yeni tabak her zaman en üste konur ve kullanmak istediğinizde en üsttekini alırsınız. Alttaki tabağa ulaşmak için üsttekileri tek tek kaldırmanız gerekir. Başka bir örnek silah şarjörüdür: ilk doldurulan mermi en sona iner ve en son doldurulan mermi ilk ateşlenir.

LIFO vs FIFO

Stack'in LIFO (Last In, First Out) prensibini tam olarak kavramak için, karşıtı olan FIFO (First In, First Out) ile karşılaştırmak faydalıdır. FIFO, queue (kuyruk) veri yapısının prensibidir ve sıra mantığıyla çalışır: ilk gelen ilk çıkar. Stack bir tabak yığınıdır (son konan tabak ilk alınır), queue ise bir market kasası kuyruğudur (ilk gelen müşteri ilk çıkar).

Temel Kavramlar ve Terminoloji

Top (Tepe)

Stack'in en üstündeki elemandır ve stack'te doğrudan erişilebilen tek elemandır. Push ile yeni eleman top'a eklenir, pop ile top'taki eleman çıkarılır, peek ile top okunur. Alttaki elemanlara doğrudan erişim yoktur; onlara ulaşmak için üsttekileri tek tek çıkarmak gerekir. Dizi tabanlı stack'te top bir indeks değişkenidir (0, 1, 2…). Linked list tabanlı stack'te ise top, listenin head pointer'ıdır.

Stack Operasyonları

Overflow ve Underflow

Stack Overflow: Dolu bir stack'e push yapmaya çalışmaktır. Dizi tabanlı stack'lerde kapasite sınırı olduğu için bu durum oluşabilir. Linked list tabanlı stack'lerde teorik olarak bellek bitene kadar overflow olmaz. Bu kavramı bir de şöyle düşünün: bilgisayardaki fonksiyon çağrı yığını (call stack) da sonlu bir alandır. Sonsuz recursion, call stack'i taşırır ve programın "stack overflow" hatasıyla çökmesine yol açar — ünlü programcı sitesi stackoverflow.com de adını buradan alır.

Stack Underflow: Boş bir stack'ten pop veya peek yapmaya çalışmaktır. Her iki implementasyonda da olabilir. Kontrol edilmezse dizi tabanlıda geçersiz indeks erişimi, linked list tabanlıda NULL pointer dereference'a neden olur ve program çöker.

Dizi Tabanlı Stack (Array-Based)

Stack'i gerçeklemenin en basit ve en yaygın yolu bir dizi kullanmaktır. Sabit boyutlu bir dizi elemanları saklar. Bir top değişkeni tepedeki elemanın indeksini takip eder. Stack boşken top = -1'dir; her push ile top bir artar, her pop ile bir azalır.

Bellekteki Görünüm

Dizi tabanlı stack'te elemanlar bellekte ardışık olarak yer alır. Bu ardışıklık, CPU cache'inin çok verimli çalışmasını sağlar ve stack'in hızlı olmasının en büyük sebebidir. Top indeksi mantıksal olarak "stack'in tepesi"ni gösterir; top'un üstündeki indeksler fiziksel olarak bellekte olsa da stack dışında kabul edilir.

Stack Yapısı ve Oluşturma

C dilinde stack yapısını bir struct ile tanımlarız. İki bileşen yeterlidir: elemanları saklayan sabit boyutlu bir dizi ve tepedeki elemanın indeksini tutan bir top değişkeni. stackOlustur fonksiyonu top'u -1 yaparak stack'i "boş" duruma getirir.

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

#define MAX 100

typedef struct {
    int items[MAX];   // elemanları tutan dizi
    int top;           // tepedeki elemanın indeksi
} Stack;

// Stack oluşturma (initialize)
void stackOlustur(Stack* s) {
    s->top = -1;      // -1 = boş stack
}

isEmpty ve isFull Kontrolleri

Her push ve pop operasyonundan önce stack'in durumunu kontrol etmek zorunludur. Kontrol yapmadan işlem yapmak, dizi sınırını aşma veya negatif indekse erişme gibi ciddi hatalara yol açar. Bu kontroller O(1) karmaşıklığındadır — sadece top değişkeninin değerine bakılır.

// Stack boş mu?
int isEmpty(Stack* s) {
    return s->top == -1;
}
// top == -1 → hiçbir eleman yok → boş (return 1)
// top >= 0  → en az bir eleman var (return 0)

// Stack dolu mu?
int isFull(Stack* s) {
    return s->top == MAX - 1;
}
// top == MAX-1 → son indeks dolu → stack dolu (return 1)
// top <  MAX-1 → hâlâ yer var (return 0)

// Kullanım:
Stack s;
stackOlustur(&s);
printf("Boş: %d\n", isEmpty(&s));   // 1 (true)
printf("Dolu: %d\n", isFull(&s));   // 0 (false)

Stack Boyutu (size)

Stack'teki eleman sayısını bulmak son derece basittir: top + 1. Top indeksi 0-tabanlı olduğu için eleman sayısı her zaman top'tan bir fazladır.

int size(Stack* s) {
    return s->top + 1;
}

// top = -1 → size = 0 (boş)
// top =  0 → size = 1 (tek eleman)
// top =  4 → size = 5
// top = MAX-1 → size = MAX (dolu)

Push İşlemi

Push, stack'in tepesine yeni eleman ekler. İşlem iki adımdan oluşur: önce top'u bir artır, sonra yeni elemanı items[top] pozisyonuna yaz. Push'tan önce isFull kontrolü yapılmalıdır; aksi halde dizinin sınırları dışına yazılır ve tanımsız davranış (undefined behavior) oluşur.

void push(Stack* s, int deger) {
    // 1. Overflow kontrolü
    if (isFull(s)) {
        printf("Stack Overflow! Kapasite: %d\n", MAX);
        return;
    }

    // 2. top'u artır
    s->top++;

    // 3. Yeni elemanı yaz
    s->items[s->top] = deger;

    // Tek satırda yazılışı: s->items[++s->top] = deger;
}

// Kullanım:
Stack s;
stackOlustur(&s);
push(&s, 10);   // top: -1→0, items[0]=10
push(&s, 20);   // top:  0→1, items[1]=20
push(&s, 30);   // top:  1→2, items[2]=30

Pop İşlemi

Pop, tepedeki elemanı stack'ten çıkarır ve değerini döndürür. İşlem üç adımdan oluşur: top'taki elemanı bir değişkene oku, top'u bir azalt, okunan değeri döndür. Pop'tan önce isEmpty kontrolü yapılmalıdır.

Önemli bir detay: pop sırasında eleman bellekten fiziksel olarak silinmez. Sadece top indeksi geri çekilir ve o pozisyon artık "stack dışında" kabul edilir. Bir sonraki push o pozisyonun üzerine yazacaktır. Bu, performans için avantajlıdır çünkü silme maliyeti sıfırdır.

int pop(Stack* s) {
    // 1. Underflow kontrolü
    if (isEmpty(s)) {
        printf("Stack Underflow! Stack boş.\n");
        return -1;   // hata değeri
    }

    // 2. Tepedeki elemanı oku
    int deger = s->items[s->top];

    // 3. top'u geri çek
    s->top--;

    // 4. Okunan değeri döndür
    return deger;

    // Tek satırda: return s->items[s->top--];
}

// Kullanım: (stack: 10, 20, 30, 40)
int x = pop(&s);   // x = 40 (son eklenen ilk çıkar)
int y = pop(&s);   // y = 30
int z = pop(&s);   // z = 20
pop(&s);            // → 10
pop(&s);            // "Stack Underflow!" (boş)

Peek (Top) İşlemi

Peek, tepedeki elemana bakar ama çıkarmaz. Pop'un "salt-okunur" versiyonudur. Stack'in durumunu hiçbir şekilde değiştirmez: ne top indeksi ne de elemanlar etkilenir. Ardı ardına 100 kez peek çağırsanız bile her seferinde aynı değer döner ve stack aynı kalır.

Peek, birçok algoritmada kritik öneme sahiptir. Örneğin parantez eşleştirmede yeni bir kapanış parantezi geldiğinde, stack'in tepesindeki açılış parantezinin eşleşip eşleşmediğini kontrol etmek için önce peek yapılır. Eşleşiyorsa pop yapılır, eşleşmiyorsa hata bildirilir. Bu karar mekanizması olmadan algoritma çalışamaz.

int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack boş, peek yapılamaz!\n");
        return -1;
    }
    return s->items[s->top];   // top DEĞİŞMEZ!
}

// push(10), push(20), push(30) sonrası:
printf("%d\n", peek(&s));      // 30
printf("%d\n", peek(&s));      // 30 (hâlâ aynı, stack değişmedi)
printf("Boyut: %d\n", size(&s)); // 3 (boyut aynı)
pop(&s);                        // 30 çıktı
printf("%d\n", peek(&s));      // 20 (yeni top)

Stack'i Yazdırma

Gerçek bir stack'te sadece top'a erişim vardır; tüm elemanları görmek soyutlamayı kırar. Ancak debug ve eğitim amacıyla top'tan aşağıya doğru yazdırma fonksiyonu son derece kullanışlıdır.

void stackYazdir(Stack* s) {
    if (isEmpty(s)) {
        printf("[Stack boş]\n");
        return;
    }
    printf("Stack (top → bottom):\n");
    for (int i = s->top; i >= 0; i--) {
        if (i == s->top)
            printf("  → [%d] %d  ← TOP\n", i, s->items[i]);
        else
            printf("    [%d] %d\n", i, s->items[i]);
    }
    printf("  Boyut: %d / %d\n", size(s), MAX);
}

// Çıktı (push 10, 20, 30 sonrası):
// Stack (top → bottom):
//   → [2] 30  ← TOP
//     [1] 20
//     [0] 10
//   Boyut: 3 / 100

Tam Çalışan Program

Tüm operasyonları bir araya getiren eksiksiz bir program. Overflow ve underflow durumlarını, push/pop/peek sıralamasını ve size/isEmpty/isFull kontrollerini gösterir.

#include <stdio.h>

#define MAX 5

typedef struct {
    int items[MAX];
    int top;
} Stack;

void stackOlustur(Stack* s) { s->top = -1; }
int  isEmpty(Stack* s)      { return s->top == -1; }
int  isFull(Stack* s)       { return s->top == MAX - 1; }
int  size(Stack* s)         { return s->top + 1; }

void push(Stack* s, int val) {
    if (isFull(s)) { printf("  ⚠ Overflow!\n"); return; }
    s->items[++s->top] = val;
    printf("  push(%d) → top=%d, size=%d\n", val, s->top, s->top + 1);
}

int pop(Stack* s) {
    if (isEmpty(s)) { printf("  ⚠ Underflow!\n"); return -1; }
    int val = s->items[s->top--];
    printf("  pop() → %d, top=%d\n", val, s->top);
    return val;
}

int peek(Stack* s) {
    if (isEmpty(s)) { printf("  ⚠ Boş!\n"); return -1; }
    return s->items[s->top];
}

void stackYazdir(Stack* s) {
    if (isEmpty(s)) { printf("  [Boş]\n"); return; }
    printf("  Stack: ");
    for (int i = s->top; i >= 0; i--)
        printf("%d ", s->items[i]);
    printf("(top→bottom)\n");
}

int main() {
    Stack s;
    stackOlustur(&s);

    printf("=== Push İşlemleri ===\n");
    push(&s, 10);  push(&s, 20);  push(&s, 30);
    push(&s, 40);  push(&s, 50);
    push(&s, 60);   // overflow!

    printf("\n=== Durum ===\n");
    printf("  Peek: %d\n", peek(&s));
    printf("  Boyut: %d/%d\n", size(&s), MAX);
    printf("  Boş mu: %d\n", isEmpty(&s));
    printf("  Dolu mu: %d\n", isFull(&s));
    stackYazdir(&s);

    printf("\n=== Pop İşlemleri ===\n");
    while (!isEmpty(&s))
        pop(&s);
    pop(&s);   // underflow!

    return 0;
}

=== Push İşlemleri ===
  push(10) → top=0, size=1
  push(20) → top=1, size=2
  push(30) → top=2, size=3
  push(40) → top=3, size=4
  push(50) → top=4, size=5
  ⚠ Overflow!

=== Durum ===
  Peek: 50
  Boyut: 5/5
  Boş mu: 0
  Dolu mu: 1
  Stack: 50 40 30 20 10 (top→bottom)

=== Pop İşlemleri ===
  pop() → 50, top=3
  pop() → 40, top=2
  pop() → 30, top=1
  pop() → 20, top=0
  pop() → 10, top=-1
  ⚠ Underflow!

Dinamik Dizi Tabanlı Stack

Yukarıda sabit boyutlu (static) dizi tabanlı stack'i inceledik. Bu yaklaşımın en büyük sorunu kapasitenin derleme zamanında belirlenmesidir. #define MAX 100 yazdığınızda, stack en fazla 100 eleman tutabilir — ne eksik ne fazla. Kapasite küçükse overflow, büyükse bellek israfı yaşarsınız. Peki ya kaç eleman geleceğini bilmiyorsak?

Dinamik dizi tabanlı stack, bu sorunu çalışma zamanında çözer. Başlangıçta küçük bir kapasite ile başlanır (örneğin 4) ve stack dolduğunda realloc ile kapasite 2 katına çıkarılır. Bu strateji "doubling strategy" olarak bilinir.

Doubling Strategy Nasıl Çalışır?

Amortized O(1) Analizi

Her realloc çağrısı O(n) sürer çünkü tüm elemanlar eski bellekten yeni belleğe kopyalanır. Bu ilk bakışta push'un O(n) olduğu izlenimini verebilir. Ancak realloc her push'ta değil, sadece dolu olunca yapılır. Kapasite her seferinde 2 katına çıktığı için geometrik seri oluşur:

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

typedef struct {
    int* items;       // dinamik dizi (heap'te)
    int top;           // tepedeki elemanın indeksi
    int kapasite;      // mevcut dizi boyutu
} DStack;

// Oluşturma
void dstackOlustur(DStack* s, int baslangicKap) {
    s->items = (int*)malloc(baslangicKap * sizeof(int));
    if (!s->items) {
        printf("Bellek ayrılamadı!\n");
        exit(1);
    }
    s->top = -1;
    s->kapasite = baslangicKap;
}

// Kontroller
int disEmpty(DStack* s) { return s->top == -1; }
int dsize(DStack* s)   { return s->top + 1; }

// Push — doluysa kapasiteyi 2 katına çıkar
void dpush(DStack* s, int deger) {
    if (s->top == s->kapasite - 1) {
        int yeniKap = s->kapasite * 2;
        int* yeni = (int*)realloc(s->items, yeniKap * sizeof(int));
        if (!yeni) {
            printf("realloc hatası!\n");
            return;
        }
        s->items = yeni;
        printf("  ↑ Kapasite %d → %d\n", s->kapasite, yeniKap);
        s->kapasite = yeniKap;
    }
    s->items[++s->top] = deger;
}

// Pop
int dpop(DStack* s) {
    if (disEmpty(s)) {
        printf("Underflow!\n");
        return -1;
    }
    return s->items[s->top--];
}

// Peek
int dpeek(DStack* s) {
    if (disEmpty(s)) {
        printf("Stack boş!\n");
        return -1;
    }
    return s->items[s->top];
}

// Belleği serbest bırak
void dstackSerbest(DStack* s) {
    free(s->items);
    s->items = NULL;
    s->top = -1;
    s->kapasite = 0;
}

Shrink Stratejisi (Opsiyonel)

Dinamik stack'te sadece büyüme değil, küçülme de uygulanabilir. Pop sonrası eleman sayısı kapasitenin ¼'üne düştüğünde kapasiteyi yarıya indirmek bellekten tasarruf sağlar. Neden ½ değil de ¼? Eğer eşik ½ olursa, tam sınırda art arda push-pop yapıldığında sürekli genişle-küçül döngüsü oluşur (thrashing). ¼ eşiği bu sorunu önler.

int dpopShrink(DStack* s) {
    if (disEmpty(s)) { printf("Underflow!\n"); return -1; }

    int deger = s->items[s->top--];

    // Kapasite çok büyükse küçült (min kapasite: 4)
    if (s->top + 1 > 0 &&
        s->top + 1 == s->kapasite / 4 &&
        s->kapasite > 4)
    {
        s->kapasite /= 2;
        s->items = (int*)realloc(s->items,
                   s->kapasite * sizeof(int));
        printf("  ↓ Kapasite %d'ye küçültüldü\n", s->kapasite);
    }

    return deger;
}

Bağlı Liste Tabanlı Stack

Stack'i linked list ile gerçeklemek, kapasite sorununu tamamen ortadan kaldırır: her yeni push için bir düğüm oluşturulur, bellek bitene kadar overflow olmaz. İsFull kontrolüne gerek yoktur. Push işlemi linked list'in başına ekleme, pop işlemi baştan silme ile birebir eşleşir — her ikisi de zaten O(1) olan operasyonlardır.

Eşleşme: Stack ↔ Linked List

Push ve Pop Görsel

Tam Implementasyon

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

// ── Düğüm yapısı ──
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// ── Stack yapısı ──
typedef struct {
    Node* top;     // listenin başı = stack'in tepesi
    int boyut;     // eleman sayısı (O(1) size için)
} LLStack;

// ── Oluşturma ──
void llStackOlustur(LLStack* s) {
    s->top = NULL;
    s->boyut = 0;
}

// ── Kontroller ──
int llIsEmpty(LLStack* s) { return s->top == NULL; }
int llSize(LLStack* s)    { return s->boyut; }

// ── Push = başa ekleme ──
void llPush(LLStack* s, int deger) {
    Node* yeni = (Node*)malloc(sizeof(Node));
    if (!yeni) {
        printf("Bellek ayrılamadı!\n");
        return;
    }
    yeni->data = deger;       // veriyi ata
    yeni->next = s->top;      // yeninin next'i → eski top
    s->top = yeni;             // yeni düğüm artık top
    s->boyut++;

    printf("  push(%d) → boyut=%d\n", deger, s->boyut);
}

// ── Pop = baştan silme ──
int llPop(LLStack* s) {
    if (llIsEmpty(s)) {
        printf("  ⚠ Underflow!\n");
        return -1;
    }

    Node* silinecek = s->top;          // ①
    int deger = silinecek->data;        // ② değeri kaydet
    s->top = silinecek->next;           // ③ top → sonraki
    free(silinecek);                     // ④ eski top'u serbest bırak
    s->boyut--;

    printf("  pop() → %d, boyut=%d\n", deger, s->boyut);
    return deger;
}

// ── Peek ──
int llPeek(LLStack* s) {
    if (llIsEmpty(s)) {
        printf("  ⚠ Stack boş!\n");
        return -1;
    }
    return s->top->data;    // sadece oku, çıkarma
}

// ── Yazdırma ──
void llYazdir(LLStack* s) {
    if (llIsEmpty(s)) { printf("  [Boş]\n"); return; }
    printf("  top");
    Node* temp = s->top;
    while (temp) {
        printf(" → [%d]", temp->data);
        temp = temp->next;
    }
    printf(" → NULL\n");
}

// ── Tüm stack'i serbest bırak ──
void llStackSerbest(LLStack* s) {
    while (!llIsEmpty(s))
        llPop(s);
}

// ── Demo ──
int main() {
    LLStack s;
    llStackOlustur(&s);

    printf("=== Push ===\n");
    llPush(&s, 10);
    llPush(&s, 20);
    llPush(&s, 30);
    llPush(&s, 40);
    llYazdir(&s);

    printf("\nPeek: %d\n", llPeek(&s));

    printf("\n=== Pop ===\n");
    llPop(&s);
    llPop(&s);
    llYazdir(&s);

    llStackSerbest(&s);

    return 0;
}

=== Push ===
  push(10) → boyut=1
  push(20) → boyut=2
  push(30) → boyut=3
  push(40) → boyut=4
  top → [40] → [30] → [20] → [10] → NULL

Peek: 40

=== Pop ===
  pop() → 40, boyut=3
  pop() → 30, boyut=2
  top → [20] → [10] → NULL
  pop() → 20, boyut=1
  pop() → 10, boyut=0

Üç Implementasyonun Karşılaştırması

Stack Nerelerde Kullanılır?

1. Fonksiyon Çağrı Yığını (Call Stack)

Programlama dillerinin çalışma zamanı ortamı fonksiyon çağrılarını bir stack ile yönetir. Her fonksiyon çağrıldığında stack'e bir "stack frame" push edilir. Bu frame, fonksiyonun yerel değişkenlerini, parametrelerini ve dönüş adresini içerir. Fonksiyon bittiğinde frame pop edilir ve kontrol çağıran fonksiyona döner.

Recursive fonksiyonlarda her çağrı yeni bir frame oluşturur. Eğer recursion çok derine giderse (örneğin base case'siz bir factorial fonksiyonu), call stack taşar ve program "Segmentation fault" veya "Stack Overflow" hatası ile çöker. Linux'ta varsayılan call stack boyutu genellikle 8 MB'dır.

2. Geri Alma (Undo) / Yeniden Yapma (Redo)

Metin editörlerinde her eylem undo stack'ine push edilir. Ctrl+Z basıldığında son eylem pop edilip geri alınır ve redo stack'ine push edilir. Ctrl+Y (veya Ctrl+Shift+Z) basıldığında redo stack'inden pop edilip tekrar uygulanır. İki stack birlikte çalışarak ileri-geri gezinme sağlar.

3. Parantez Eşleştirme

Derleyiciler ve kod editörleri, parantez dengesi kontrolünü stack ile yapar. Açılan her parantez push, kapanan her parantez peek + pop ile kontrol edilir. Bu algoritma () [] {} <> tüm eşleşen semboller için çalışır.

int parantezDengeli(const char* ifade) {
    Stack s;
    stackOlustur(&s);

    for (int i = 0; ifade[i] != '\0'; i++) {
        char c = ifade[i];

        // Açılış → push
        if (c == '(' || c == '[' || c == '{') {
            push(&s, c);
        }
        // Kapanış → peek + pop ile kontrol
        else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty(&s)) return 0;  // eşi yok

            char top = pop(&s);
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
                return 0;  // yanlış eşleşme
        }
    }
    return isEmpty(&s);  // stack boşsa dengeli
}

parantezDengeli("{[()]}");   // 1 (dengeli ✓)
parantezDengeli("([)]");     // 0 (çapraz ✗)
parantezDengeli("(((");      // 0 (kapanmamış ✗)
parantezDengeli("()");       // 1 (dengeli ✓)

4. Postfix İfade Değerlendirme

Hesap makineleri ve derleyiciler, matematiksel ifadeleri stack ile değerlendirir. İnfix ifade (3 + 4 * 2) önce postfix'e (3 4 2 * +) çevrilir, sonra stack ile hesaplanır: sayılar push edilir, operatör geldiğinde iki sayı pop edilip işlem yapılıp sonuç push edilir.

5. Tarayıcı Geri/İleri Butonu

Ziyaret edilen her sayfa "back stack"e push edilir. Geri butonu son sayfayı pop edip "forward stack"e push eder. İleri butonu bunun tersini yapar. Undo/redo ile aynı iki-stack mekanizmasıdır.

6. DFS (Derinlik Öncelikli Arama)

Graf ve ağaç yapılarında derinlik öncelikli arama stack kullanır. Her adımda mevcut düğümün komşuları push edilir ve pop edilen düğüm ziyaret edilir. Recursive DFS ise aslında call stack'i dolaylı olarak kullanır — explicit stack ile iteratif DFS yazmak aynı sonucu verir.

7. String Tersine Çevirme

Her karakter sırayla push edilir, ardından tüm karakterler pop edilir. LIFO prensibi gereği son karakter ilk çıkar ve string otomatik olarak tersine döner.

Sık Yapılan Hatalar

1. Overflow / Underflow Kontrolü Yapmamak

En tehlikeli ve en yaygın hata. Her push'tan önce isFull (dizi tabanlıda), her pop/peek'ten önce isEmpty kontrolü zorunludur. Kontrol yapılmazsa programın çökmesi kaçınılmazdır.

// ❌ YANLIŞ: Kontrol yok
int x = s.items[s.top--];   // top=-1 ise → items[-1] → ÇÖKME
s.items[++s.top] = val;     // top=MAX-1 ise → dizi taşması

// ✅ DOĞRU: Her zaman kontrol et
if (!isEmpty(&s)) { int x = pop(&s); }
if (!isFull(&s))  { push(&s, val); }

2. Pop ve Peek Karıştırmak

Pop elemanı çıkarır, peek çıkarmaz. Sadece bakmak isteyip yanlışlıkla pop çağırmak veri kaybına yol açar. Özellikle döngü içinde koşul kontrolü yaparken peek kullanılmalıdır.

// ❌ YANLIŞ: Sadece bakmak istiyorduk ama pop yaptık
if (pop(&s) == hedef) {
    // eleman zaten çıktı, tekrar erişilemez!
}

// ✅ DOĞRU: Önce peek ile bak, gerekirse pop yap
if (peek(&s) == hedef) {
    int x = pop(&s);   // şimdi bilinçli çıkardık
}

3. Pre/Post Increment-Decrement Karışıklığı

// Push: ÖNCE artır, SONRA yaz → pre-increment
s->items[++s->top] = deger;   // ✅ doğru pozisyona yazar
s->items[s->top++] = deger;   // ❌ eski pozisyona yazar

// Pop: ÖNCE oku, SONRA azalt → post-decrement
return s->items[s->top--];    // ✅ doğru elemanı döndürür
return s->items[--s->top];    // ❌ bir alttakini döndürür

4. Linked List Stack'te free() Unutmak

Pop sırasında düğümü free() etmemek bellek sızıntısına (memory leak) neden olur. Her pop'ta eski düğüm free edilmelidir. Programın sonunda kalan düğümler için llStackSerbest() çağırmak iyi bir alışkanlıktır.

// ❌ YANLIŞ: free() yok → bellek sızıntısı
int llPop_hatali(LLStack* s) {
    int deger = s->top->data;
    s->top = s->top->next;   // eski düğüm kayıp!
    return deger;
}

// ✅ DOĞRU: Önce kaydet, sonra free
int llPop_dogru(LLStack* s) {
    Node* silinecek = s->top;   // ① pointer'ı kaydet
    int deger = silinecek->data; // ② değeri kaydet
    s->top = silinecek->next;    // ③ top'u ilerlet
    free(silinecek);              // ④ belleği serbest bırak
    return deger;
}

5. Stack'i Queue Gibi Kullanmak

Stack'in ortasından veya altından eleman çıkarmak tanım gereği mümkün değildir. Eğer FIFO davranışına ihtiyaç duyuyorsanız queue kullanmalısınız. İki stack kullanarak bir queue simüle etmek mümkündür — bu yaygın bir mülakat sorusudur ve stack uygulamaları bölümünde ele alınacaktır.

Zaman ve Alan Karmaşıklığı Özeti

* Linked list'te boyut sayacı tutuluyorsa O(1), yoksa traverse gerekir O(n).

Sonuç

Stack, programlamanın en temel yapı taşlarından biridir. LIFO prensibi basit görünse de bu prensibin uygulandığı alanlar son derece geniştir: fonksiyon çağrı yönetiminden parantez eşleştirmeye, undo mekanizmalarından DFS algoritmasına kadar her yerde stack karşımıza çıkar. Tüm temel operasyonlarının O(1) olması, stack'i kullanım alanında son derece verimli bir araç yapar.

Üç implementasyon yöntemini de bilmek önemlidir: sabit dizi en basiti, dinamik dizi en pratik olanı, linked list ise en esnek olanıdır. Gerçek dünya uygulamalarında genellikle dinamik dizi tabanlı tercih edilir (cache locality avantajı); ancak kapasite bilinmediğinde linked list güçlü bir alternatiftir.

Bir sonraki bölümde stack'in uygulamalarını detaylı olarak inceleyeceğiz: postfix ifade değerlendirme, infix→postfix dönüşüm (Shunting Yard algoritması), min stack, iki stack ile queue simülasyonu ve recursion'ın stack ile iteratif hale dönüştürülmesi. Ardından stack'in ikizi olan queue (kuyruk) veri yapısına geçeceğiz.