DSA: Stack Temelleri – Teoriden LeetCode Pratiğine Kapsamlı Rehber

Veri yapıları ve algoritmalar dünyasında yığın (stack), belki de en temel ama aynı zamanda en güçlü araçlardan biridir. Peki, bilgisayarların günlük hayatta karşılaştığımız karmaşık görevleri nasıl yönettiğini hiç merak ettiniz mi? Tarayıcılarınızın geri tuşu nasıl çalışır, metin düzenleyicilerdeki “geri al” (undo) fonksiyonu hangi prensibe dayanır ya da bir programın fonksiyon çağrıları bellekte nasıl organize edilir? Tüm bu soruların cevabı, basit ama etkili bir veri yapısı olan yığında saklıdır. Bu makalede, yığının teorik temellerinden başlayarak, gerçek dünya senaryolarındaki uygulamalarına ve LeetCode gibi platformlardaki problem çözme pratiklerine kadar derinlemesine bir yolculuğa çıkacağız. Kod örnekleri ve adım adım açıklamalarla, yığını sıfırdan öğrenip, algoritmik düşünme becerilerinizi geliştireceksiniz.

Bilgisayar bilimlerinde bir yığın, belirli bir prensibe göre çalışan, soyut bir veri yapısıdır. Tıpkı üst üste dizilmiş tabaklar veya kitaplar gibi düşünebilirsiniz. Yeni bir eleman eklediğinizde her zaman en üste gelirken, bir elemanı çıkarmak istediğinizde ise sadece en üstteki elemanı alabilirsiniz. Bu karakteristik özellik, yığını diğer veri yapılarından ayıran en temel ilkedir: “Son Giren İlk Çıkar” (Last-In, First-Out – LIFO). Yani, yığına en son eklenen eleman, yığından ilk çıkan eleman olacaktır.

Yığının bu LIFO prensibi, birçok gerçek dünya ve programlama senaryosunda kritik bir rol oynar. Örneğin, bir web tarayıcısının geçmişini düşünün. Bir sayfayı ziyaret ettiğinizde, bu sayfa geçmiş yığınına eklenir. “Geri” tuşuna bastığınızda ise, en son ziyaret ettiğiniz sayfa (yani yığının en üstündeki eleman) yüklenir ve yığından çıkarılır. Bu basit mekanizma, karmaşık kullanıcı deneyimlerinin temelini oluşturur. Benzer şekilde, metin düzenleyicilerdeki “geri al” (undo) işlevi de yığın mantığıyla çalışır. Her yaptığınız işlem bir yığına eklenir ve “geri al” dediğinizde en son işlemi geri alırsınız.

Peki, yığın neden bu kadar önemlidir? Öncelikle, karmaşıklığı yönetmeye yardımcı olur. Birçok algoritmik problem, yığının LIFO yapısı sayesinde daha zarif ve verimli bir şekilde çözülebilir. Fonksiyon çağrılarının yönetimi gibi temel bilgisayar operasyonları bile yığın kullanılarak gerçekleştirilir. Bir program bir fonksiyonu çağırdığında, bu fonksiyonun bilgileri (parametreler, yerel değişkenler vb.) bir “çağrı yığınına” (call stack) itilir. Fonksiyon çalışmasını bitirdiğinde ise, bu bilgiler yığından çıkarılır ve kontrol çağıran fonksiyona geri döner. Bu mekanizma, programların düzenli ve öngörülebilir bir şekilde çalışmasını sağlar.

Özellikle algoritmalar ve veri yapıları dünyasına yeni adım atanlar için yığın, öğrenilmesi gereken ilk ve en önemli yapılardan biridir. Anlaması kolay, uygulaması nispeten basit olmakla birlikte, karmaşık problemlerin çözümünde esnek ve güçlü bir araç sunar. Bu temel prensibi kavradığımızda, dinamik programlama, graf algoritmaları ve hatta yapay zeka gibi daha ileri konularda karşımıza çıkacak olan birçok yapının mantığını anlamak çok daha kolay hale gelecektir. Bu nedenle, yığın sadece bir veri yapısı olmaktan öte, programlamanın temel taşlarından biridir ve yazılım geliştirme yolculuğunuzda size sıkça eşlik edecektir.

Yığın Veri Yapısının Anatomisi: LIFO İlkesi ve Temel İşlemler

Her veri yapısının kendine özgü bir çalışma prensibi ve bir dizi temel işlemi vardır. Yığın için bu prensip “Son Giren İlk Çıkar” (LIFO) iken, temel işlemler de yığının doğasına uygun olarak tasarlanmıştır. Bu bölümde, yığının kalbinde yer alan bu işlemleri detaylı bir şekilde inceleyecek ve yığının nasıl çalıştığını daha iyi kavrayacağız.

Push ve Pop İşlemleri Nasıl Çalışır?

Yığının iki ana ve en sık kullanılan işlemi vardır: push ve pop. Bu iki işlem, yığının dinamik yapısını oluşturur ve eleman ekleme ile çıkarma mekanizmasını yönetir.

• Push (Ekleme): Bu işlem, yığına yeni bir eleman eklemek için kullanılır. Her push işleminde, yeni eleman yığının en üstüne konulur. Örneğin, üst üste yığılmış tabakları düşünün; yeni bir tabak her zaman en üste yerleştirilir. Bu işlem genellikle O(1) zaman karmaşıklığına sahiptir, yani yığının boyutundan bağımsız olarak sabit bir sürede gerçekleşir. Çünkü sadece yığının “üst” kısmında bir değişiklik yapılır.
• Pop (Çıkarma): Pop işlemi ise yığının en üstündeki elemanı çıkarmak ve döndürmek için kullanılır. Tabağa geri dönersek, kirli bir tabak almak istediğinizde her zaman en üsttekini alırsınız. Eğer yığın boşsa ve pop işlemi çağrılırsa, bu bir hata (underflow) durumuna yol açar. Pop işlemi de genellikle O(1) zaman karmaşıklığına sahiptir, çünkü sadece en üstteki elemana erişilir ve o eleman kaldırılır.

Bu iki işlemin yanı sıra, yığın veri yapısının etkinliğini ve kullanışlılığını artıran başka yardımcı işlemler de bulunmaktadır:

• Peek (Zirveyi Görme) / Top (Üst): Bu işlem, yığının en üstündeki elemanı çıkarmadan sadece görmemizi sağlar. Yani, yığının durumunu değiştirmeden en son eklenen elemana bakmak için kullanılır. Tıpkı bir tabak yığınının en üstündeki tabağın ne olduğunu anlamak gibi. Bu işlem de O(1) zaman karmaşıklığına sahiptir.
• isEmpty (Boş mu?): Yığının herhangi bir eleman içerip içermediğini kontrol eden bir boolean fonksiyonudur. pop veya peek gibi işlemleri çağırmadan önce yığının boş olup olmadığını kontrol etmek, hataları önlemek için oldukça önemlidir.
• isFull (Dolu mu?): Eğer yığın belirli bir maksimum kapasiteye sahip sabit boyutlu bir veri yapısı olarak uygulanmışsa, isFull işlemi yığının kapasitesine ulaşıp ulaşmadığını kontrol eder. Bu durum genellikle dinamik olarak büyüyebilen yığın uygulamalarında (örneğin Python listeleriyle) geçerli değildir, ancak belleği kısıtlı sistemlerde veya belirli sınırlamalarla çalışıldığında önem kazanır.
• Size (Boyut): Yığındaki toplam eleman sayısını döndürür.

Yığın Nasıl Uygulanır? (Diziler ve Bağlı Listeler)

Yığın soyut bir veri yapısı olduğu için, bilgisayar belleğinde farklı şekillerde uygulanabilir. En yaygın iki uygulama yöntemi diziler (veya dinamik diziler) ve bağlı listelerdir.

Dizi Tabanlı Uygulama:

Yığını bir dizi (array) kullanarak uygulamak oldukça basittir. Dizinin sonunu yığının “üst” kısmı olarak kabul ederiz.

Push işlemi: Dizinin sonuna yeni bir eleman ekleriz (örneğin, Python’da append(), JavaScript’te push()).

Pop işlemi: Dizinin sonundan bir elemanı çıkarırız (örneğin, Python’da pop(), JavaScript’te pop()).

Peek işlemi: Dizinin son elemanına erişiriz (örneğin, my_array[-1]).

Dizi tabanlı yığınlar, elemanlara doğrudan indeksle erişim sağladığı için genellikle hızlıdır. Ancak, sabit boyutlu diziler kullanıldığında kapasite aşımı (overflow) riski taşır. Dinamik diziler (bellek gerektiğinde kendini yeniden boyutlandıran diziler) bu sorunu çözer ancak ara sıra yeniden boyutlandırma maliyeti olabilir.

Bağlı Liste Tabanlı Uygulama:

Bir bağlı liste kullanarak yığın uygulamak da popüler bir yöntemdir. Bu durumda, bağlı listenin başı (head) yığının “üst” kısmını temsil eder.

Push işlemi: Yeni bir düğüm (node) oluşturulur ve listenin başına eklenir. Bu, mevcut head düğümünü yeni düğümün bir sonraki elemanı yapar ve yeni düğüm head olur.

Pop işlemi: Listenin başındaki düğüm kaldırılır ve baş bir sonraki düğüme kaydırılır.

Peek işlemi: Sadece head düğümünün değerine bakılır.

Bağlı liste tabanlı yığınların en büyük avantajı, dinamik boyutlandırma yeteneğidir; yani, yığının boyutu bellek izin verdiği sürece sınırsızca büyüyebilir. Ancak, her eleman için ek bir bellek alanı (pointerlar için) gerektirir ve dizi tabanlı uygulamalara kıyasla elemanlara erişim biraz daha dolaylı olabilir.

Her iki uygulama yöntemi de LIFO prensibini korur ve çoğu durumda O(1) zaman karmaşıklığı sunar. Seçim, genellikle performans gereksinimlerine, bellek kısıtlamalarına ve geliştirme kolaylığına bağlıdır. Python gibi dillerde, yerleşik listeler zaten dinamik diziler olduğu için, yığın uygulamak çok kolay ve verimlidir.

Gerçek Dünya Senaryoları: Yığın Nerede Karşımıza Çıkar? Pratik Kullanım Alanları

Yığın veri yapısı, sadece teorik bir kavram olmanın ötesinde, günlük kullandığımız birçok yazılımın ve sistemin temelinde yatan kritik bir bileşendir. Soyut bir kavram gibi görünse de, yığının LIFO prensibi, karmaşık süreçleri düzenlemek ve yönetmek için inanılmaz derecede esneklik sunar. Gelin, yığının gerçek dünyada nasıl kullanıldığına dair bazı çarpıcı örnekleri ve bir vaka analizini birlikte inceleyelim.

Tarayıcı Geçmişi ve Geri Alma Fonksiyonları: Bir Vaka Analizi

Web Tarayıcıları ve Gezinme Geçmişi: Belki de yığının en bilinen ve en kolay anlaşılır pratik uygulamalarından biri web tarayıcılarımızdır. Herhangi bir web sayfasına gittiğinizde, bu sayfanın URL’si dahili bir yığına (history stack) itilir. “Geri” (back) düğmesine bastığınızda, tarayıcı yığının en üstündeki URL’yi çıkarır ve sizi o sayfaya yönlendirir. “İleri” (forward) düğmesi ise genellikle ayrı bir yığın veya geçici bir depolama mekanizması kullanarak, geri alınan sayfaları tekrar yüklemeye olanak tanır. Bu sayede, internet üzerinde sorunsuz bir şekilde gezinebilir, önceki sayfalara kolayca dönebiliriz. Bu sistemde, her yeni sayfa yüklemesi bir push işlemi iken, geri tuşu bir pop işlemidir.

Metin Düzenleyicilerde “Geri Al” (Undo) ve “Yinele” (Redo): Bir metin düzenleyicide (Microsoft Word, Google Docs, Sublime Text vb.) yazı yazarken, sürekli olarak “geri al” veya “yinele” fonksiyonlarını kullanırız. Bu işlevler de yığın prensibiyle çalışır. Her yaptığınız değişiklik (bir karakter yazmak, bir paragraf silmek, metin formatını değiştirmek) bir “işlem yığınına” (undo stack) kaydedilir. “Geri al” tuşuna bastığınızda, en son yapılan işlem bu yığından çıkarılır ve ilgili değişiklik geri alınır. Geri alınan işlem ise genellikle ayrı bir “yinele yığınına” (redo stack) eklenir. Böylece, “yinele” tuşuna bastığınızda, bu yığından en son geri alınan işlem çıkarılır ve tekrar uygulanır. Bu iki yığın, kullanıcının yaptığı değişiklikleri esnek bir şekilde yönetmesini sağlar.

Bu mekanizma, basit gibi görünse de, kullanıcı deneyimi açısından hayati öneme sahiptir. Kullanıcıya hata yapma özgürlüğü tanır ve karmaşık düzenleme işlemlerinde güvence sağlar. Düşünün ki, yanlışlıkla önemli bir metni sildiniz ve geri alma özelliği olmasaydı. İşte tam da bu noktada yığının gücü ve önemi devreye giriyor.

Fonksiyon Çağrıları Yönetimi (Call Stack): Bilgisayar bilimindeki belki de en temel ve en kritik yığın uygulaması, programların fonksiyon çağrılarını yönetmek için kullandığı “çağrı yığınıdır” (call stack). Bir program çalışırken, bir fonksiyonu çağırdığında, bu fonksiyonun parametreleri, yerel değişkenleri ve dönüş adresi gibi bilgileri çağrı yığınına (push) eklenir. Fonksiyon işini tamamladığında, bu bilgiler yığından çıkarılır (pop) ve kontrol, fonksiyondan önceki konuma geri döner. Bu sayede, programlar iç içe fonksiyon çağrılarını, özyinelemeli (recursive) algoritmaları ve genel program akışını hatasız bir şekilde yönetebilir. Eğer bir program sonsuz bir özyinelemeye girerse, çağrı yığını kapasitesini aşar ve meşhur “stack overflow” hatasını alırsınız. Bu hata, yığının sabit boyutlu olduğu durumlarda kapasite sınırlamalarına işaret eder.

Parantez Eşleştirme ve İfade Değerlendirme: Derleyiciler ve yorumlayıcılar, kodunuzdaki parantezlerin ((), {}, []) doğru bir şekilde eşleşip eşleşmediğini kontrol etmek için yığınları kullanır. Açılan her parantez yığına itilir. Kapanan bir parantez geldiğinde, yığının en üstündeki parantez çıkarılır ve eşleşip eşleşmediği kontrol edilir. Eğer eşleşme varsa devam edilir, yoksa veya yığın boşsa bir hata bildirilir. Benzer şekilde, aritmetik ifadelerin (infix, prefix, postfix) değerlendirilmesinde de yığınlar kritik bir rol oynar. Örneğin, postfix ifadeleri yığın kullanarak kolayca değerlendirilebilir.

Görüldüğü üzere, yığın sadece soyut bir veri yapısı olmaktan çok daha fazlasıdır. Modern yazılım geliştirmenin, kullanıcı deneyiminin ve hatta donanım düzeyindeki operasyonların ayrılmaz bir parçasıdır. Bu pratik örnekler, yığının algoritmik düşünme becerilerimizi nasıl zenginleştirdiğini ve karşılaştığımız problemleri çözmede ne kadar güçlü bir araç olabileceğini açıkça ortaya koymaktadır.

Kendi Yığın Yapımızı Kodlayalım: Adım Adım Python Örnekleri

Teorik bilgileri pekiştirmenin en iyi yolu, öğrendiklerimizi pratiğe dökmektir. Bu bölümde, Python programlama dilini kullanarak kendi yığın (Stack) veri yapımızı adım adım nasıl oluşturacağımızı göreceğiz. Python’ın listeleri, dinamik dizi özellikleriyle yığın implementasyonu için oldukça uygundur ve bize kolaylık sağlar. Kendi sınıfımızı oluşturarak yığının temel işlemlerini (push, pop, peek, isEmpty, size) hayata geçireceğiz.

İlk olarak, Stack adında bir sınıf tanımlayarak başlayabiliriz. Bu sınıfın yapıcı metodunda (constructor) yığın elemanlarını tutacak bir Python listesi (array) başlatacağız. Ardından, yığının temel işlevlerini bu listeyi kullanarak uygulayacağız.

class Stack:
    def __init__(self):
        # Yığın elemanlarını tutacak dahili bir Python listesi kullanıyoruz.
        # Python listeleri dinamik diziler olduğu için boyut yönetimi bizim için otomatik yapılır.
        self.items = []

    def is_empty(self):
        # Yığının boş olup olmadığını kontrol eder.
        # Liste boşsa True, doluysa False döndürür.
        # return len(self.items) == 0 da kullanılabilir.
        return not self.items

    def push(self, item):
        # Yeni bir elemanı yığının en üstüne (listenin sonuna) ekler.
        self.items.append(item)
        print(f"'{item}' yığına eklendi. Yığın: {self.items}")

    def pop(self):
        # Yığının en üstündeki elemanı çıkarır ve döndürür.
        # Eğer yığın boşsa, IndexError fırlatırız (underflow durumu).
        if not self.is_empty():
            removed_item = self.items.pop()
            print(f"'{removed_item}' yığından çıkarıldı. Yığın: {self.items}")
            return removed_item
        else:
            raise IndexError("Yığın boş! Çıkarılacak eleman yok.")

    def peek(self, n=1):
        # Yığının en üstündeki elemanı (veya n'inci elemanı) gösterir, çıkarmadan.
        # n=1 varsayılan olarak en üstteki elemanı gösterir.
        if not self.is_empty():
            if n > 0 and n <= len(self.items):
                # -n indeksi sondan n'inci elemanı verir.
                print(f"Yığının üstünden {n}. eleman: '{self.items[-n]}'")
                return self.items[-n]
            else:
                raise IndexError(f"Geçersiz n değeri veya yeterli eleman yok. Yığın boyutu: {self.size()}")
        else:
            raise IndexError("Yığın boş! Gösterilecek eleman yok.")

    def size(self):
        # Yığındaki eleman sayısını döndürür.
        current_size = len(self.items)
        print(f"Yığının mevcut boyutu: {current_size}")
        return current_size

    def display(self):
        # Yığının mevcut durumunu gösterir.
        if self.is_empty():
            print("Yığın boş.")
        else:
            print(f"Yığın içeriği (üstten alta): {self.items[::-1]}") # Ters çevirerek LIFO sırasını vurguluyoruz

Yukarıdaki kod bloğu, Stack sınıfımızın tüm temel işlevlerini içermektedir. __init__ metodunda self.items = [] ile boş bir liste başlatıyoruz. is_empty metodu, listenin boş olup olmadığını kontrol eder. push metodu, append() fonksiyonu ile listenin sonuna (yığının üstüne) eleman ekler. pop metodu ise pop() fonksiyonu ile listenin sonundaki elemanı çıkarır ve döndürür. peek metodu, listenin son elemanına [-1] indeksi ile erişerek yığının en üst elemanını gösterir. size metodu ise len() fonksiyonu ile liste boyutunu döndürür. display metodu ise yığının o anki durumunu görselleştirmeye yardımcı olur.

Şimdi de bu Stack sınıfını kullanarak nasıl işlemler yapabileceğimize dair bir örnek senaryoya bakalım:

# Bir yığın nesnesi oluşturalım
my_stack = Stack()

# Yığının başlangıç durumunu kontrol edelim
my_stack.is_empty() # Çıktı: Yığının mevcut boyutu: 0, True

# Elemanları yığına ekleyelim (Push işlemleri)
my_stack.push("Kitap A")
my_stack.push("Kitap B")
my_stack.push("Kitap C")

# Yığının mevcut durumunu ve boyutunu kontrol edelim
my_stack.display() # Çıktı: Yığın içeriği (üstten alta): ['Kitap C', 'Kitap B', 'Kitap A']
my_stack.size()    # Çıktı: Yığının mevcut boyutu: 3, 3

# Yığının en üstündeki elemana bakalım (Peek işlemi)
my_stack.peek() # Çıktı: Yığının üstündeki eleman: 'Kitap C', 'Kitap C'
my_stack.peek(2) # Çıktı: Yığının üstünden 2. eleman: 'Kitap B', 'Kitap B'

# Elemanları yığından çıkaralım (Pop işlemleri)
my_stack.pop() # Çıktı: 'Kitap C' yığından çıkarıldı. Yığın: ['Kitap A', 'Kitap B']
my_stack.pop() # Çıktı: 'Kitap B' yığından çıkarıldı. Yığın: ['Kitap A']

# Yığının boş olup olmadığını tekrar kontrol edelim
my_stack.is_empty() # Çıktı: False (çünkü hala 'Kitap A' var)

# Kalan son elemanı da çıkaralım
my_stack.pop() # Çıktı: 'Kitap A' yığından çıkarıldı. Yığın: []

# Şimdi yığın boş olmalı
my_stack.is_empty() # Çıktı: True

# Boş bir yığından pop yapmaya çalışırsak ne olur?
try:
    my_stack.pop()
except IndexError as e:
    print(f"Hata yakalandı: {e}") # Çıktı: Hata yakalandı: Yığın boş! Çıkarılacak eleman yok.

# Boş bir yığından peek yapmaya çalışırsak ne olur?
try:
    my_stack.peek()
except IndexError as e:
    print(f"Hata yakalandı: {e}") # Çıktı: Hata yakalandı: Yığın boş! Gösterilecek eleman yok.

Bu örnekte, my_stack adında bir yığın oluşturduk, çeşitli elemanlar ekledik, yığının durumunu kontrol ettik ve elemanları çıkardık. Ayrıca, boş bir yığın üzerinde pop ve peek yapmaya çalışarak nasıl hata yönetimi yapıldığını da gösterdik. Python'ın yerleşik listeleri sayesinde, bu tür bir veri yapısını uygulamak oldukça sezgisel ve basittir. Ancak bu basitlik, yığının altında yatan temel prensipleri ve LIFO mantığını anlamak için bir engel teşkil etmemelidir. Önemli olan, bu yapıların nasıl çalıştığını ve hangi durumlarda kullanılabileceğini kavramaktır.

LeetCode Pratiği: Yığın Temelli Algoritmalar ve Problemler

Yığının teorik temellerini ve pratik uygulamasını kavradıktan sonra, sıra gerçek dünya problem çözme becerilerinizi geliştirmeye geliyor. LeetCode, HackerRank gibi platformlar, algoritmaları ve veri yapılarını kullanarak problem çözme yeteneğinizi test etmek ve geliştirmek için mükemmel kaynaklardır. Yığın, bu platformlarda karşınıza çıkacak birçok problemin anahtar çözüm mekanizmasıdır. Bu bölümde, yığın ile çözülebilecek tipik LeetCode problemlerine genel bir bakış atacak ve popüler bir örneği detaylandıracağız.

Yığınla çözülen problemler genellikle şu kategorilere ayrılır:

• Parantez Eşleştirme/Doğrulama: Açılış ve kapanış parantezlerinin ((), {}, []) doğru sırada ve eşleşmiş olup olmadığını kontrol etme.
• İfade Değerlendirme: Infix, Prefix veya Postfix gösterimindeki aritmetik veya boolean ifadeleri değerlendirme.
• Geri Alma/İleri Alma İşlevselliği: İşlem geçmişini yönetme.
• Monotonik Yığın (Monotonic Stack): Yığında elemanların artan veya azalan sırada tutulmasını sağlayarak "sonraki daha büyük eleman" (next greater element) gibi problemleri çözme.
• Bellek Yönetimi ve Fonksiyon Çağrıları Simülasyonu: Çağrı yığınını taklit etme.

Geçerli Parantezler Problemi (Valid Parentheses): Yığınla Çözüm

LeetCode'da sıkça karşılaşılan ve yığının gücünü gösteren klasik bir problem "Geçerli Parantezler" (Valid Parentheses) problemidir. Problem şu şekildedir: Bir string S verildiğinde, bu stringin geçerli parantezlerden oluşup oluşmadığını belirleyin. Geçerli bir string şu koşulları sağlamalıdır:

1. Açılan parantezler aynı tipte bir kapanış paranteziyle kapatılmalıdır.
2. Açılan parantezler doğru sırada kapatılmalıdır.
3. Her kapanış parantezinin karşılık gelen bir açılış parantezi olmalıdır.

Örnekler: "()" geçerli, "()[]{}" geçerli, "(]" geçersiz, "([)]" geçersiz.

Yığın Yaklaşımı:

Bu problemi çözmek için bir yığın kullanabiliriz. Mantık oldukça basittir:

1. String üzerinde karakter karakter ilerleriz.
2. Eğer karşılaştığımız karakter bir açılış parantezi ise ('(', '{', '['), bunu yığına push ederiz.
3. Eğer karşılaştığımız karakter bir kapanış parantezi ise (')', '}', ']'), iki durumu kontrol etmeliyiz:
   • Yığın boş mu? Eğer boşsa ve kapanış parantezi bulduysak, bu, karşılık gelen bir açılış parantezi olmadığı anlamına gelir. String geçersizdir.
   • Yığın boş değilse, yığının en üstündeki elemanı pop ederiz. Bu eleman, mevcut kapanış parantezimizle eşleşen açılış parantezi olmalıdır. Eşleşme yoksa (örneğin, ')' için '{' çıktıysa), string geçersizdir.
4. Tüm stringi işledikten sonra, eğer yığın tamamen boşsa, bu, her açılış parantezinin bir kapanış paranteziyle doğru bir şekilde eşleştiği anlamına gelir. String geçerlidir. Eğer yığın boş değilse, bazı açılış parantezleri kapatılmamış demektir ve string geçersizdir.

def is_valid_parentheses(s: str) -> bool:
    stack = [] # Yığınımızı Python listesi olarak kullanıyoruz
    # Parantez eşleşmelerini kolayca kontrol etmek için bir sözlük tanımlıyoruz
    mapping = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in mapping:  # Eğer karakter bir kapanış parantezi ise
            # Yığın boşsa veya yığının en üstündeki eleman kapanış parantezinin eşi değilse
            top_element = stack.pop() if stack else '#' # Yığın boşsa '#' koy ki eşleşme olmasın
            if mapping[char] != top_element:
                return False
        else:  # Eğer karakter bir açılış parantezi ise
            stack.append(char) # Yığına ekle

    # Tüm stringi işledikten sonra yığın boşsa geçerlidir, aksi halde değil
    return not stack

# Test örnekleri
print(f"'()' geçerli mi? {is_valid_parentheses('()')}") # True
print(f"'()[]{{}}' geçerli mi? {is_valid_parentheses('()[]{}')}") # True
print(f"'(]' geçerli mi? {is_valid_parentheses('(]')}") # False
print(f"'([)]' geçerli mi? {is_valid_parentheses('([)]')}") # False
print(f"'{{[]}}' geçerli mi? {is_valid_parentheses('{[()]}}')}") # True
print(f"'' geçerli mi? {is_valid_parentheses('')}") # True
print(f"'[' geçerli mi? {is_valid_parentheses('[')}") # False

Bu kod parçası, "Geçerli Parantezler" problemini yığın kullanarak nasıl çözebileceğinizi adım adım göstermektedir. Bu tür problemler, yığının LIFO prensibini ve basitliğini kullanarak karmaşık görünen senaryoları nasıl çözdüğümüzü anlamak için mükemmel örneklerdir. LeetCode'da benzer birçok problem bulabilir, yığın becerilerinizi daha da geliştirebilirsiniz. Unutmayın, pratik yapmak, algoritmaları ve veri yapılarını ustalaşmanın anahtarıdır.

İleri Düzey İpuçları: Yığın Performansını Optimize Etmek ve Sınır Durumlar

Yığın, temel bir veri yapısı olsa da, performansını optimize etmek ve sınır durumları doğru şekilde ele almak, özellikle büyük ölçekli uygulamalar veya rekabetçi programlama ortamları için hayati önem taşır. Yığının basitliğinin ardında, dikkat edilmesi gereken bazı ince detaylar ve ileri düzey ipuçları bulunur.

Zaman ve Yer Karmaşıklığı Analizi

Bir yığının performansını değerlendirirken, işlemlerin zaman ve yer (bellek) karmaşıklığını anlamak önemlidir. Yığının temel işlemleri olan push, pop ve peek, ideal durumda genellikle O(1) zaman karmaşıklığına sahiptir. Yani, yığının boyutu ne kadar büyük olursa olsun, bu işlemler sabit bir sürede tamamlanır. Bu, yığının birçok uygulama için tercih edilmesinin ana nedenlerinden biridir. Yer karmaşıklığı ise, yığında depolanan eleman sayısı kadar olacaktır, yani O(N), N eleman sayısıdır.

Ancak, bu O(1) durumu, yığının dinamik bir dizi (Python listeleri gibi) olarak uygulandığı ve dizinin yeniden boyutlandırılma ihtiyacı duymadığı sürece geçerlidir. Eğer dizi tabanlı bir yığın kullanıyorsanız ve dizi kapasitesini aşarsanız, sistemin yeni, daha büyük bir dizi oluşturması ve mevcut elemanları bu yeni diziye kopyalaması gerekebilir. Bu yeniden boyutlandırma işlemi, O(N) zaman karmaşıklığına neden olabilir ve bu da işlem süresinde anlık bir yavaşlamaya yol açabilir. Ancak amortize edilmiş (ortalama) zaman karmaşıklığı yine de O(1) olarak kabul edilir, çünkü bu tür yeniden boyutlandırmalar nadiren gerçekleşir.

Sınır Durumları ve Hata Yönetimi

Her veri yapısında olduğu gibi, yığında da sınır durumlar (edge cases) mevcuttur ve bunların doğru şekilde ele alınması gerekmektedir. En yaygın sınır durumları şunlardır:

• Yığın Boşken Pop veya Peek: Yığın boşken bir elemanı çıkarmaya (pop) veya en üstteki elemana bakmaya (peek) çalışmak "underflow" durumuna yol açar. Bu durumda bir hata (örneğin, Python'da IndexError) fırlatmak veya özel bir değer (None, null vb.) döndürmek uygun bir hata yönetimi stratejisidir. Kod örneklerimizde bu durumu IndexError ile yönettik.
• Yığın Doluyken Push (Sabit Boyutlu Yığınlar İçin): Eğer yığın sabit bir boyuta sahip bir diziyle uygulanmışsa ve kapasitesi doluyken yeni bir eleman eklemeye (push) çalışılırsa, bu "overflow" durumuna yol açar. Bu durumda da bir hata fırlatılması veya elemanın eklenemediğini belirten bir dönüş değeri sağlanması gerekir. Dinamik diziler (Python listeleri) bu sorunu otomatik olarak yönettiği için bu durum Python'da doğrudan bir problem yaratmaz, ancak düşük seviyeli dillerde veya belleği kısıtlı ortamlarda kritik bir konudur.
• Tek Elemanlı Yığın: Yığında sadece bir eleman varken pop veya peek işlemleri. Bu durum, yığının boş olma durumuna geçişini doğru bir şekilde yönetmeyi gerektirir.

Optimize Edilmiş Yığın Tasarımları

Bazı özel problem türleri için standart yığın yapısını geliştirmek gerekebilir. Örneğin, "Min Stack" (Minimum Yığın) problemi, yığının en üstündeki elemanı O(1) zaman karmaşıklığıyla döndürmenin yanı sıra, yığındaki en küçük elemanı da O(1) zaman karmaşıklığıyla döndürmesini ister. Bu, genellikle iki yığın kullanarak çözülür: bir ana yığın ve sadece minimum değerleri tutan yardımcı bir yığın. Bu tür optimize edilmiş tasarımlar, problemin gereksinimlerine göre yığın yapısının esnekliğini ve uyarlanabilirliğini gösterir.

Performans ve sınır durumları anlamak, sadece kodunuzun doğru çalışmasını sağlamakla kalmaz, aynı zamanda daha sağlam, güvenilir ve verimli yazılımlar geliştirmenize olanak tanır. Her zaman, belirli bir problem için en uygun veri yapısını ve implementasyonunu seçme konusunda bilinçli kararlar vermeye çalışmalısınız. Bu, geliştirici olarak yetkinliğinizin önemli bir göstergesidir.

Sonuç: Yığının Gücü ve Gelecekteki Adımlarınız

Bu makalede, yığın veri yapısının derinliklerine inerek, temel prensibi olan LIFO'dan (Last-In, First-Out) başlayıp, onu gerçek dünya senaryolarında nasıl kullanıldığına, kendi yığınımızı Python'da nasıl kodlayabileceğimize ve LeetCode gibi platformlardaki problem çözme pratiklerine kadar geniş bir perspektifte inceledik. Yığının sadece soyut bir kavram olmadığını, aksine web tarayıcılarından metin düzenleyicilere, derleyicilerden işletim sistemlerinin bellek yönetimine kadar pek çok alanda kritik bir rol oynayan temel bir yapı taşı olduğunu gördük. Özellikle fonksiyon çağrı yığını örneği, programların dahili işleyişinde ne kadar merkezi bir rol üstlendiğini gözler önüne serdi.

Kendi yığın sınıfımızı oluştururken, push, pop, peek, isEmpty ve size gibi temel işlemlerin nasıl çalıştığını adım adım Python kod örnekleriyle pekiştirdik. Bu pratik uygulama, teorik bilgileri somutlaştırmak ve algoritmik düşünme becerilerinizi geliştirmek için paha biçilmez bir adımdı. Ayrıca, "Geçerli Parantezler" problemi üzerinden yığının problem çözme yeteneğini keşfederken, LeetCode'daki benzer sorunlara nasıl yaklaşmanız gerektiği konusunda bir kılavuz edindiniz.

Unutmayın ki yığın, veri yapıları ve algoritmalar yolculuğunuzda karşılaşacağınız ilk duraklardan sadece biridir. Ancak, bu temel yapıyı sağlam bir şekilde kavramak, kuyruklar (queues), ağaçlar (trees) ve graflar (graphs) gibi daha karmaşık veri yapılarını anlamak için sağlam bir zemin oluşturacaktır. Bu bilgi birikimi, yazılım mühendisliği mülakatlarında başarılı olmanızdan, daha verimli ve optimize edilmiş kodlar yazmanıza kadar pek çok alanda size avantaj sağlayacaktır.

Gelecek adımlarınız için öneriler:

• Farklı dillerde (Java, C++, JavaScript) yığın implementasyonlarını deneyin.
• LeetCode'da yığın kategorisindeki diğer problemleri çözmeye çalışın (örn: Daily Temperatures, Largest Rectangle in Histogram, Min Stack).
• Monotonik yığın kavramını ve uygulamalarını araştırın.
• Özyinelemeli (recursive) algoritmaların çağrı yığını üzerinde nasıl çalıştığını derinlemesine inceleyin.

Bu yolculukta edindiğiniz bilgilerle, yazılım geliştirme dünyasında karşılaştığınız birçok problemi daha akılcı ve verimli bir şekilde çözebileceğinizden eminiz. Başarılar!

Sıkça Sorulan Sorular: Yığın Hakkında Merak Edilenler

Yığın veri yapısı hakkında aklınıza takılabilecek bazı yaygın soruları ve yanıtlarını aşağıda bulabilirsiniz:

• S: Yığın ve Kuyruk arasındaki temel fark nedir?

  C: Yığın (Stack) "Son Giren İlk Çıkar" (LIFO - Last-In, First-Out) prensibiyle çalışır; yani en son eklenen eleman ilk çıkarılır. Kuyruk (Queue) ise "İlk Giren İlk Çıkar" (FIFO - First-In, First-Out) prensibiyle çalışır; yani ilk eklenen eleman ilk çıkarılır.

• S: "Stack Overflow" hatası ne anlama gelir?

  C: "Stack Overflow" hatası, programın çağrı yığınının (call stack) kapasitesini aşması durumunda meydana gelir. Genellikle sonsuz özyinelemeli (recursive) fonksiyon çağrıları veya çok derin fonksiyon çağrı zincirleri sonucunda bellek yetersizliği nedeniyle ortaya çıkar.

• S: Yığın neden O(1) zaman karmaşıklığına sahiptir?

  C: Yığının push, pop ve peek gibi temel işlemleri, elemanların her zaman yığının bir ucundan (üstünden) eklenip çıkarılmasıyla ilgilidir. Bu, yığının boyutundan bağımsız olarak sabit bir sayıda işlem gerektirdiği için O(1) zaman karmaşıklığına sahiptir. Ancak dinamik dizi tabanlı uygulamalarda ara sıra gerçekleşen yeniden boyutlandırma işlemleri geçici olarak O(N) maliyetine neden olabilir, ancak amortize edilmiş maliyet yine de O(1)'dir.

• S: Yığın kullanmadan "geri al" (undo) fonksiyonu uygulanabilir mi?

  C: Teorik olarak başka veri yapıları (örneğin, bir dizi veya bağlı liste) kullanılarak "geri al" işlevi uygulanabilir ancak yığın (LIFO prensibiyle) bu tür bir işlevsellik için en doğal, sezgisel ve verimli veri yapısıdır. Diğer yaklaşımlar genellikle daha karmaşık olur veya aynı performansı sağlamayabilir.

• S: Yığın mobil uygulama geliştirmede nasıl kullanılır?

  C: Mobil uygulamalarda navigasyon akışını yönetmek için sıkça yığın benzeri yapılar kullanılır. Örneğin, bir kullanıcının bir dizi ekran arasında gezinmesi (ekran push, geri tuşu pop), uygulama içi işlemlerin geçmişini yönetmek (undo/redo) ve hatta bazı UI bileşenlerinin durumu gibi senaryolarda yığın mantığından faydalanılır.