2.3: Stack Analizi

📐 Big O Notasyonu Hatırlatma

Big O, bir algoritmanın en kötü durumda ne kadar süreceğini gösterir. Stack için şunları anlamamız gerekir:

O(1) - Sabit Zaman: İşlem süresi veri boyutundan bağımsız. 10 eleman da olsa, 10 milyon da olsa aynı süre.
O(n) - Doğrusal Zaman: Veri iki katına çıkarsa, süre de iki katına çıkar.

Zaman Karmaşıklığı (Time Complexity)

Operasyon	Karmaşıklık	Açıklama
Push	O(1)	Dizinin sonuna ekleme. Her zaman tek adım, veri boyutu önemli değil.
Pop	O(1)	Dizinin sonundan silme. Her zaman tek adım.
Peek (Üste Bak)	O(1)	En üstteki elemana bakmak. Sadece indeks erişimi.
isEmpty	O(1)	Stack boş mu? Top değişkenine bakmak yeterli.
Arama (Search)	O(n)	Stack'te arama yapmak için tüm elemanları kontrol etmek gerekir.

✅ Neden O(1) Bu Kadar İyi?

Stack'te 10 eleman olsa da, 10 milyon eleman olsa da push/pop aynı sürede tamamlanır. Bu "sabit zaman" garantisi, stack'i çok güvenilir bir veri yapısı yapar.

💾 Alan Karmaşıklığı (Space Complexity)

Durum	Alan	Açıklama
Genel	O(n)	n eleman tutmak için n birim bellek gerekir
Her işlem	O(1)	Push/Pop için ek bellek gerekmez

🧪 Laboratuvar: Numpy vs Python List

1 Milyon elemanlık veri için hız testi.

Python Kodu

import time
import numpy as np

# --- NUMPY STACK SINIFI ---
class NumpyStack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = np.zeros(capacity, dtype=int)
        self.top = 0
        
    def push(self, value):
        if self.top < self.capacity:
            self.data[self.top] = value
            self.top += 1
            
    def pop(self):
        if self.top > 0:
            self.top -= 1
            return self.data[self.top]

# --- TEST ---
N = 1_000_000
print(f"{N} eleman için test...\n")

# 1. Python List
py_stack = []
start = time.time()
for i in range(N): py_stack.append(i)
while py_stack: py_stack.pop()
print(f"Python List: {time.time() - start:.4f} sn")

# 2. Numpy Stack
np_stack = NumpyStack(N)
start = time.time()
for i in range(N): np_stack.push(i)
while np_stack.top > 0: np_stack.pop()
print(f"Numpy Stack: {time.time() - start:.4f} sn")

print("\n--- NEDEN NUMPY DAHA YAVAŞ ÇIKTI? ---")
print("1. Python 'list' yapısı C dili ile yazılmıştır ve çok optimize edilmiştir.")
print("2. Bizim yazdığımız 'NumpyStack' sınıfı ise her push işleminde Python fonksiyonu çağırır.")
print("3. Python'da fonksiyon çağırmak maliyetlidir (Function Call Overhead).")
print("4. Eğer C ile yazılmış bir NumpyStack kullansaydık, listeden daha hızlı olurdu.")
print("5. Numpy'ın asıl gücü tek tek eleman eklemede değil, vektörel işlemlerde ortaya çıkar.")

import time
import numpy as np

class NumpyStack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = np.zeros(capacity, dtype=int)
        self.top = 0
    def push(self, value):
        if self.top < self.capacity:
            self.data[self.top] = value
            self.top += 1
    def pop(self):
        if self.top > 0:
            self.top -= 1
            return self.data[self.top]

N = 1_000_000
print(f"{N} eleman için test...\n")

# 1. Python List
py_stack = []
start = time.time()
for i in range(N): py_stack.append(i)
while py_stack: py_stack.pop()
print(f"Python List: {time.time() - start:.4f} sn")

# 2. Numpy Stack
np_stack = NumpyStack(N)
start = time.time()
for i in range(N): np_stack.push(i)
while np_stack.top > 0: np_stack.pop()
print(f"Numpy Stack: {time.time() - start:.4f} sn")

print("\n--- NEDEN NUMPY DAHA YAVAŞ ÇIKTI? ---")
print("1. Python 'list' yapısı C dili ile yazılmıştır ve çok optimize edilmiştir.")
print("2. Bizim yazdığımız 'NumpyStack' sınıfı ise her push işleminde Python fonksiyonu çağırır.")
print("3. Python'da fonksiyon çağırmak maliyetlidir (Function Call Overhead).")
print("4. Eğer C ile yazılmış bir NumpyStack kullansaydık, listeden daha hızlı olurdu.")
print("5. Numpy'ın asıl gücü tek tek eleman eklemede değil, vektörel işlemlerde ortaya çıkar.")

Çıktı bekleniyor...