Yığın (Stack) Veri Yapısı ve Uygulama Örnekleri

Yığınlar (Stacks), bilgisayar bilimlerinde önemli veri yapılarından biridir. Yığınlar, veri ekleme ve çıkarma işlemlerinin yalnızca bir uçtan (üstten) yapıldığı bir veri yapısıdır. Bu yapı, “son giren, ilk çıkar” (Last In, First Out – LIFO) prensibiyle çalışır. Bu yazıda, yığın (stack) veri yapısının ne olduğunu, nasıl çalıştığını ve çeşitli örneklerle nasıl uygulandığını inceleyeceğiz.

Yığın Nedir?

Yığın (Stack), veri ekleme ve çıkarma işlemlerinin yalnızca bir uçtan yapılabildiği bir veri yapısıdır. Yani, son eklenen veri ilk çıkar. Tıpkı üst üste dizilmiş tabaklar gibi düşünebiliriz; bir tabağı eklemek ya da çıkarmak istediğinizde en üstteki tabakla işlem yaparsınız. Yığındaki işlemler temel olarak şu iki işlemle gerçekleştirilir:

• Push: Yığının üstüne bir eleman ekler.
• Pop: Yığının en üstündeki elemanı çıkarır.

Yığının Temel İşlemleri

1. Push (Ekleme): Yığına bir veri ekler. Bu veri yığının en üstüne eklenir.
2. Pop (Çıkarma): Yığının en üstündeki veriyi çıkarır ve döndürür.
3. Peek (En Üstteki Elemanı Görme): Yığının en üstündeki veriyi döndürür ancak yığından çıkarmaz.
4. IsEmpty (Boşluk Kontrolü): Yığının boş olup olmadığını kontrol eder.

Yığının Python İle Uygulanması

Python’da yığın veri yapısını listelerle veya collections.deque modülü ile kolayca uygulayabiliriz. Şimdi, Python listeleri kullanarak bir yığın veri yapısının nasıl oluşturulacağını inceleyelim.

Python İle Yığın Uygulaması

class Yigin:
def __init__(self):
self.yigin = []

def push(self, veri):
self.yigin.append(veri)

def pop(self):
if not self.is_empty():
return self.yigin.pop()
else:
return “Yığın boş”

def peek(self):
if not self.is_empty():
return self.yigin[-1]
else:
return “Yığın boş”

def is_empty(self):
return len(self.yigin) == 0

def boyut(self):
return len(self.yigin)

Bu sınıf, yığın veri yapısının temel işlemlerini içerir:

• push(): Yığına yeni bir eleman ekler.
• pop(): Yığından en üstteki elemanı çıkarır.
• peek(): Yığının en üstündeki elemanı görüntüler.
• is_empty(): Yığının boş olup olmadığını kontrol eder.
• boyut(): Yığındaki eleman sayısını döndürür.

Örnek Kullanım

Yığın sınıfını kullanarak basit bir örnek yapalım:

y = Yigin()

y.push(5)
y.push(10)
y.push(15)

print(y.peek()) # Çıktı: 15
print(y.pop()) # Çıktı: 15
print(y.pop()) # Çıktı: 10
print(y.is_empty()) # Çıktı: False
print(y.pop()) # Çıktı: 5
print(y.is_empty()) # Çıktı: True

Bu örnek, yığına eleman ekleme (push) ve çıkarma (pop) işlemlerini göstermektedir.

Yığınların Kullanım Alanları

Yığınlar birçok farklı problemde kullanılır. Bazı yaygın kullanım alanları şunlardır:

1. Fonksiyon Çağrı Yığınları: Yığınlar, programların fonksiyon çağrılarını takip etmek için kullanılır. Her fonksiyon çağrıldığında yığına eklenir ve çağrı tamamlandığında yığından çıkar.
2. Undo/Redo İşlemleri: Metin düzenleyicilerinde yapılan işlemleri geri alma (undo) veya ileri alma (redo) işlemleri yığınlar yardımıyla gerçekleştirilir. Son yapılan işlem geri alınırken yığından çıkarılır, ileri alınacak işlemler yığının başka bir versiyonunda tutulur.
3. Parantez Dengesi Kontrolü: Bir metin içinde parantezlerin dengeli olup olmadığını kontrol etmek için yığınlar kullanılır. Açılan her parantez yığına eklenir ve kapandığında yığından çıkarılır. Bu işlem sonunda yığın boşsa, parantezler dengelidir.
4. İfade Çözümleme (Postfix, Prefix): Matematiksel ifadeleri (infix, postfix, prefix) çözümlemek için yığınlar kullanılır.

Örnek Uygulama: Parantez Dengesi Kontrolü

Yığınların önemli bir uygulaması olan parantez dengesi kontrolünü inceleyelim. Bu problemde, bir metin içindeki parantezlerin açılıp kapanma sıralamasının doğru olup olmadığını kontrol etmek istiyoruz. Yani, her açılan parantezin bir kapanan parantezi olmalı ve parantezler doğru sırada kapanmalı.

Python İle Parantez Dengesi Kontrolü

def parantez_dengesi(metin):
yigin = Yigin()
parantez_eslesmesi = {‘)’: ‘(‘, ‘]’: ‘[‘, ‘}’: ‘{‘}

for karakter in metin:
if karakter in parantez_eslesmesi.values(): # Açılan parantezler
yigin.push(karakter)
elif karakter in parantez_eslesmesi.keys(): # Kapanan parantezler
if yigin.is_empty() or yigin.pop() != parantez_eslesmesi[karakter]:
return False

return yigin.is_empty()

Bu fonksiyon, açılan ve kapanan parantezlerin dengeli olup olmadığını kontrol eder. Eğer açılan parantezlerin her biri doğru bir şekilde kapanıyorsa, parantezler dengelidir.

print(parantez_dengesi(“(a + b) * (c + d)”)) # Çıktı: True
print(parantez_dengesi(“{[a + b] * (c + d)}”)) # Çıktı: True
print(parantez_dengesi(“(a + b))”)) # Çıktı: False

Zaman Karmaşıklığı

Yığın veri yapısının temel işlemlerinin zaman karmaşıklığı şu şekildedir:

• Push: O(1), yığının en üstüne eleman eklemek sabit zaman alır.
• Pop: O(1), yığından en üstteki elemanı çıkarmak sabit zaman alır.
• Peek: O(1), en üstteki elemanı görmek sabit zaman alır.
• IsEmpty: O(1), yığının boş olup olmadığını kontrol etmek sabit zaman alır.

Yığın Veri Yapısının Avantajları ve Dezavantajları

Avantajlar:

• Basitlik: Yığın veri yapısının çalışma prensibi oldukça basittir ve anlaşılması kolaydır.
• Hızlı Erişim: Yığının en üstündeki elemana erişim, ekleme ve çıkarma işlemleri hızlıdır (O(1) zaman karmaşıklığı).
• Esneklik: Yığınlar, birçok farklı problemde esnek bir şekilde kullanılabilir.

Dezavantajlar:

• Yalnızca Tek Uçtan Erişim: Yığın veri yapısında yalnızca en üstteki elemana erişebilirsiniz, bu da veri yapısına her yerden erişim gereken durumlarda sınırlayıcı olabilir.
• Sabit Kapasite: Sabit kapasiteli bir yığın kullanıyorsanız, yığın dolduğunda daha fazla eleman eklemek mümkün olmayabilir.

Sonuç

Yığın (Stack), son giren ilk çıkar (LIFO) prensibi ile çalışan basit ama güçlü bir veri yapısıdır. Birçok uygulama alanına sahip olan yığınlar, fonksiyon çağrıları, undo/redo işlemleri ve parantez dengesi kontrolü gibi birçok problemde kullanılır. Python’da yığın veri yapısını oluşturmak ve kullanmak oldukça kolaydır ve veri işleme süreçlerinde sıklıkla tercih edilir.