Yığınlar ve Kuyruklar

Genel Bakış

Yığınlar ve kuyruklar, bilgisayar biliminde öğeleri ekleyip kaldırabileceğin sırayı belirten yaygın veri yapılarıdır. Bunları verilerle etkileşimde bulunma sıranı kontrol etmek için kullanabilirsin:

• Yığın: Okumak için bir kitap yığınının en üstündeki kitabı almak gibi, öğeleri ilk giren son çıkar (FILO) düzenine göre yerleştirip çıkardığın bir kapsayıcıdır.

• Sıra: Yemek bekleyen müşteri sırasının işleyişi gibi, öğeleri ilk giren ilk çıkar (FIFO) düzenine göre ekleyip çıkardığın bir kapsayıcıdır.

Yığın ve kuyrukların temeldeki kodları benzer olsa da, ikisinin de deneyimini hızlı, verimli ve sezgisel hale getirmek için kullanabileceğin önemli farkları ve güçlü yönleri vardır.

Yığınlar

Bir yığını bir gözleme yığını gibi düşünebilirsin. Bir kahvaltıcıda olduğunu ve garsonun sana sonsuz sayıda gözleme verdiğini varsayalım. Nezaket gereği, her seferinde yalnızca bir tane ve yalnızca yığının en üstündeki gözlemeyi alacaksın. Garsondan yığının en üstüne yeni bir tane gözleme itmesini (push) isteyebilirsin ve acıktığında yığının en üstünden bir gözleme çıkarabilir (pop) ve onu yemek üzere tabağına koyabilirsin. Yığının ortasındaki belirli bir gözlemeyi yemek istiyorsan onu alana kadar üstten gözleme yemeye devam etmek zorundasın. Eklenen ilk gözleme, aldığın son gözleme olacaktır. Bu, yığının FILO veya ilk giren son çıkar veri yapısında olduğu anlamına gelir.

Ne Zaman Kullanılır

Yığınlar, geriye doğru izlemeye, yani olayları hangi sırayla yaptığını hatırlama yeteneğine ihtiyacın olduğunda kullanışlıdır. Bu bir geri alma fonksiyonu, bir olaylar zinciri veya bir seçenekler dizisi olabilir. Örneğin, yolların dallar halinde ayrıldığı bir labirenti çözmesi gereken bir robotun olabilir. Robot labirentte bir ayrıma geldiğinde bir yol seçer ve bu seçeneği yığının üzerine iter. Bir çıkmaza girdiğinde, yığında geriye doğru gider ve gidebileceği yeni bir yol bulana kadar seçenekleri yığından çıkarır.

Verse’te Uygulama

Verse API’sinde yerleşik bir yığın uygulaması yoktur ancak bunu kendin oluşturabilirsin.

Bir yığındaki öğeleri dizi veya bağlantılı liste gibi herhangi bir sıralı veri yapısını kullanarak temsil edebilirsin. Bu örnekte, yığının en üstüne kolayca erişmeni sağladığı için dizi kullanacaksın.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Elements dizisi, yığında t türündeki objeleri depolar. Bu, bir yığını int, float, stack vb. gibi herhangi bir öğe türüyle başlatabileceğin anlamına gelir. Yığın sınıfı için bağımsız değişken olarak type (tür) kullanılması, [parametrik türün](parametric-types-in-verse) bir örneğini oluşturur.

Şimdi birkaç yardımcı fonksiyonu tanımlayalım. Öğeleri Push() çağrısıyla yığına itmek ve Pop() çağrısıyla yığından çıkarmak için yığının üst kısmının nerede olduğunu bilmen gerekir. Bunun içinse şu üç fonksiyona ihtiyacın var: Size(), IsEmpty() ve Peek().

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

Size() fonksiyonu yalnızca Elements dizisinin Length değerini döndürür. IsEmpty() fonksiyonu, Size() fonksiyonunu çağırır ve <transacts> belirleyicisine sahiptir, yani Size() değeri 0’a eşit değilse başarısız olur.

Peek() fonksiyonu, elements dizisinin en üst (Uzunluk - 1) dizinindeki öğeyi döndürür. Dizi boşsa diziye erişim başarısız olabileceğinden, bu fonksiyon <decides><transacts> belirleyicilerine sahiptir.

Bir yığın başlatmak için bir oluşturucu fonksiyon kullanabilirsin. Oluşturucu, ilişkili olduğu sınıfın bir örneğini oluşturan özel bir fonksiyondur. Oluşturucu, bir objenin başlangıç değerlerini ayarlar ve Elements değerine erişerek bunu bir başlangıç öğe dizisine atamana olanak sağlar.

# Creates and returns a stack from an initial array of elements InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

İtme ve Çıkarma

Yığına öğe eklemek ve çıkarmak için ya yeni öğeyi yığının en üstüne itmen (push) veya en üstten öğeyi çıkarman (pop) gerekir.

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

Push() fonksiyonu, yığının en üstüne koymak istediğin öğeyi alır ve bu öğenin üstte olduğu yeni bir yığın döndürür. Mevcut yığını değiştirmek yerine yeni bir yığın döndürmek bir işlevsel programlama örneğidir ve yan etki riskini azaltır.

Pop() fonksiyonunu uygulamak için önce yığının üstündeki öğeyi Peek() fonksiyonunu kullanarak bulman gerekir. Ardından, üstteki öğeyi (RemoveElement[] fonksiyonunu kullanarak) çıkarman ve ayrıca bu öğenin yer almadığı yeni bir yığın döndürmen gerekir. Yeni yığını ve çıkarılan öğeyi eşzamanlı olarak döndürebilmek için demet kullanabilirsin. Dizi erişimi için ifadeler ve Peek() fonksiyonu çağrısı başarısız olabilir nitelikte olduğundan, Pop() fonksiyonu <decides><transacts> belirleyicilerini içermek zorundadır.

Tam Kod

Yığın sınıfı için tam kod aşağıda yer alıyor.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

Kuyruklar

Bir kuyruğu suşi taşıyan bir bant gibi düşünebilirsin. Bir suşi restoranında olduğunu ve sana taşıma bandında her seferinde bir tabak suşi gönderdiklerini, tabakların sipariş sırasına göre geldiğini varsayalım. Sıranın önündeki tabağı alıp yemek için kuyruktan kaldırabilirsin ancak bir seferinde yalnızca bir tabak alabilirsin. Yeni bir tabak sipariş etmek istediğinde şeften bir tabağı sıranın en sonuna olmak üzere kuyruğa eklemesini istersin. Kuyrukta zaten başka suşi tabakları varsa sondaki tabağa ulaşana kadar kuyruğun ön tarafındaki tabakları alıp yemeye devam etmen gerekir. Eklenen ilk suşi tabağı, aldığın ilk tabak olacaktır. Bu, kuyruğun FIFO yani ilk giren ilk çıkar veri yapısında olduğu anlamına gelir.

Ne Zaman Kullanılır

Kuyruklar, verileri geldikleri zamana göre işlemen gerektiğinde kullanışlıdır. Bu, bir arabaya servis restoranında müşterilere servis yapmak, çağrı merkezinde aramaları sıralamak veya bir mülakatta oyuncuya bir dizi soru sormak olabilir. Örneğin, her seferinde bir görevi yerine getirirken veya bir deneyimden geçen oyuncular için bekleme odası oluşturmak istiyorsan oyuncuları ilk gelen ilk alır ilkesi temelinde geliş zamanına göre sıralamak için kuyruğu kullanabilirsin.

Verse’te Uygulama

Verse API’sinde yerleşik bir kuyruk uygulaması yoktur ancak bunu kendin oluşturabilirsin.

Yığınlarda olduğu gibi, kuyruktaki öğeleri dizi veya bağlantılı liste gibi herhangi bir sıralı veri yapısını kullanarak temsil edebilirsin. Bu örnekte, kuyruğun hem başına hem de sonuna kolayca erişmeni sağladığı için dizi kullanacaksın. Bağlantılı liste kullanan bir kuyruk uygulaması için bu kod parçacığına göz at.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Elements dizisi, kuyrukta t türündeki objeleri depolar. Bu, bir kuyruğu int, float, queue vb. gibi herhangi bir öğe türüyle başlatabileceğin anlamına gelir. Yığın sınıfı için bağımsız değişken olarak type (tür) kullanılması, [parametrik türün](parametric-types-in-verse) bir örneğini oluşturur.

Yığınlarda olduğu gibi kuyruklar da birkaç yardımcı fonksiyona ihtiyaç duyar. Enqueue() ve Dequeue() işlemlerini gerçekleştirebilmek için kuyruğun önünün ve arkasının nerede olduğunu bilmen gerekir. Ayrıca kuyruğun boyutunu ve boş olup olmadığını bilmek de yararlı olacaktır. Bunları şu dört fonksiyonla tanımlarsın: Size(), IsEmpty(), Front() ve Back().

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

Size() fonksiyonu Elements dizisinin Length değerini döndürür. IsEmpty() fonksiyonu, Size() fonksiyonunu çağırır ve <transacts> belirleyicisine sahiptir, yani Size() değeri 0’a eşit değilse başarısız olur.

Front() ve Rear() fonksiyonları, elements dizisinin ön (dizin 0) ve arka (Uzunluk - 1) dizinindeki öğeyi döndürür. Dizi boşsa diziye erişim başarısız olabileceğinden, her iki fonksiyon da <decides><transacts> belirleyicilerine sahiptir.

Stack gibi queue sınıfının da Elements dizisini atamak için bir oluşturucu fonksiyon kullanması gerekir. Oluşturucu fonksiyon, Elements değerine erişerek bunu bir başlangıç öğe dizisine atamana olanak sağlar.

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Kuyruğa Alma ve Kuyruktan Çıkarma

Kuyruğa öğe eklemek ve çıkarmak için ya yeni öğeyi arkadan kuyruğa eklemen ya da öndeki öğeyi kuyruktan çıkarman gerekir.

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

Enqueue() fonksiyonu, kuyruğa eklemek istediğin öğeyi alır ve yeni öğenin arkada olduğu yeni bir kuyruk döndürür. Mevcut kuyruğu değiştirmek yerine yeni bir kuyruk döndürmek bir işlevsel programlama örneğidir ve yan etki riskini azaltır.

Dequeue() fonksiyonu için kuyruğun önündeki öğeyi çıkarıp döndürmen ve ayrıca ilk öğenin (RemoveElement[] fonksiyonunu kullanarak) çıkarıldığı yeni bir kuyruk döndürmen gerekir. Dizi erişimi için ifadeler ve Front() fonksiyonu çağrısı başarısız olabilir nitelikte olduğundan, Dequeue() fonksiyonu <decides><transacts> belirleyicilerini içermek zorundadır.

Tam Kod

Kuyruk sınıfı için tam kod aşağıda yer alıyor.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

Kendi Kendine Yapabileceklerin

Yığın ve kuyrukları iyileştirip geliştirmenin birçok yolu vardır ve işlevsellik eklemenin farklı yollarını araştırmalısın. İşte başlaman için birkaç fikir:

• Bir kuyruğu, son öğenin ilk öğeye bağlandığı ve kuyruğun döngü halinde devam ettiği dairesel bir kuyruğa dönüştürebilir misin?

• Peki, objelerin kuyruğa giriş zamanlarına VE ayrıca başka bir değere göre sıralandığı bir öncelik kuyruğuna ne dersin?

• Yığınları kullanarak Hanoi Kuleleri gibi oyunlar oluşturabilir misin? Ya da müşterilerin kuyrukta beklemesi gerektiği bir restoran oyunu?