Yığın (stack) veri modeli

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

Bu hafta yığını bir sınıf yazarak değil, Python’ın mevcut koleksiyonlarını kullanarak inceleyeceğiz. Amaç class Stack üretmek değil, LIFO davranışını anlamak ve uygun problemde kullanmaktır.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

  • LIFO ilkesini açıklayabilmeli,
  • push, pop ve peek işlemlerini yığın bağlamında yorumlayabilmeli,
  • 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ı ve DFS kavramlarının yığınla ilişkisini tanıma düzeyinde 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 düşünülür:

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

#| edit: false
#| completion: false
stack = []

stack.append("A")
stack.append("B")
stack.append("C")

print("Yığın:", stack)
print("Üstte:", stack[-1])
print("Çıkan:", stack.pop())
print("Kalan:", stack)

Burada listenin sonunu yığının üstü olarak kullanıyoruz. Bu seçim önemlidir; listenin sonuna append() ve sondan pop() kullanmak doğaldır.

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

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

#| edit: false
#| completion: false
stack = []
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)

x = stack.pop()
print(x, stack)

stack.append(40)
print(stack)

Yığın problemlerinde ara durumları çizmek, hataları yalnızca son çıktıya bakmaktan daha kolay ortaya çıkarır.

5 Boş yığından çıkarma

#| edit: false
#| completion: false
stack = []

try:
    print(stack.pop())
except IndexError as error:
    print(type(error).__name__ + ":", error)

Bu yüzden çıkarma yapmadan önce boşluk durumunu düşünmeliyiz:

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

6 Uygulama: geri alma geçmişi

Bir metin alanındaki durumları yığında tutabiliriz:

#| edit: false
#| completion: false
history = []
text = ""

history.append(text)
text = "Merhaba"

history.append(text)
text = "Merhaba dünya"

history.append(text)
text = "Merhaba dünya!"

print("Şimdiki:", text)
text = history.pop()
print("Undo 1:", text)
text = history.pop()
print("Undo 2:", text)

Gerçek bir editör bundan çok daha karmaşık olabilir; fakat temel fikir aynıdır: geçmiş durumları LIFO sırasıyla geri alırız.

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.

#| edit: false
#| completion: false
def balanced_parentheses(text):
    stack = []

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

    return not stack

print(balanced_parentheses("(a+b)*(c-d)"))
print(balanced_parentheses("(a+b*(c-d)"))
print(balanced_parentheses("a+b)"))

İki farklı hata olasılığı vardır:

  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 yalnızca [ ve ] karakterlerinin dengeli olup olmadığını döndürecek biçimde tamamlayın.

#| exercise: hafta05-brackets
#| completion: false
#| persist: true
def balanced_brackets(text):
    stack = []

    for char in text:
        # Burayı tamamlayın.
        pass

    return not stack

print(balanced_brackets("[a[b]c]"))
#| exercise: hafta05-brackets
#| check: true
scope = {}
try:
    exec(user_code, scope)
    fn = scope.get("balanced_brackets")
    correct = (
        callable(fn)
        and fn("[a[b]c]") is True
        and fn("[[a]") is False
        and fn("a]") is False
        and fn("") is True
    )
except Exception:
    correct = False

feedback = (
    {"correct": True, "message": "Köşeli parantez denetimi doğru çalışıyor."}
    if correct
    else {"correct": False, "message": "'[' geldiğinde ekleyin; ']' geldiğinde önce yığının boş olup olmadığını kontrol edin."}
)
feedback

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

Solution. 

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 yalnızca sayıları eşleştirmek yetmez; kapanan türün son açılan türle eşleşmesi gerekir. Yığın burada sırayı korur:

#| edit: false
#| completion: false
def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    opening = set(pairs.values())
    stack = []

    for char in text:
        if char in opening:
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False

    return not stack

for sample in ["([])", "([)]", "{a+[b*c]}", "(("]:
    print(sample, balanced(sample))

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

Fonksiyonlar birbirini çağırdığında Python, hangi fonksiyona geri döneceğini ve yerel bilgileri takip etmek 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. Ayrıntılı çalışma zamanı uygulaması bu dersin kapsamında değildir, fakat son çağrılan fonksiyonun önce tamamlanması LIFO davranışını açıklar.

11 Kavram köşesi: DFS

Graf ve ağaçlarda kullanılan Depth-First Search (DFS) yaklaşımı da yığın fikriyle ilişkilidir. DFS’nin ayrıntılı graf uygulamasını bu derste yapmayacağız. Şimdilik şu bağlantıyı bilmeniz yeterlidir:

DFS, gidilebildiği kadar derine ilerleyip geri dönme davranışını yığınla gerçekleştirebilir.

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 davranışı ister ve bir sonraki haftanın konusu olan kuyruk daha uygundur.

13 Bölüm özeti

  • Yığın LIFO ilkesine göre çalışır.
  • Python listesinde append() ve sondan pop() ile yığın davranışı elde edilebilir.
  • Boş yığından çıkarma sınır durumudur.
  • Parantez denetimi ve undo geçmişi doğal yığın problemleridir.
  • Çağrı yığını ve DFS, yığın fikrinin başka bağlamlardaki örnekleridir.
  • Veri yapısı seçimi, işlemlerin hangi sırada gerçekleşmesi 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 iki farklı başarısızlık durumu nedir?
  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