Yığın (stack) veri modeli

Bazı problemlerde en son eklenen öğenin ilk çıkarılması gerekir. Tarayıcıdaki geri düğmesi, metin düzenleyicideki geri alma (undo) ve iç içe parantezlerin denetlenmesi bu davranışa örnektir. Bu veri modeline yığın (stack) denir.

Bu hafta yığın için sınıf yazmayacağız; Python listesini yığın gibi kullanacağız. Hedefimiz LIFO (son giren ilk çıkar) davranışını anlamak ve bu davranışı gerektiren problemlerde yığın kullanabilmek.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

  • LIFO ilkesini açıklayabilmeli,
  • Yığında push, pop ve peek işlemlerinin ne yaptığını açıklayabilmeli,
  • Python listesiyle basit bir yığın kullanabilmeli,
  • Boş yığından çıkarma hatasını önleyebilmeli,
  • Parantez denetimi ve geri alma geçmişi gibi problemlerde yığını kullanabilmeli,
  • Çağrı yığınının ve DFS’nin yığınla ilişkisini ana hatlarıyla açıklayabilmelisiniz.

2 LIFO: son giren ilk çıkar

LIFO (Last In, First Out), en son eklenen öğenin ilk çıkarılması anlamına gelir.

flowchart TB
    T["Üst"] --> C["C - en son eklendi"]
    C --> B["B"]
    B --> A["A - ilk eklendi"]

Bir yığında genellikle şu işlemler bulunur:

Soyut işlem Anlamı Python listesiyle
push(x) üste eleman ekle stack.append(x)
pop() üstteki elemanı çıkar stack.pop()
peek() üsttekine bak stack[-1]
is_empty() boş mu? len(stack) == 0 veya not stack

3 Python listesiyle yığın

Burada listenin sonunu yığının üstü olarak kullanıyoruz. Bunun bir nedeni var: 2. haftada gördüğümüz gibi listenin sonuna append() ile eklemek ve sondan pop() ile çıkarmak ucuzdur, listenin başında ise aynı işler O(n) tutar.

4 Yığın durumunu adım adım izleme

Aşağıdaki kodun her satırından sonra yığının durumunu tahmin edin:

Yığın problemlerinde ara durumları çizerseniz hataları, yalnızca son çıktıya baktığınızdan daha kolay yakalarsınız.

5 Boş yığından çıkarma

Bu yüzden çıkarmadan önce yığının boş olup olmadığına bakmalıyız:

if stack:
    item = stack.pop()
else:
    print("Yığın boş")

6 Uygulama: geri alma geçmişi

Bir metin kutusundaki yazının önceki hâllerini yığında tutabiliriz:

Gerçek bir metin düzenleyici bundan çok daha karmaşık olabilir, ama fikir aynı: önceki hâllere LIFO sırasıyla, en yeniden başlayarak döneriz.

7 Uygulama: parantez denetimi

Şu ifadeleri düşünün:

(a + b) * (c - d)      ✓
(a + b * (c - d)       ✗

Açılan her ( karakterini yığına ekleyebilir, kapanan ) geldiğinde bir açılışı çıkarabiliriz.

İfade iki şekilde dengesiz çıkabilir:

  1. Kapanış geldiğinde yığın boş olabilir,
  2. Metin bittiğinde yığında kapanmamış açılış kalabilir.

8 Alıştırma: köşeli parantezleri denetle

Aşağıdaki fonksiyonu tamamlayın. Fonksiyon yalnızca [ ve ] karakterlerine baksın; bunlar dengeliyse True, değilse False döndürsün.

[ için append, ] için önce if not stack: return False, sonra pop() kullanın.

def balanced_brackets(text):
    stack = []

    for char in text:
        if char == "[":
            stack.append(char)
        elif char == "]":
            if not stack:
                return False
            stack.pop()

    return not stack

9 Birden çok parantez türü

(, [, { karakterlerini birlikte denetlerken kaç parantez açılıp kaç parantez kapandığını saymak yetmez. Her kapanış, en son açılan parantezle aynı türden olmalı. ([)] ifadesinde sayılar tutar ama sıra yanlıştır. Yığın bu sırayı tutar:

10 Çağrı yığını sezgisi

Bir fonksiyon başka bir fonksiyonu çağırdığında Python, çağrılan fonksiyon bitince nereye döneceğini ve her fonksiyonun yerel değişkenlerini saklamak zorundadır. Bunu çağrı yığını (call stack) fikriyle düşünebiliriz:

main()
  └─ calculate()
       └─ validate()

validate() bittiğinde kontrol calculate() fonksiyonuna; o da bittiğinde main() fonksiyonuna döner. Python’ın bunu program çalışırken nasıl yaptığına bu derste girmiyoruz. Ama son çağrılan fonksiyonun önce bitmesi bir LIFO davranışıdır.

11 Kavram köşesi: DFS

Derinlik öncelikli arama (depth-first search, DFS) da yığın fikriyle ilişkilidir. DFS, graf ve ağaç gibi birbirine bağlı düğümlerden oluşan yapılarda arama yapmanın bir yoludur. Ayrıntılı graf uygulamasını bu derste yapmayacağız. Şimdilik şu bağlantıyı bilmeniz yeter:

DFS bir yoldan gidebildiği kadar derine iner, ilerleyemeyince geri döner. Geri dönülecek yerleri bir yığında tutabilir.

12 Yığın ne zaman uygun değildir?

İlk gelen işin önce işlenmesi gereken bir müşteri sırası düşünün. Yığın kullanırsak yeni gelen müşteri daha önce gelenlerin önüne geçer. Bu problem FIFO (First In, First Out, ilk giren ilk çıkar) davranışı ister; bunun için gelecek haftanın konusu olan kuyruk daha uygundur.

13 Bölüm özeti

  • Yığın LIFO ilkesine göre çalışır.
  • Python listesini append() ve sondan pop() ile yığın gibi kullanabiliriz.
  • Boş yığından çıkarma bir uç durumdur (edge case); çıkarmadan önce yığının boş olup olmadığına bakın.
  • Parantez denetimi ve geri alma geçmişi tipik yığın problemleridir.
  • Çağrı yığını ve DFS de yığın fikrini kullanır.
  • Hangi veri yapısını seçeceğimiz, elemanların hangi sırayla çıkması gerektiğine bağlıdır.

14 Kendinizi kontrol edin

  1. LIFO ne demektir?
  2. Neden listenin sonunu yığının üstü olarak kullanıyoruz?
  3. Parantez denetiminde bir ifade hangi iki şekilde dengesiz çıkar?
  4. Undo geçmişi neden kuyruk değil yığın davranışı ister?
  5. Çağrı yığını ile LIFO arasındaki ilişki nedir?
Back to top