Yığın
- İngilizcesi
- Stack
- Türkçe karşılığı
- yığıt
- Okunuşu
- stek
Günlük kullanımda iki ad da yaygın.
Kısaca
Yığın, öğeleri son giren ilk çıkar (LIFO) sırasıyla saklayan bir veri yapısıdır; en son eklenen öğe her zaman ilk çıkarılan öğedir.
Yığın (stack) veri yapısı nedir?
Yığın, öğelerin aynı uçtan, yani tepeden (top) eklendiği ve çıkarıldığı bir koleksiyondur. Öğe eklemeye push, tepedeki öğeyi çıkarmaya pop, tepedeki öğeye onu çıkarmadan bakmaya ise peek denir. Bu kural LIFO olarak bilinir: last in, first out (son giren ilk çıkar).
Klasik benzetme bir tabak yığınıdır. Temiz tabakları üste koyar ve tabakları üstten alırsınız; yani en son eklediğiniz tabak ilk kullandığınızdır. Yığın genellikle dinamik bir dizi ya da bağlı liste üzerine kurulur ve push, pop ve peek işlemlerinin hepsi O(1) sürer. Dinamik dizide push amortize O(1)'dir; yani dizinin ara sıra büyümesi gerekse de ortalamada O(1) demektir.
Yığınlar programlamanın her yerinde karşımıza çıkar. Bir editörün geri al özelliği son değişikliklerin bir yığınını tutar, ayrıştırıcılar parantezlerin dengeli olup olmadığını denetlemek için yığın kullanır ve derinlik öncelikli arama nereye geri döneceğini hatırlamak için yığın kullanır. Hangi fonksiyonun hangisini çağırdığını izleyen çağrı yığını (call stack) de bir yığındır: her fonksiyon çağrısı bir çerçeveyi push eder, her dönüş onu pop eder ve kontrolsüz özyineleme bu alan tükendiğinde stack overflow ile sonuçlanır.
Yığın sıklıkla kuyrukla karşılaştırılır. Yığın en yeni öğeyi önce çıkarırken (LIFO) kuyruk en eski öğeyi önce çıkarır (FIFO, first in, first out). Çağrı yığınının bulunduğu bellek bölgesi olan stack belleği, aynı son giren ilk çıkar biçiminde büyüyüp küçüldüğü için adını bu veri yapısından alır.
Bir bakışta
Önemli noktalar
- Yığın LIFO sırasını izler: son giren ilk çıkar.
- Temel işlemler push, pop ve peek'tir ve her biri O(1) sürer.
- Python'da
listileappend()vepop()yığın olarak çalışır; JavaScript'tepush()vepop()içeren bir dizi de öyle. - Fonksiyon çağrılarını izleyen çağrı yığını gerçek bir yığındır; derin özyinelemenin stack overflow'a yol açabilmesinin nedeni budur.
- Yığın en yeni öğeyi önce çıkarır; kuyruk en eskiyi.
Örnek
def is_balanced(text):
# Push every opening bracket; each closing bracket must match the top
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for char in text:
if char in "([{":
stack.append(char) # push: O(1)
elif char in pairs:
if not stack or stack.pop() != pairs[char]: # pop: O(1)
return False
return not stack # balanced only if nothing is left open
print(is_balanced("{[()]}")) # True
print(is_balanced("([)]")) # FalseSık sorulan sorular
Yığın ile kuyruk arasındaki fark nedir?
Yığın, bir tabak destesi gibi en son eklenen öğeyi önce çıkarır (LIFO). Kuyruk ise bir bilet gişesindeki sıra gibi en uzun süre bekleyen öğeyi çıkarır (FIFO).
Stack overflow nedir?
Stack overflow, çağrı yığınının yerinin tükenmesidir; genellikle özyinelemeli bir fonksiyonun bir temel duruma ulaşmadan kendini çağırmaya devam etmesinden kaynaklanır. Program bu durumda çöker ya da Python'da RecursionError, JavaScript'te RangeError: Maximum call stack size exceeded gibi bir hata verir.
JavaScript'te yığın nasıl uygulanır?
Düz bir dizi kullanın: push() tepeye ekler, pop() tepeden çıkarır ve arr.at(-1) tepedeki öğeye bakar. Hem push() hem de pop() O(1) sürede çalışır.
Sık karşılaştırılanlar
İlgili sayfalar
- KuyrukVeri Yapıları, s. 24Kuyruk, öğeleri ilk giren ilk çıkar (FIFO) sırasıyla saklayan bir veri yapısıdır; en uzun süre bekleyen öğe her zaman çıkarılacak sonraki öğedir.
- Bağlı ListeVeri Yapıları, s. 4Bağlı liste, öğeleri ayrı düğümlerde saklayan bir veri yapısıdır; her düğüm bir değer ile zincirdeki sonraki düğüme bir referans tutar.
- DiziProgramlamanın Temelleri, s. 15Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.
- ÖzyinelemeProgramlamanın Temelleri, s. 42Özyineleme, bir fonksiyonun sorunu, basit bir temel duruma ulaşana dek aynı sorunun daha küçük sürümleri için kendisini çağırarak çözdüğü tekniktir.
- FonksiyonProgramlamanın Temelleri, s. 20Fonksiyon, belirli bir işi yapan, isteğe bağlı olarak parametre denen girdiler alıp sonuç döndürebilen, adlandırılmış ve yeniden kullanılabilir kod bloğudur.
- ÇizgeVeri Yapıları, s. 8Çizge, kenarlarla bağlı düğümlerden (köşelerden) oluşan ve yollar, arkadaşlıklar ve bağımlılıklar gibi ilişkileri modellemekte kullanılan bir veri yapısıdır.
- Stack Belleğiİşletim Sistemleri, s. 29Stack belleği, bir thread'in fonksiyonlarının yerel değişkenlerini ve dönüş adreslerini tuttuğu bölgedir; her çağrıda büyür, dönüşte otomatik olarak küçülür.
- DequeVeri Yapıları, s. 10Deque, hem önden hem arkadan sabit sürede öğe eklemeye ve çıkarmaya izin veren çift uçlu bir kuyruktur; hem yığın hem kuyruk gibi davranabilir.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin