Yığın (Stack)

#Nasıl çalışır?

Yığın (stack), elemanların üst üste konduğu bir veri yapısıdır; bir tabak yığını gibi düşünebilirsin. Yeni eleman her zaman en üste konur ve yalnızca en üstteki elemana erişilebilir.

Bu kurala LIFO (Last In, First Out: son giren ilk çıkar) denir. En son eklenen eleman, ilk çıkarılan eleman olur.

Yığınlar bir dizi ya da bağlı liste ile kolayca gerçeklenir. Dizide yalnızca "top" adında bir sayaç tutmak yeterlidir.

#Kendin dene

#Temel işlemler

push(x)

x değerini en üste ekler.

pop()

En üstteki elemanı çıkarır ve döndürür. Yığın boşsa hata verir (underflow).

peek() / top()

En üstteki elemanı çıkarmadan okur.

isEmpty()

Yığında eleman olup olmadığını söyler.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

class Stack:
    def __init__(self) -> None:
        self._items: list[int] = []  # the top of the stack is the end of the list

    def push(self, value: int) -> None:
        self._items.append(value)

    def pop(self) -> int:
        if not self._items:
            raise IndexError("stack is empty")
        return self._items.pop()

    def peek(self) -> int:
        if not self._items:
            raise IndexError("stack is empty")
        return self._items[-1]

    def __len__(self) -> int:
        return len(self._items)


s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())   # 3: last in, first out
print(s.peek())  # 2
print(len(s))    # 2

#Karmaşıklık

Tüm temel işlemler yalnızca en üstteki elemana dokunduğu için sabit sürede çalışır. Ortadaki bir elemana ulaşmak isterseniz üsttekileri tek tek çıkarmanız gerekir; yığın bu iş için tasarlanmamıştır.

#Ne zaman kullanılır?

Fonksiyon çağrıları (call stack), geri al (undo) özelliği, tarayıcının geri tuşu, parantez eşleştirme, ifadelerin hesaplanması ve derinlik öncelikli arama (DFS) yığın kullanır. "En son yapılanı ilk geri al" mantığı gereken her yerde aklına yığın gelmeli.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Derinlik Öncelikli Arama (DFS)
• Çift Uçlu Kuyruk (Deque)
• Graf (Graph)