Python Yığını: LIFO Veri Yapılarının Uygulanması

Her hatayı geri almak için Ctrl+Z’ye bastığınızda, tarayıcınızdaki geri düğmesine tıkladığınızda ya da özyinelemeli bir fonksiyonun sonuçlarını çözmesini izlediğinizde, bir yığına güvenirsiniz. Günlük kullandığınız yazılımlarda o kadar derine yerleşmişlerdir ki, çoğu zaman farkında bile olmadan Yığınlarla etkileşime girersiniz.

Bu yazıda, bir yığının ne olduğunu, yığınların temel mantığını inceleyecek, Python’un yerleşik kütüphanelerini kullanarak farklı uygulama stratejilerini karşılaştıracak ve bunları algoritmik problemleri çözmek için uygulayacağız.

Veri yapıları bilginizi performansla ilgili en iyi uygulamalarla eşleştirmek için şu Verimli Python Kodu Yazma kursumuzu almanızı ve hızlı başvuru için Python Temelleri Cheat Sheet’ini elinizin altında bulundurmanızı öneririm. 

Python’da Yığın (Stack) Nedir?

Koda bakmadan önce, Python yığınını bu kadar güçlü bir araç yapan kavramsal temeli anlamak önemlidir. Yığınların arkasındaki temel ilkeye bir göz atalım ve diğer yaygın veri yapılarından nasıl ayrıldıklarını görelim.

LIFO veri yapısı

Yığın, Son Giren İlk Çıkar (LIFO) ilkesini izleyen doğrusal bir veri yapısıdır. Bu, en son eklenen öğenin her zaman ilk çıkarılan olduğu anlamına gelir. Bunu, bir yemekhane tepsi yığını gibi düşünün. Yeni tabakları üste koyarsınız ve her zaman en üstteki tabağı ilk alırsınız. Ortadan ya da alttan tabak çekmezsiniz. Erişim tamamen tepe (üst) ile sınırlıdır.

Bu tek kısıt, yalnızca tepeye erişim, yığınlara öngörülebilirlik ve verimlilik kazandırır. Her öğe aynı uçtan girer ve çıkar; bu da işlemleri basit ve hızlı tutar.

Erken belirtmeye değer bir nokta, Python’un bazı diğer dillerde olduğu gibi özel, ilkel bir yığın türüyle gelmemesidir. Bir stack anahtar sözcüğü veya yerleşik bir sınıf yoktur. Bunun yerine Python, bir yığın gibi davranabilen sağlam yerleşik alternatifler sunar; örnek olarak listeler, collections.deque ve queue.LifoQueue. Bu uygulamaların her birine yazının ilerleyen kısımlarında ayrıntılı olarak bakacağız.

Yığın ve Diğer Veri Yapıları

Bir yığının ne olduğunu anlamak, ne olmadığını gördüğünüzde çok daha netleşir. Yığınlarla en sık karşılaştırılan iki yapı, kuyruklar ve standart Python listeleridir.

Yığın vs kuyruk

Kuyruk, yığının tam tersi olan İlk Giren İlk Çıkar (FIFO) ilkesini izler. Kuyrukta, öğeler arkaya eklenir ve önden çıkarılır; tıpkı gişe önünde sıra bekleyen insanlar gibi. Yığınlar da kuyruklar da doğrusaldır ve her ikisi de öğelere nasıl erişileceğini kısıtlar; ancak bunu zıt yönlerde yaparlar. 

Yanlış olanı seçmek, bir algoritmanın mantığını sessizce bozabilir. Örneğin, bir derinlik öncelikli aramada yığını kuyruk ile değiştirmek onu genişlik öncelikli aramaya dönüştürür ve tamamen farklı sonuçlar üretir.

Yığın vs liste

Öte yandan, standart bir Python listesi rastgele erişim sağlar. my_list[3] veya my_list.insert(2, value) gibi işlemlerle herhangi bir indekste öğe okuyabilir, ekleyebilir ya da silebilirsiniz. Bu esneklik pek çok bağlamda kullanışlıdır; ancak yapının ortasındaki öğelere kazara erişmenizi veya onları değiştirmenizi engelleyen bir şey olmadığı anlamına da gelir. 

Geri izleme, söz dizimi ayrıştırma veya geri alma işlevi gibi katı LIFO sıralamasına bağlı bir algoritma uyguladığınızda, bir listenin kısıtlanmamış doğası ince hatalara yol açabilir.

İşte tam da bu nedenle yığının kısıtlı erişim deseni bir sınırlama değil, bir özelliktir. Yalnızca en üst öğeyle etkileşime izin vererek, bir Python yığını tasarım gereği doğruluğu uygular. Yanlış uçtan yanlışlıkla çıkarma yapamaz ya da yapının derinlerine gömülü bir öğenin üzerine yazamazsınız. 

Algoritma tasarımında bu tür kısıtlar, mantığınızı temiz ve kodunuzu öngörülebilir tutan şeylerdir.

Temel Yığın İşlemleri ve Zaman Karmaşıklığı

Artık bir Python yığınının ne olduğunu ve diğer yapılardan nasıl farklılaştığını anladığımıza göre, her yığının desteklediği temel işlemlere bakalım ve her birinin ne kadar verimli çalıştığını analiz edelim.

Standart yığın işlemleri

Her yığın uygulaması, programlama dilinden bağımsız olarak küçük bir standart işlem kümesine dayanır. Yığınla çalıştığınız her seferde kullanacağınız yapı taşları bunlardır.

Push, yığının tepesine bir öğe ekler. Yığın [A, B] içeriyorsa ve C’yi iterseniz, yığın [A, B, C] olur ve C artık üsttedir.

Pop, şu anda üstte bulunan öğeyi kaldırır ve döndürür. Yukarıdaki örneğe devam edersek, [A, B, C]’den çıkarma C’yi döndürür ve yığını [A, B] olarak bırakır.

Peek (bazen top/top-of-stack de denir), üstteki öğeyi kaldırmadan görmenizi sağlar. Mantığınız, çıkarmaya karar vermeden önce mevcut üst değeri incelemeyi gerektiriyorsa kullanışlıdır; bu desen, ifade ayrıştırma ve dengeli parantez problemlerinde sık görülür.

Bu üç temel işlemin yanı sıra, güvenli ve hatasız yığın kodu yazmak için iki yardımcı yöntem önemlidir:

• is_empty(), yığında herhangi bir öğe olup olmadığını kontrol eder. Boş bir yığında pop veya peek çağırmak yaygın bir çalışma zamanı hata kaynağıdır; bu nedenle önce boşluğu kontrol etmek, erken edinmeniz gereken bir savunmacı programlama alışkanlığıdır.

• size(), yığındaki geçerli öğe sayısını döndürür. Bir özyinelemenin ne kadar derine gittiğini veya kaç öğenin hâlâ işlenmesi gerektiğini takip etmeniz gerektiğinde faydalıdır.

Son olarak, ders kitaplarında ve mülakatlarda karşınıza çıkacak bir terimi tanımlamak gerekir: Yığın Taşması (Stack Underflow). Boş bir yığından pop veya peek yapmaya çalıştığınızda ortaya çıkan hata durumudur. Kaldıracak veya görüntüleyecek bir şey yoktur; bu nedenle işlem geçersizdir. 

Bunun ürettiği kesin istisna veya davranış, uygulamaya bağlıdır. Bir sonraki bölümde list, deque ve LifoQueue’ya bakarken Python’un bunu somut olarak nasıl ele aldığını göreceğiz.

Karmaşıklık analizi

Yığınların algoritmalarda bu kadar yaygın kullanılmasının en büyük nedenlerinden biri verimlilikleridir. Her işlemin zaman ve alan karmaşıklığını parçalayalım.

Push O(1)’dir. Verimli bir yığın uygulamasında, tepeye bir öğe eklemek sabit zamanlı bir işlemdir. Yığın, mevcut öğeleri kaydırmak veya yeniden düzenlemek zorunda değildir. Yeni öğeyi yalnızca sona yerleştirir. Bu, hem collections.deque hem de küçültülmüş ortalama durumda Python’un yerleşik list’i için geçerlidir.

Pop O(1)’dir. Üstteki öğeyi kaldırmak da aynı derecede hızlıdır. Yığın, son konuma doğrudan erişir, değeri döndürür ve içsel boyut sayacını azaltır. Yine, diğer öğelerin kaydırılması gerekmez.

Peek O(1)’dir. Üstteki öğeyi kaldırmadan görüntülemek de doğrudan indeks aramasıdır; bu da sabit zamanlıdır.

Arama O(n)’dir. Yığınlar, kasıtlı bir ödünleşimi burada açığa çıkarır. Yığının bir yerinde belirli bir değerin olup olmadığını bulmanız gerekiyorsa, üstten alta tüm n öğeleri taramaktan başka seçeneğiniz yoktur. 

Yığınlar, keyfi aramalar için tasarlanmamıştır. Hızlı ve öngörülebilir push/pop karşılığında arama yeteneğinden feragat ederler. Kullanım durumunuz sık aramalar gerektiriyorsa, küme (set) veya sözlük (dictionary) gibi başka bir veri yapısı daha uygundur.

Alan karmaşıklığı O(n)’dir. n öğe tutan bir yığın, n ile orantılı bellek gerektirir. Öğelerin kendilerini depolamak için gerekenlerin ötesinde gizli bir ek yük yoktur; yapının iç defter tutma işlemleri için küçük bir sabit dışında.

Kısa bir özet burada:

Önemli çıkarım şudur: Bir Python yığını, tek uçtan hızlı ekleme ve kaldırma için optimize edilmiştir. Onu, sıralı LIFO erişimi yönetmek gibi tasarlandığı amaç için kullandığınız sürece mükemmel performans verir. Kendinizi düzenli olarak bir yığın içinde arama yaparken bulduğunuz anda, veri yapısı seçiminizi yeniden gözden geçirmeniz gerektiğine dair bir işarettir.

Python Yığın Uygulamaları

Teori ve karmaşıklık analizini geride bıraktığımıza göre artık gerçek kod yazma zamanı. Python, her birinin kendi güçlü ve zayıf yönleri olan üç temel yığın uygulama yolu sunar. Üçünü de adım adım inceleyelim ve kullanım durumumuza hangisinin uyduğuna nasıl karar vereceğimizi görelim.

Yerleşik liste ile Python yığını

Python yığını oluşturmanın en basit yolu yerleşik list ile başlamaktır. Listeler, sondan öğe ekleme ve çıkarma destekleyen dinamik diziler olduğundan, yığın davranışına doğal olarak uyarlar. 

.append() yöntemi push görevi görür ve argümansız .pop() son öğeyi kaldırıp döndürür. Bunu aşağıdaki kod örneğiyle görelim:

# Creating a stack using a Python list
stack = []

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)

# Pop the top element
top = stack.pop()
print(top)
print(stack)

# Peek at the top element
print(stack[-1])

[10, 20, 30]
30
[10, 20]
20

Bu iyi çalışır; ancak boş yığın durumunu dikkatle ele almanız gerekir. Python’da hem .pop() hem de stack[-1], liste boşken bir IndexError yükseltir. Bu, daha önce tanımladığımız Yığın Taşması durumunu Python’un yüzeye çıkarma biçimidir. 

En iyi uygulama, bu çağrıları bir try/except bloğuna sarmak veya tepeye erişmeden önce boşluğu kontrol etmektir; örneğin aşağıdaki gibi:

# Handling Stack Underflow with try/except
stack = []

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty stack")

try:
    top = stack[-1]
except IndexError:
    print("Stack Underflow: cannot peek at an empty stack")

# Alternatively, check before accessing
if stack:
    top = stack.pop()
else:
    print("Stack is empty")

Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is empty

Anlaşılması gereken bir performans nüansı vardır. Python listeleri dinamik dizilerle desteklenir. .append() çağrısı genellikle anlık O(1)’dir. Ancak, dahili dizi önceden ayrılan alanı tükendiğinde, Python yeni, daha büyük bir bellek bloğu ayırmak ve tüm mevcut öğeleri oraya kopyalamak zorundadır. 

Bu ara sıra yeniden ayırma, .append()’i katı bir O(1) yerine küçültülmüş ortalama O(1) yapar. Pratikte gecikme nadir ve kısadır; ancak gecikmeye duyarlı veya gerçek zamanlı uygulamalarda bu öngörülemezlik önemli olabilir.

Bu uyarıya rağmen, bir listedeki .append() ve .pop() çoğu basit yığın görevi için tercih edilen yaklaşımdır. Sıfır ithalat gereksinimi, tanıdık sözdizimi ve geniş geliştirici aşinalığı; özellikle betikler, prototipleme ve sadeliğin önemli olduğu mülakat problemleri için onu iyi bir varsayılan seçim yapar.

collections.deque ile Python yığına

Ara sıra yeniden ayırma gecikmesi olmadan tutarlı O(1) performansa ihtiyacınız varsa, collections.deque önerilen yükseltmedir. Adı “çift uçlu kuyruk” anlamına gelir; ancak yüksek performanslı bir Python yığını olarak mükemmel çalışır. Önceki örneğimiz, deque sözdizimiyle şöyle görünür:

from collections import deque

# Creating a stack using deque
stack = deque()

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) 

# Pop the top element
top = stack.pop()
print(top)
print(stack)
 
# Peek at the top element
print(stack[-1])

deque([10, 20, 30])
30
deque([10, 20])
20

Arayüzün liste tabanlı yaklaşımla özdeş olduğuna dikkat edin. .append(), .pop() ve [-1] aynı şekilde çalışır. Boş erişimdeki IndexError davranışı da değişmez; dolayısıyla hata yakalama kodunuzda bir değişiklik yapmanız gerekmez:

from collections import deque

stack = deque()

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty deque stack")

Stack Underflow: cannot pop from an empty deque stack

Kritik fark, kaputun altındadır. Bir deque, tek bir dizi yerine sabit boyutlu bloklardan oluşan çift bağlı bir liste olarak uygulanır. Bu, büyüdüğünde tüm yapıyı yeniden ayırıp kopyalaması gerekmediği anlamına gelir. 

Her .append() ve .pop() gerçek, garantili O(1) işlemdir; küçültülmüş ortalama değil, tutarlıdır. Binlerce ya da milyonlarca kez push/pop yaptığınız algoritma ağırlıklı çalışmalarda bu tutarlılık birikir.

queue.LifoQueue ile Python yığını

Python’un standart kütüphanesi ayrıca özellikle çok iş parçacıklı programlar için tasarlanmış bir yığın uygulaması olan queue.LifoQueue’yu içerir. Adındaki “LIFO”, Son Giren İlk Çıkar sıralamasını takip ettiğini doğrular; ancak arayüz ve davranış, önceki iki yaklaşımdan oldukça farklıdır. Bunu bir kod örneğiyle görelim:

from queue import LifoQueue

# Creating a thread-safe stack
stack = LifoQueue()

# Push elements using .put()
stack.put(10)
stack.put(20)
stack.put(30)
print(stack.qsize())

# Pop the top element using .get()
top = stack.get()
print(top)
print(stack.qsize())

3
30
2

İlk fark edeceğiniz şey sözdizimi değişikliğidir. Push .put(), pop .get() olur. Bu isimlendirme, bir iş parçacığının öğeleri “koyduğu”, başka bir iş parçacığının ise “aldığı” queue modülünün üretici-tüketici tasarım deseninden gelir.

Farkında olmanız gereken iki önemli davranışsal fark vardır. 

Birincisi, LifoQueue’nun güvenli bir peek yöntemi yoktur. Üst öğeyi kaldırmadan görüntülemenin yerleşik bir yolu yoktur. İç özniteliklere erişebilirsiniz; ancak çok iş parçacıklı bir bağlamda bunu yapmak, iş parçacığı güvenli bir sınıf kullanmanın amacını boşa çıkarır ve yarış durumları riski taşır.

İkincisi, LifoQueue boş bir yığından öğe almaya çalıştığınızda IndexError yükseltmez. Varsayılan olarak .get() bloklar. Çağıran iş parçacığını duraklatır ve bir başka iş parçacığı yığına bir öğe koyana kadar süresiz bekler. Engellemesiz davranış isterseniz, block=False geçebilirsiniz; bu da bunun yerine bir queue.Empty istisnası yükseltir. Bunu bir örnekle görelim:

from queue import LifoQueue, Empty

stack = LifoQueue()

# Non-blocking get raises Empty, not IndexError
try:
    stack.get(block=False)
except Empty:
    print("Stack is empty — no items to get")

Stack is empty — no items to get

LifoQueue’yu iş parçacığı güvenli kılan dahili kilitleme mekanizması nedeniyle, işlemleri list veya deque’ye kıyasla daha fazla ek yüke sahiptir. Bu, onu tek iş parçacıklı kod için kötü bir seçim yapar. LifoQueue’yu yalnızca aynı anda veri üreten ve tüketen birden çok iş parçacığınız olduğunda kullanın; diğer tüm durumlarda deque veya list’e yönelin.

Python’da doğru yığın uygulamasını seçme

Üç seçenek varken, kararınızı yönlendirmek için yan yana bir karşılaştırma:

İşte en iyi uygulamayı seçmek için karar çerçevem:

• list’i, betikler, not defterleri ve mülakat tahtaları gibi ithalat gerektirmeyen hızlı bir yığına ihtiyaç duyduğunuzda kullanın. 

• collections.deque’yi algoritmik kod yazarken, büyük veri kümelerini işlerken veya performansın önemli olduğu her şeyi inşa ederken kullanın. 

• queue.LifoQueue’yu yalnızca eşzamanlı erişimli doğal bir çok iş parçacıklı senaryonuz olduğunda kullanın.

Sıfırdan, her düğümün bir değer ve altındaki düğüme bir işaretçi tuttuğu özel bir bağlı liste sınıfı kullanarak bir Python yığını uygulayan eğitimlere de rastlayabilirsiniz. Bana göre, bu kesinlikle yığınların dahili olarak nasıl çalıştığını ve bellek başvurularının nasıl zincirlendiğini derinleştirebilecek değerli bir eğitim egzersizidir. 

Ancak, üretim Python kodunda, tek tek düğüm nesneleri oluşturmanın ek yükü nedeniyle bağlı liste yığını çoğu zaman bir deque’den daha yavaştır. Gerçek dünya Python işleri için collections.deque hız, açıklık ve güvenilirliğin en iyi birleşimini sunar.

Python Yığınının Uygulamaları

Bir Python yığınının nasıl uygulanacağını anlamak resmin yalnızca yarısıdır. Yığınların gerçek değeri, LIFO sıralaması olmadan çok daha karmaşık olacak problemleri çözdüklerini gördüğünüzde ortaya çıkar. Kodlama mülakatlarında, yazılım sistemlerinde ve algoritma tasarımında sürekli karşımıza çıkan üç klasik uygulamaya bakalım.

Dengeli parantezleri kontrol etme

Dengeli parantezler problemi, teknik mülakatlarda en sık sorulan yığın sorularından biridir. (), [] ve {} gibi parantezler içeren bir dize verildiğinde, her açma parantezinin doğru sırada karşılık gelen bir kapama parantezi olup olmadığını belirlemeniz gerekir.

Mantık bir yığına mükemmel şekilde uyar. Dizeyi soldan sağa tararken, her açma parantezini yığına itersiniz. Bir kapama paranteziyle karşılaştığınızda, yığının tepesinden çıkarır ve eşleşip eşleşmediğini kontrol edersiniz.

Çıkarmaya çalıştığınızda yığın boşsa ya da çıkarılan parantez eşleşmiyorsa, dize dengesizdir. Tüm diziyi işledikten sonra yığın boş olmalıdır. Artık kalan açma parantezleri, bir şeylerin hiç kapanmadığı anlamına gelir. Bunu uygulamada görelim:

from collections import deque

def is_balanced(expression):
    stack = deque()
    matching = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack:
                return False  # closing bracket with nothing to match
            if stack.pop() != matching[char]:
                return False  # mismatched pair
    
    return len(stack) == 0  # stack should be empty if balanced

# Test cases
print(is_balanced("([])")) 
print(is_balanced("{[()]}"))
print(is_balanced("([)]"))
print(is_balanced("(("))
print(is_balanced(""))

True
True
False
False
True

"{[()]}" ifadesini yığının çalışmasını görmek için adım adım izleyelim:

Yazının sonunda yığın boştur; dolayısıyla ifade dengelidir.

Aynı mantık, mülakat problemlerinin çok ötesine uzanır. Derleyiciler ve yorumlayıcılar, kaynak koddaki her açma etiketinin, parantezin veya ayırıcının uygun bir eşleşmesi olduğundan emin olmak için bunu kullanır. 

Python’da SyntaxError: unexpected EOF iletisini gördüyseniz, bu denetimin bir türünü iş başında görmüşsünüzdür. HTML doğrulayıcıları, JSON ayrıştırıcıları ve yapılandırma dosyası denetleyicileri bile bu yığın tabanlı yaklaşımın varyasyonlarına dayanır.

Derinlik öncelikli arama (DFS) uygulama

Derinlik öncelikli arama, temel grafik dolaşım algoritmalarından biridir ve onu çalıştıran veri yapısı yığındır. Fikir basittir. Bir düğümde başlayın, bir dal boyunca olabildiğince ileri gidin, sonra bir sonrakini denemek için geri izleyin. Bir Python yığınının LIFO doğası, bu “önce derine git” davranışının doğal olarak ortaya çıkmasını sağlar.

Çoğu giriş dersi DFS’yi, çağrı yığınının dolaşım sırasını örtük olarak yönettiği özyineleme ile öğretir. Ancak özyinelemeli yaklaşımın pratik bir sınırlaması vardır. Python’un varsayılan özyineleme sınırı 1.000 framedir. 

Büyük veya derin iç içe geçmiş grafiklerde bu, bir RecursionError ile sonuçlanır. Açık yığın kullanan yinelemeli sürüm, bu sorundan kaçınır ve dolaşım üzerinde tam kontrol sağlar.

Bir kod örneği görelim. Aşağıdaki grafikte DFS yapacağız:

from collections import deque

def dfs_iterative(graph, start):
    visited = set()
    stack = deque()
    stack.append(start)
    traversal_order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            # Push neighbors onto the stack
            # Reverse to maintain left-to-right order after LIFO popping
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return traversal_order

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(dfs_iterative(graph, 'A'))

['A', 'B', 'D', 'E', 'F', 'C']

Yığının dolaşımı nasıl yönettiğini görmek için yürütmeyi izleyelim:

Dikkat edin; LIFO sıralaması, algoritmanın A → B → D ve A → B → E → F dallarını tamamen keşfetmesini, C’yi ziyaret etmek için geri izlemeye başlamadan önce zorunlu kılar. Bu, kuyruğun kullanıldığı ve mevcut derinlikteki tüm komşuları keşfettikten sonra daha derine inen genişlik öncelikli aramadan onu ayıran şeydir. 

Burada gösterilen yinelemeli DFS deseni, ağaçlar, yönlendirilmiş ve yönlendirilmemiş grafikler için çalışır. Ayrıca topolojik sıralama, döngü tespiti ve labirent/bulmaca çözme gibi daha gelişmiş algoritmaların temelidir.

Geri al/yeniden yap işlemlerini yönetme

Bir metin düzenleyici, çizim uygulaması veya e-tabloda hiç düşünmeden geri al ve yeniden yap kullandıysanız, bunun altındaki çalışma mantığına güvenmişsinizdir. Mekanizma zariftir ve tam olarak iki yığın üzerinde çalışır.

Bir geri alma yığını, kullanıcı değişiklik yaptıkça her eylemi veya durumu saklar. Kullanıcı geri al tetiklediğinde, geçerli durum geri alma yığından çıkarılır ve yeniden yap yığınına itilir.

Kullanıcı ardından yeniden yap tetiklerse, durum yeniden yap yığından çıkarılır ve geri alma yığınına geri itilir. Kullanıcı geri aldıktan sonra tamamen yeni bir değişiklik yaparsa, yeniden yap yığını temizlenir. Yeni bir eylem tarafından üzeri yazılan bir şeyi yeniden yapamazsınız. Bunu bir kod örneğiyle görelim:

from collections import deque

class TextEditor:
    def __init__(self):
        self.content = ""
        self.undo_stack = deque()
        self.redo_stack = deque()

    def type_text(self, text):
        """Record current state and apply new text."""
        self.undo_stack.append(self.content)
        self.content += text
        self.redo_stack.clear()  # new action invalidates redo history

    def undo(self):
        """Revert to the previous state."""
        if not self.undo_stack:
            print("Nothing to undo")
            return
        self.redo_stack.append(self.content)
        self.content = self.undo_stack.pop()

    def redo(self):
        """Re-apply the last undone action."""
        if not self.redo_stack:
            print("Nothing to redo")
            return
        self.undo_stack.append(self.content)
        self.content = self.redo_stack.pop()

    def show(self):
        print(f'Content: "{self.content}"')

# Demonstrate the undo/redo flow
editor = TextEditor()
editor.type_text("Hello")
editor.show()                

editor.type_text(" World")
editor.show()                

editor.type_text("!")
editor.show()              

editor.undo()
editor.show()           

editor.undo()
editor.show()           

editor.redo()
editor.show()

editor.type_text(" Python")
editor.show()         

editor.redo()  

Content: "Hello"
Content: "Hello World"
Content: "Hello World!"
Content: "Hello World"
Content: "Hello"
Content: "Hello World"
Content: "Hello World Python"
Nothing to redo

İki yığın arasındaki durum akışı net bir deseni izler:

Bu iki yığın deseni, metin editörleriyle sınırlı değildir. Kullanıcıların değişiklikler dizisinde ileri geri gidebilmesi gereken her yerde (ki bu neredeyse her yerdir) karşımıza çıkar:

• Görüntü düzenleme yazılımları
• Veritabanı işlem geri almaları
• Oyun durumu yönetimi

Altta yatan ilke her zaman aynıdır. Bir Python yığını geçmişi, diğeri geleceği izler ve LIFO sıralaması, her zaman en son duruma ilk döndüğünüzü garanti eder.

Python Yığında İleri Konular

Yığınlar, çalıştırdığınız her Python programının yüzeyinin altında da önemli bir rol oynar ve belirli sorunların zaman karmaşıklığını dramatik biçimde azaltabilen optimizasyon tekniklerini güçlendirir. Her iki ileri boyuta da bakalım.

Çağrı yığınını anlamak

Python’da bir fonksiyonu her çağırdığınızda, doğrudan kontrol etmediğiniz sahne arkasında bir şey olur. Python, çağrı yığını olarak bilinen dahili bir veri yapısına yeni bir çerçeve (frame) iter. Bu çerçeve, fonksiyonun yerel değişkenlerini, parametrelerini ve çağrıyı başlatan kod satırına geri işaretçiyi tutar. 

Fonksiyon yürütmeyi tamamladığında, çerçevesi çağrı yığından çıkarılır ve kontrol çağırana döner.

Bunu basit bir örnekle gerçekten inceleyebilirsiniz:

def function_c():
    print("Inside function_c")
    # At this point, the call stack holds:
    # [main → function_a → function_b → function_c]  (top)

def function_b():
    print("Inside function_b")
    function_c()

def function_a():
    print("Inside function_a")
    function_b()

function_a()

Inside function_a
Inside function_b
Inside function_c

function_c çalıştığında, çağrı yığınında üst üste yığılmış dört çerçeve vardır. Her fonksiyon tamamlandıkça çerçevesi LIFO sırasıyla çıkarılır. Önce function_c, sonra function_b, ardından function_a ve sonunda ana modül kapsamı biter.

Özyinelemeyi çalıştıran mekanizma tam olarak budur. Her özyinelemeli çağrı, kendi yerel değişkenlerine sahip yeni bir çerçeve iter ve sonuçlar çerçeveler çıkarıldıkça çözülür. Bunu bir örnekle görelim:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

# Call stack at deepest point:
# factorial(1)  ← top (returns 1)
# factorial(2)  ← waiting for factorial(1)
# factorial(3)  ← waiting for factorial(2)
# factorial(4)  ← waiting for factorial(3)
# factorial(5)  ← waiting for factorial(4)

120

Sorun, özyineleme çok derine indiğinde ortaya çıkar. Python, çağrı yığınının mevcut tüm belleği tüketmesini önlemek için varsayılan 1.000 çerçevelik bir özyineleme sınırı belirler. Özyinelemeli fonksiyonunuz bu sınırı aşarsa, Python bir RecursionError yükseltir. Bunu bir örnekle görelim:

def infinite_recursion(n):
    return infinite_recursion(n + 1)

try:
    infinite_recursion(0)
except RecursionError:
    print("RecursionError: maximum recursion depth exceeded")

RecursionError: maximum recursion depth exceeded

Bu sınırı sys modülünü kullanarak kontrol edebilir ve değiştirebilirsiniz; ancak artırmayı dikkatle yapmak gerekir:

import sys

print(sys.getrecursionlimit())  
sys.setrecursionlimit(5000)     # Increase with caution

5000

Aklınızda tutmanız gereken önemli ayrım şudur: çağrı yığını, Python yorumlayıcısı tarafından yönetilen sistem düzeyinde bir yapıdır. Ona doğrudan push veya pop yapamazsınız. Önceki bölümlerde oluşturduğumuz list, deque ve LifoQueue yığınları ise programınızın heap belleğinde yaşayan kullanıcı tanımlı veri yapılarıdır. Farklı amaçlara hizmet ederler; ancak her ikisi de aynı LIFO ilkesini takip eder.

Monotonik yığınların kullanımı

Monotonik yığın, öğelerin azalmayan ya da artmayan düzende (veya probleme bağlı olarak bazen kesin artan/azalan) korunduğu özel bir varyasyondur. Yeni bir öğe ittiğinizde, sıralama kısıtını ihlal edecek tüm öğeleri önce çıkarırsınız. Bu, tüm bir optimizasyon problem sınıfını doğrusal sürede çözmenin anahtarıdır.

Klasik örnek, Bir Sonraki Daha Büyük Öğeyi Bulma problemidir: Bir tamsayı dizisi verildiğinde, her öğe için sağında ondan daha büyük olan ilk öğeyi bulun. İç içe döngüler kullanan kaba kuvvet yaklaşımı O(n²) çalışır. Her öğe için sağındaki her şeyi tararsınız. Monotonik yığın bunu O(n) ile çözer.

Sezgi şudur: Diziyi sağdan sola dolaşırsınız ve azalan bir yığın tutarsınız. Her öğe için, ondan küçük veya ona eşit olan her şeyi yığından çıkarırsınız. Bu değerler, soldaki gelecekteki herhangi bir öğe için artık “bir sonraki daha büyük öğe” olamaz. 

Çıkarma işleminden sonra yığının tepesinde kalan ne varsa, mevcut öğe için yanıttır. Sonra mevcut öğeyi yığına itersiniz. Bunu bir kod örneğiyle görelim. Burada -1, ilgili sayının sağında daha büyük bir öğe olmadığı anlamına gelir:

from collections import deque

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # default: no greater element found
    stack = deque()     # monotonic decreasing stack (stores values)

    # Traverse from right to left
    for i in range(n - 1, -1, -1):
        # Pop elements that are not greater than current
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        
        # If stack is not empty, top is the next greater element
        if stack:
            result[i] = stack[-1]
        
        # Push current element onto the stack
        stack.append(nums[i])

    return result

nums = [4, 5, 2, 25, 7, 18]
print(next_greater_element(nums))

[5, 25, 25, -1, 18, -1]

Monotonik özelliğin nasıl korunduğunu görmek için yürütmeyi izleyelim:

Dikkat edin, her öğe tam olarak bir kez yığına itilir ve tüm dolaşım boyunca en fazla bir kez çıkarılır. Bu nedenle, iç zaman karmaşıklığının O(n) olmasının nedeni budur; içte bir while döngüsü olsa bile. Tüm yinelemeler boyunca push ve pop işlemlerinin kümülatif sayısı asla 2n’yi aşmaz.

Daha önce belirttiğim gibi, monotonik yığın deseniyle O(n²)’den O(n)’e hızlandırılan çok sayıda benzer problem vardır. Bunlardan bazıları:

• Hisse senedi aralığı problemi: Her günün fiyatı için, daha düşük veya eşit fiyata sahip kaç ardışık önceki gün olduğunu bulun.
• Histogramda en büyük dikdörtgen: Bir çubuk grafiğin altında sığabilecek en büyük dikdörtgensel alanı bulun (klasik zor seviye mülakat sorunu).
• Günlük sıcaklıklar: Günlük sıcaklıklardan oluşan bir dizi verildiğinde, daha sıcak bir gün için kaç gün beklemeniz gerektiğini bulun.
• Yağmur suyu biriktirme: Farklı yüksekliklerdeki çubuklar arasında biriken yağmur suyunun miktarını hesaplayın.

Her durumda, temel fikir aynıdır: monotonik kısıt, gelecekteki sonuçları artık etkileyemeyecek öğeleri elerken, arama uzayını kareselden doğrusal düzeye indirir.

Sonuç

Yığın, her programcının öğrendiği ilk veri yapılarından biridir ve ironik biçimde Son Giren İlk Çıkar doğasının tam tersi olarak, yeni kullanım alanları keşfetmeyi en geç bıraktıklarından biridir. 

Bu yazıda, bu LIFO kısıtının; iç içe parantezleri doğrulamaktan, derinlik öncelikli aramaları yönlendirmeye; geri al/yeniden yap durumunu yönetmekten, monotonik yığınlarla dizi problemlerini optimize etmeye kadar birçok farklı senaryoda nasıl faydalı olabileceğini gördük. 

Tek bir öneri alınacaksa o da şu olur: özel bir nedeniniz olmadıkça, Python yığın uygulamanız için varsayılan olarak collections.deque kullanın. 

Bir sonraki adım olarak, şu kursumuzu almanızı öneririm: Python’da Veri Yapıları ve Algoritmalar.