Yığınlara (Stack) Giriş
Yığınlar, sıralı bir veri kümesi içeren veri yapıları olarak tanımlanabilir. Yığınlar, etkileşim için üç yöntem sunmaktadır;
- Push: Verileri yığının üstüne ekler.
- Pop: Verileri yığının en üstünden değer olarak döndürür ve kaldırır.
- Peek: Yığının en üstündeki değeri kaldırmadan döndürür.
Stack, fiziksel bir nesne olarak yığına benzetilir. Bir dizi spor salonu ağırlığını düşünelim. Her plakanın bir ağırlığı yani verisi vardır. Zemine eklediğiniz ilk plaka yığının hem altıdır hem de başka plaka olmadığı için üstüdür. Eklenen her ağırlık yığının yeni tepesi olur. Herhangi bir noktada yığından kaldırabileceğiniz tek ağırlık en üstteki ağırlıktır. Bununla birlikte en üstteki ağırlığı yığından kaldırmadan inceleyebilir ve değerini okuyabilirsiniz. Bıraktığınız son plaka, erişebileceğiniz ilk ve tek plaka olur. Bu duruma “son giren, ilk çıkar” (LIFO: Last In, First Out) denmektedir. Daha az kullanılan bir tabir ise yine aynı anlama gelen “ilk giren, son çıkar” (FILO: First In, Last Out) olarak yorumlanır.
Gif By Codecademy
Yığınların Uygulanması
Yığınlar, bir liste veya diziden daha verimli olduğu için temel veri yapısı olarak bağlantılı liste (linked list) kullanılarak uygulanabilmektedir.
Uygulamaya bağlı olarak, yığının tepesi bağlantılı bir listenin (linked list) baş düğümüne (root veya head) eşdeğerdir. Bir yığın için tanımlanabilecek bir kısıtlama onun boyutudur. Bu, veri yapısının dolu olduğunda yeni veri almasının önüne geçmek içindir. Halihazırda dolu olan bir yığına veri göndermeye çalışmak yığının taşmasına (stack overflow) neden olur. Benzer şekilde, boş bir yığından veri almaya çalışırsanız, bu bir yığının aşağı yönde taşması (stack underflow) olarak yorumlanır.
Python ile Yığınlara Giriş
Yığınların teoride nasıl çalıştığına göz attık şimdi Python ile yığının nasıl kodlanacağına odaklanalım. Yığınların sahip olması gereken üç özellik vardı:
- Push: Verileri yığının üstüne ekler.
- Pop: Verileri yığının en üstünden değer olarak döndürür ve kaldırır.
- Peek: Yığının en üstündeki değeri kaldırmadan döndürür.
Bu yöntemlerin yanı sıra yığının boyutunu göz önünde bulundurmamız gerekir ve bu sınıra göre yöntemlerimizi biraz değiştirmemiz gerekebilir. Böylece yığında taşma durumu (overflow) oluşmaz.
İlk olarak daha önceki kodlarda oluşturulan düğüm (node) kodlarımızı çağırmamız gerekecektir. Kısaca `Node` sınıfımızın kodlarına bakalım ve sonrasında yığın yani `Stack` sınıfımızı tanımlayalım.
class Node:
def __init__(self, value, next_node = None):
self.value = value
self.next_node = next_node
def set_next_node(self, next_node):
self.next_node = next_node
def get_next_node(self):
return self.next_node
def get_value(self):
return self.value
Yığının `push()` ve `pop()` yöntemleri (method) yığına öğe eklemek ve çıkarmak için kullandığımız araçlardır. pop() yöntemi ayrıca yığının üstünden kaldırılan değeri de dönderir. Yalnızca yığının en üstünde değişiklik yapabildiğimizi unutmayalım.
from node import Node
class Stack:
def __init__(self):
self.top_item = None
def peek(self):
return self.top_item.get_value()
Yığınların boyutunun önemli olduğundan bahsetmiştik. Dikkate almazsak yığınımızdaki veriler taşabilir. Herhangi bir yığının taşmasını istemediğimiz için yığın boyutunu izlememize ve sınırlandırmamıza yardımcı olacak yöntemlerimizde birkaç değişiklik yapmamız gerekecektir.
- Yığınımız boşken birisi en üsteki değere bakmak için `peek()` yöntemini çağırırsa veya pop() yöntemi ile boş yığının en üstündeki değeri kaldırmak isterse ne olacak?
- Zaten sınıra ulaşılmış bir yığına bir kişinin `push()` yöntemi ile veri eklemesini nasıl önleyebiliriz?
- Yığının nasıl bir büyüklüğe ulaştığını nasıl kontrol edebileceğiz?
from node import Node
class Stack:
def __init__(self, limit=1000):
self.top_item = None
self.limit = limit
self.size = 0
def push(self, value):
item = Node(value)
item.set_next_node(self.top_item)
self.top_item = item
def pop(self):
if self.size > 0:
item_to_remove = self.top_item
self.top_item = item_to_remove.get_next_node()
self.size-=1
return item_to_remove.get_value()
else:
print("Bu yıgın tamamiyle bos!")
def peek(self):
if self.size > 0:
return self.top_item.get_value()
else:
print("Gosterilecek bir veri yok!")
Yığın sınıfımızı oluşturmuş olabiliriz ancak bazı ince dokunuşlar yapmamız gerekebilir. İlk olarak, yığınımızda daha fazla öğe için yer olup olmadığını kontrol eden bir düzenleme yapmamız gerekir. Sonrasında ise yığının boş olup olmadığını kontrol eden bir yönteme sahip olmak yararlıdır.
from node import Node
class Stack:
def __init__(self, limit = 1000):
self.top_item = None
self.size = 0
self.limit = limit
def push(self, value):
if self.has_space():
item = Node(value)
item.set_next_node(self.top_item)
self.top_item = item
self.size -= 1
else:
print("Yıgında veri eklenecek bosluk kalmadı !")
def pop(self):
if not self.is_empty():
item_to_remove = self.top_item
self.top_item = item_to_remove.get_next_node()
self.size -= 1
return item_to_remove.get_value()
else:
print("Bu yıgın tamamiyle bos!!")
def peek(self):
if not self.is_empty():
return self.top_item.get_value()
else:
print("Goruntulenecek deger yok!")
def has_space(self):
if self.limit > self.size:
return True
def is_empty(self):
if self.size == 0:
return True
Peki şimdi bakalım kodumuz pizza teslimatına karşı nasıl bir yığın oluşturuyor.
# Bos bir pizza yığını tanımlayalım
pizza_stack = Stack(6)
# Sahip olduğumuz pizzaları yığına ekleyelim
pizza_stack.push("pizza #1")
pizza_stack.push("pizza #2")
pizza_stack.push("pizza #3")
pizza_stack.push("pizza #4")
pizza_stack.push("pizza #5")
pizza_stack.push("pizza #6")
# Limit değişkenine değer olarak 6 atadık fazla pizza eklemeye çalışırsak ne olacak görmek için aşağıdaki satırı yorumdan çıkarın.
#pizza_stack.push("pizza #7")
# Yığının tepesinden aşağı doğru pizzaları teslim edelim
print("İlk Teslim Edilen Pizza : " + pizza_stack.peek())
pizza_stack.pop()
pizza_stack.pop()
pizza_stack.pop()
pizza_stack.pop()
pizza_stack.pop()
pizza_stack.pop()
# Tüm pizzalar dağıtılmasına rağmen 'pop()' işlemi yaparsak ne olur görmek için aşağıdaki satırı yorumdan çıkarın.
pizza_stack.pop()
