stack sınıf şablonu

Öğe olarak aldıkları bir STL kabını kullanarak belirli bir soyut veri tipi (abstract data type) arayüzü sunan sınıf şablonlarına STL, kap uyumlandırıcıları (container adapters) diyor. STL‘de temel soyut veri tiplerini temsil eden 3 standart kap uyumlandırıcısı var:

stack (yığın)
queue (kuyruk)
priority_queue (öncelik kuyruğu)

Kap uyumlandırıcıları kap (container) değiller. Adımlayıcı (iterator) sunmuyorlar ve bu nedenle STL algoritmaları kap uyumlandırıcıları için doğrudan çağrılamıyor. Kap uyumlandırıcılarını yalnızca bize sundukları arayüz ile kullanabiliyoruz.
Son giren ilk çıkar (Last In First Out) arayüzünü sağlayan soyut veri tipi olan yığın (stack) programlamada çok sık kullanılıyor. 

stack sınıf şablonu <stack> başlık dosyası içinde sunuluyor:

Şablonun birinci tür parametresi olan T, yığında tutulacak öğelerin türü. Şablonun ikinci tür parametresi olan C yığındaki öğeleri tutacak kabın türü. Bu parametre varsayılan tür argumanı olarak deque<T> açılımını almış. Burada kullanılan C türünün STL‘in SequenceContainer özelliklerini sağlaması ve aynı zamanda

işlevlerine sahip olması gerekiyor. Bu özellikleri sağlayan std::vector, std::deque ve std::list ikinci şablon tür parametresi olarak kullanılabiliyor. Yığının kullanacağı kabı kendimiz belirlemek istersek bu parametre için dilediğimiz kap türünü seçebiliyoruz. Aksi halde deque kabını kullanmayı kabul etmiş oluyoruz:

s1 nesnesi

kabını, s2 nesnesi

kabını, s3 nesnesi ise

kabını kullanacak.

Şablonlara yönelik türden bağımsız işlemlerin daha kolay yapılabilmesi için stack sınıf şablonu bazı typedef bildirimleri içeriyor:

stack sınıfının arayüzünde bulunan 3 önemli temel işlev var: push, pop ve top:
push işleviyle başlayalım:

push, yığına öğe ekleyen işlev. C++11 ile birlikte taşıma semantiğinden faydalanmak için bir de sağ taraf referansı parametreli yüklemesi var:

Sağ taraf değerleri için sağ taraf referansı parametreli push işlevi çağrılıyor. Böylece gereksiz kopyalamalardan kurtulmuş oluyoruz:

stack sınıfının pop işlevi yığının en üstünde bulunan öğeyi (son giren öğeyi) yığından çıkartıyor. Birçok yığın kütüphanesinde pop işlemi aynı zamanda yığından çıkarılmış olan değeri geri döndürürken STL verimliliği birinci tasarım ilkesi olarak aldığından stack sınıfının pop işlevi bir geri dönüş değerine sahip değil:

Yığın boşken pop işleminin yapılması durumunda bir hata nesnesi (exception) gönderilmiyor. Bu işlem çalışma zamanına ilişkin bir hata. Yığından çıkartılan öğenin ne olduğunu bilmek istiyorsak (ki çoğu zaman isteyeceğiz) bu öğeyi yığından çıkartmadan önce top işleviyle bu öğenin değerini elde edebiliyoruz. Sınıfın top işlevleriyle yığının en üstündeki veriye erişebiliyor ve bu veriyi (gerekirse) değiştirebiliyoruz.

İşlev const yüklemesine tabi tutulmuş. const olan stack nesneleri için const olan üye işlev çağrılıyor. İşlevin referans döndürdüğüne dikkat edin. Yığının en üstündeki veriyi yığından çıkartmadan değiştirmek mümkün.
Yığın boşken top işevinin çağrılması çalışma zamanı hatası ve bu durumda bir hata nesnesi (exception) gönderilmiyor.

sınıfın size isimli üye işleviyle yığında tutulmakta olan öğe sayısını öğrenebiliyoruz.

empty işleviyle yığının boş olup olmadığını sınayabiliyoruz:

Bu sınamayı

biçiminde de yapabiliriz. Ancak standartlar bu amaçla empty işlevini kullanmanın daha verimli olabileceğini söylüyor.

C++11 ile arayüze eklenen swap üye işleviyle aynı türden iki yığını takas edebiliyoruz.

takas işlemini global swap şablonunun stack sınıfı şablonu için özelleştirilmiş biçimi (specialization) ile de gerçekleştirmemiz mümkün:

stack sınıfı iki ayrı kurucu işlev sunuyor. Varsayılan kurucu işlevi seçtiğimizde

boş bir yığınla başlıyoruz. Ancak elimizde hali hazırda şablon parametresi türünden bir kap varsa bu kaptan öğeleri kopyalayarak ya da taşıyarak yığınımızı oluşturabiliyoruz:

İşlev 2. şablon parametresi türünden parametreye sahip. Bildirimlerden de görüldüğü ikinci kurucu işlev taşıma semantiğini gerçekleştirmek için yüklenmiş. Dilersek kaptaki öğeleri kopyalayarak değil taşıyarak stack nesnemizi başlatabiliyoruz:

C++11 ile artık stack sınıfı da kullandığı kap sınıfının emplace işlevini de kendi arayüzünde sunuyor:

emplace işlevi ile yığına eklenecek nesneyi bir kopyalama işlemine gerek kalmadan, daha düşük maliyetle, doğrudan bu amaç için elde edilmiş bellek alanında hayata başlatabiliyoruz.

stack sınıf şablonu nesne yönelimli programlama da “compositon” dediğimiz ilişki biçiminin de tipik örneklerinden birini temsil ediyor. stack sınıfı veri öğesi olarak aldığı kap sınıfının public arayüzünü kendisi için uyumlandırarak daha özel ve daraltılmış bir arayüzü kendi müşterilerine sunuyor. stack sınıfının basitleştirilmiş bir gerçekleştirimi aşağıdaki gibi olabilir:

stack sınıfı için tüm karşılaştırma işlevleri yüklenmiş. Aynı türden iki stack nesnesini karşılaştırma işlevleriyle karşılaştırabiliyoruz. Karşılaştırma “lexicographical compare” algoritması ile yapılıyor. Bu algoritmaya göre
öğe sayıları birbirine eşit ve karşılıklı tüm öğeleri eşit olan 2 stack eşittir.
İlk farklı öğesi küçük olan stack daha küçüktür.

Geri planda kullanılan kabın stack sınıfının protected bölümünde yer aldığını görüyorsunuz. stack sınıf şablonundan ya da bu şablonun belirli bir açılımından kalıtım yoluyla yeni bir sınıf oluşturduğumuzda, oluşturduğumuz sınıf taban sınıfın veri öğesi olan kap nesnesini c ismiyle kullanabiliyor. Aşağıdaki kodda standart stack şablonundan kalıtım yoluyla elde ettiğimiz mystack sınıf şablonuna clear isimli üye işlevi ekliyoruz:

mystack sınıfının müşterileri sınıfın clear isimli üye işleviyle yığını boşaltabilecekler.

stack sınıfının bazı üye işlevlerinin kullanımı için aşağıdaki kodu inceleyin:

Şimdi de bir yazı içinde bulunan parantez türü öğelerin uyumunu sınayan is_match isimli bir işlev tanımlıyoruz:

İşlevimizde char türden öğeleri tutacak bir cstack isimli bir yığın oluşturuyoruz. Yazıyı dolaşarak, açılan karakterlerden birini gördüğümüzde bu karakteri yığına ekliyoruz (push). Kapanan parantez türü karakterlerden biriyle karşılaştığımızda eğer yığın boşsa ya da yığının en üstündeki karakter, kapanana karşılık gelen uygun açılan parantez değil ise, parantezler uyumsuz demektir. Yığının en üstündeki karakter uygun açılan parantez ise bu karakteri yığından çıkartıyoruz (pop). Parantezlerin uyumlu olması için yazı bittiğinde yığının boş olması gerekiyor.

Necati Ergin

C ve Sistem Programcıları Derneğinde eğitmen olarak çalışıyor.

Bunlar da ilginizi çekebilir

stack sınıf şablonu” için 2 yorum

  1. C derin bir kuyu.
    Aynı zamanda sonsuz satranç tahtası ve satranç taşı olan bir oyun.

    Teşşekürler Sayın Necati Hocama.

    Yapay zeka konusundaki gelişmeler ve yol almalar acaba C/C++ ile mi yapılıyor,
    Yoksa daha derin ve daha karmaşık başka bilmediğimiz bir arac (dil) varmıdır?

  2. Necati bey,
    Elinize sağlık. Yine çok açıklayıcı bir yazı olmuş. Multithreading ve socket programlama ile ilgili yazılarınızı sabırsızlıkla bekliyoruz.

    Kısa bir düzeltme:

    en baştaki kod içerisinde bir büyüktür karakteri eksik kalmış.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Kod Eklemek İçin Okuyun