Ana içeriğe geç

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

LIFO ilkelerini, Python’da listeler, deque ve LifoDeque kullanarak yığınların nasıl uygulanacağını öğrenin ve bunları geri al/yeniden yap sistemleri veya grafik gezinimi için uygulayın.
· 15 dk. oku

Yapay Zeka ile Keşfedin

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.

python stack LIFO principle

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.

python stack vs list vs queue

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.

python stack
operations: Push, pop, peek

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:

İşlem

Zaman Karmaşıklığı

Notlar

Push

O(1)

Sabit zaman. Python listeleri için küçültülmüş ortalama O(1)

Pop

O(1)

Sabit zaman

Peek

O(1)

Üst öğeye doğrudan erişim

Arama

O(n)

Tüm öğeler taranmalı

Alan

O(n)

Saklanan öğe sayısıyla doğrusal

Ö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:

Özellik

list

collections.deque

queue.LifoQueue

İthalat gerekli

Hayır

Evet (collections)

Evet (queue)

Push yöntemi

.append()

.append()

.put()

Pop yöntemi

.pop()

.pop()

.get()

Peek yöntemi

stack[-1]

stack[-1]

Güvenli yöntem yok

Boş hata durumu

IndexError

IndexError

Bloklar veya Empty

Push/Pop hızı

Küçültülmüş ortalama O(1)

Gerçek O(1)

Kilit ek yüküyle O(1)

İş parçacığı güvenliği

Hayır

Hayır

Evet

En iyisi

Basit betikler, prototipleme

Algoritmalar, performans kritik kod

Çok iş parçacıklı üretici-tüketici

İş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