Yığın (stack): dizi ve bağlı liste ile

Yığın (stack) üst üste konmuş tabaklar gibidir: tabağı en üste koyarsın, alırken de en üsttekini alırsın. Ortadan tabak çekemezsin. Bu kurala LIFO (Last In, First Out) denir. Basit görünür ama derleyicilerin ifade hesaplaması, metot çağrıları, geri al (undo) özelliği ve parantez kontrolü hep yığınla çalışır. Sınav soruları iki tiptir: bir işlem dizisinden sonra ne basıldığını ya da yığında ne kaldığını bulmak, ve push/pop’u dizi ya da bağlı liste ile yazmak.

Altın kurallar:

1. Sadece tepeye erişirsin. push tepeye koyar, pop tepeden alır.
2. peek bakar, silmez. İz sürerken pop ile peek’i karıştırma.
3. Dizide top son elemanın indeksidir. Boş yığında -1.
4. Bağlı listede tepe listenin başıdır. Sonu değil.
5. Boş yığından pop = underflow, dolu diziye push = overflow.

Soyut veri tipi (ADT)

Yığın bir soyut veri tipidir (abstract data type): hangi işlemlerin olduğunu söyler, nasıl yapıldığını söylemez. İşlemler:

Aynı ADT’yi iki şekilde gerçekleyebiliriz: diziyle ya da bağlı listeyle. Kullanan kod farkı görmez.

Dizi ile yığın (array-based stack)

class ArrayStack {
    private int[] data;
    private int top = -1;   // son elemanın indeksi

    ArrayStack(int capacity) { data = new int[capacity]; }

    boolean isEmpty() { return top == -1; }
    boolean isFull()  { return top == data.length - 1; }
    int size()        { return top + 1; }

    void push(int x) {
        if (isFull()) throw new RuntimeException("Stack overflow");
        data[++top] = x;    // önce artır, sonra yaz
    }

    int pop() {
        if (isEmpty()) throw new RuntimeException("Stack underflow");
        return data[top--]; // önce oku, sonra azalt
    }

    int peek() {
        if (isEmpty()) throw new RuntimeException("Stack underflow");
        return data[top];
    }
}

++top ile top-- farkı burada kritik. data[top++] = x yazarsan ilk eleman data[-1]’e yazılmaya çalışılır ve ArrayIndexOutOfBoundsException alırsın.

Çözümlü örnek

ArrayStack s = new ArrayStack(5);
s.push(10); s.push(20); s.push(30);
System.out.println(s.pop());
System.out.println(s.peek());
s.push(40);
System.out.println(s.size() + " " + s.raw());   // raw: dizinin ham hali

30
20
3 [10, 20, 40, 0, 0] top=2

push 10     [10, _, _, _, _]   top=0
push 20     [10, 20, _, _, _]  top=1
push 30     [10, 20, 30, _, _] top=2
pop → 30    [10, 20, 30, _, _] top=1   (30 dizide duruyor ama yığında değil)
peek → 20   değişiklik yok
push 40     [10, 20, 40, _, _] top=2   (30'un üstüne yazıldı)

TUZAK · pop diziden silmez. Sınavda “dizinin içeriği ne?” diye sorulursa pop edilmiş değerler hâlâ oradadır, sadece top indeksinin üstünde kalırlar. Yeni bir push onların üstüne yazar.

Dolunca büyütmek

Sabit kapasite yerine dolunca iki katı büyüklükte yeni dizi açıp kopyalayabilirsin. O push O(n) sürer, ama kapasite her seferinde ikiye katlandığı için bu nadiren olur. n push’un toplam maliyeti O(n), yani push başına ortalama (amortized) O(1). Java’nın ArrayList ve ArrayDeque sınıfları böyle çalışır.

Bağlı liste ile yığın (linked stack)

Tek yönlü listenin başına ekleme ve baştan silme zaten O(1). Tepe = baş.

class LinkedStack {
    private static class Node {
        int data; Node next;
        Node(int d, Node n) { data = d; next = n; }
    }
    private Node top;

    boolean isEmpty() { return top == null; }

    void push(int x) { top = new Node(x, top); }

    int pop() {
        if (top == null) throw new RuntimeException("Stack underflow");
        int x = top.data;
        top = top.next;
        return x;
    }

    int peek() {
        if (top == null) throw new RuntimeException("Stack underflow");
        return top.data;
    }
}

Bu gerçeklemede overflow yok (bellek bitene kadar). Bedeli düğüm başına bir next referansı.

Yığın ile yapılan klasik işler

Ters çevirme. Harfleri sırayla it, sonra çek: “DATA” → “ATAD”. Yığına giren sıra, çıkışta tersine döner.

Ondalıktan ikiliğe. n % 2 kalanlarını it, n’yi ikiye böl; sonra hepsini çek. 13 → 1101, 6 → 110, 32 → 100000.

static String toBinary(int n) {
    if (n == 0) return "0";
    Deque<Integer> s = new ArrayDeque<>();
    while (n > 0) { s.push(n % 2); n /= 2; }
    StringBuilder sb = new StringBuilder();
    while (!s.isEmpty()) sb.append(s.pop());
    return sb.toString();
}

Metot çağrıları. Java her metot çağrısında yerel değişkenleri bir yığın çerçevesine (stack frame) koyar; metot bitince çerçeve pop edilir. Sonsuz özyineleme bu yığını doldurur ve StackOverflowError verir (10. hafta).

Diğer uygulamalar (parantez dengesi, infix → postfix, postfix hesaplama) gelecek haftanın konusu.

Pop sırası soruları

“1, 2, 3, 4 sırasıyla push ediliyor, aradaki herhangi bir anda pop yapılabilir. Hangi çıkış sırası mümkün?” Çözmek için simüle et: çıkması gereken sayıya kadar push et, sonra tepe o sayı mı diye bak.

Hedef 3 1 4 2:
  3 lazım → push 1, 2, 3 → pop 3       yığın [1, 2]
  1 lazım → tepe 2, 1 değil            İMKANSIZ

Hedef 3 2 4 1:
  push 1,2,3 → pop 3 → [1,2]
  pop 2 → [1]
  push 4 → pop 4 → [1]
  pop 1                                MÜMKÜN

Kısa kural: bir sayı çıktıktan sonra, ondan küçük olup henüz çıkmamış sayılar azalan sırada çıkmak zorunda.

Java’da hazır yığın

java.util.Stack sınıfı eskidir (Vector’den türer, senkronize, yavaş). Modern Java’da önerilen Deque arayüzü ve ArrayDeque sınıfıdır:

Deque<Integer> st = new ArrayDeque<>();
st.push(1); st.push(2);
st.peek();   // 2
st.pop();    // 2

Boş ArrayDeque üzerinde pop() NoSuchElementException fırlatır, peek() ise null döner. Ayrıntısı 9. haftada.

Sık yapılan hatalar

s.push(5); s.push(3);
System.out.print(s.pop() + " ");
s.push(8); s.push(1);
System.out.print(s.pop() + " ");
System.out.print(s.pop() + " ");
s.push(6);
System.out.println(s.peek());

for (int i = 1; i <= 5; i++) {
    s.push(i * 2);
    if (i % 2 == 0)
        System.out.print(s.pop() + " ");
}

push(7); push(2); push(9);
pop(); pop();
push(4);

try {
    for (int i = 1; i <= 4; i++) {
        s.push(i);
        System.out.print(i + " ");
    }
} catch (RuntimeException e) {
    System.out.println("-> " + e.getMessage());
}

int pop() {
    if (top == -1)
        throw new RuntimeException("Stack underflow");
    return data[top--];   // önce oku, sonra azalt
}

void push(int x) {
    top = new Node(x, top);
}

int pop() {
    if (top == null)
        throw new RuntimeException("Stack underflow");
    int x = top.data;
    top = top.next;
    return x;
}

static String f(String w) {
    Deque<Character> st = new ArrayDeque<>();
    for (char ch : w.toCharArray()) st.push(ch);
    StringBuilder sb = new StringBuilder();
    while (!st.isEmpty()) sb.append(st.pop());
    return sb.toString();
}

while (!s.isEmpty()) {
    int x = s.pop();
    if (x % 2 == 0) t.push(x);
}
while (!t.isEmpty())
    System.out.print(t.pop() + " ");

static String toBinary(int n) {
    if (n == 0) return "0";
    Deque<Integer> s = new ArrayDeque<>();
    while (n > 0) {
        s.push(n % 2);
        n /= 2;
    }
    StringBuilder sb = new StringBuilder();
    while (!s.isEmpty()) sb.append(s.pop());
    return sb.toString();
}

int sum = 0;
while (s.peek() != 4)
    sum += s.pop();
System.out.println(sum + " " + s.peek());