Tag Archives: stack

Hackerrank “30 Days of Code” Çözümleri – Day 18: Queues and Stacks

Hackerrank’in 30 Days of Code içerisinde bulunan “Day 18: Queues and Stacks” sorusunun açıklaması ve çözümü. Bu soruda queue ve stack yapısına göz attık.

► Hackerrank 30 Days of Code Çözümleri – Day 18: Queues and Stacks: https://www.hackerrank.com/challenges/30-queues-stacks/problem

► Problem açıklaması:

Welcome to Day 18! Today we’re learning about Stacks and Queues. Check out the Tutorial tab for learning materials and an instructional video!

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backwards and forwards. Can you determine if a given string, s, is a palindrome?

To solve this challenge, we must first take each character in s, enqueue it in a queue, and also push that same character onto a stack. Once that’s done, we must dequeue the first character from the queue and pop the top character off the stack, then compare the two characters to see if they are the same; as long as the characters match, we continue dequeueing, popping, and comparing each character until our containers are empty (a non-match means s isn’t a palindrome).

Write the following declarations and implementations:

Two instance variables: one for your stack, and one for your queue.

A void pushCharacter(char ch) method that pushes a character onto a stack.

A void enqueueCharacter(char ch) method that enqueues a character in the queue instance variable.

A char popCharacter() method that pops and returns the character at the top of the stack instance variable.

A char dequeueCharacter() method that dequeues and returns the first character in the queue instance variable.

Input Format

You do not need to read anything from stdin. The locked stub code in your editor reads a single line containing string s. It then calls the methods specified above to pass each character to your instance variables.

Constraints

is composed of lowercase English letters.

Output Format

You are not responsible for printing any output to stdout.

Sample Input

racecar

Sample Output

The word, racecar, is a palindrome.

.NET içerisinde Değer Tipi ve Referans Tipi

.NET kodunun çalıştırılmasını sağlayan CLR yapısı iki çeşit veri tipini destekler; referans tipi (reference types) ve değer tipi (value types). FCL (Framework Class Library) içerisinde bulunan tiplerin çoğu referans tipi olsa da, programcıların kullandığı tiplerin çoğunu değer tipleri oluşturur. Referans tiplerine her zaman belleğin “Heap” kısmından yer ayrılır ve C#’ın new operatörü de bu nesnenin bellek adresini döndürür (Bellek adresi de nesnenin bitlerini kaynak gösterir). Şunu aklınızda tutmalısınız ki, referans tipleri ile çalışırken bazı performans özelliklerine dikkat etmelisiniz. Şu 4 maddeyi göz önünde bulundurun:

1. Yönetilen heap kısmından bellek ayrılmak zorundadır.

2.Heap bölgesine ayrılmış her nesnenin kendisi ile ilişkili ilave üyeleri mevcuttur.

3.Nesnenin içineki diğer bitler her zaman sınıfa ayarlanır. (Alanlar için)

4.Bir nesneye heap bölgesinden kaynak ayırabilmek bazen Garbage Collection’ı ortaya çıkartabilir.

Her tip referans tipi olsaydı, bir uygulamanın performansı fazlasıyla kayba uğrardı. Düşünün ki, her Int32 tipini kullandığınızda bellekten bir yer tahsis etmek zorundasınız. Ne kadar kötü bir performans alacağınızı farketmişsinizdir. Performans arttırmak için, sıkça tip kullanılan uygulamalarda, CLR “hafif siklet” olarak adlandırdığı değer tiplerini önerir. Değer tipi örnekleri için çoğunlukla belleğin stack bölgesinden yer tahsis edilir (Ayrıca bir referans tipi nesnenin içerisine bir alan olarak gömülebilirler). Bu tipin bir değişkeni, örneğine bir pointer içermez, bu değişken örneğinin kendisinin bir alanını içerir. Değer tipi örnekleri, garbage collector’ın kontrolü altına girmezler ve bu sayede yönetilen heap kısmının üzerindeki yükü azaltır.

.NET Framework SDK dökümanı hangi tiplerin değer tipi, hangi tiplerin referans tipi olduğunu açık bir şekilde gösterir. Bu dökümana baktığımızda sınıf tipleri referans tipleridir. Örneğin; System.Exception, System.IO.FileStream ve System.Random birer referans tipleridir. Diğer taraftan döküman structure (yapı) ve enum tiplerinin değer tipi olduğunu gösterir. Örneğin; System.Int32 yapısı, System.DayOfWeek enum tipi, System.Decimal yapıları birer değer tipidir.

Biraz daha derinlere inmeye çalışırsak, tüm structure yapıların System.ValueType abstract tipinden türediğini görürüz. System.ValueType tipinin de System.Object tipinden türetildiğini görürürz. Tüm enum tipleri System.Enum abstract tipinden türetilmişlerdir ki bu tip te yine System.ValueType tipinden türetilir. CLR ve diğer tüm programlama dilleri enum tiplerine ayrı bir davranış sergilerler. Burada kafanıza şu soru takılabilir. Görüldüğü üzere System.ValueType bir sınıf tipidir ve sınıf tipleri referans tipidir. O halde Nasıl bir değer tipi bir referans tipinden türeyebilir?

Kendi değer tipinizi tanımlamaya çalışırken değer tiplerini temel tip olarak kullanamazsınız. Çünkü tüm değer tipleri sealed (yani o sınıf için türetilme işlemini önler) olarak tanımlıdır. Bu nedenle yeni oluşturmak istediğini referans tipinde ya da değer tipinde bir tip için, temel tip olarak değer tiplerini kullanamazsınız. Bir örnekle açıklamaya çalışırsam; Boolean, Char, Int32, Uint64, Single, Double tiplerini temel tip şeklinde kullanıp yeni bir tip oluşturmak imkansızdır.

Aşağıdaki örnek size referans tipi ve değer tiplerinin farklılığını açıklar:

using System;
namespace Program
{
 //Referans Tipi [Sınıf olduğundan]
 class ReferansTipi
 {
 public int x;
 }

//Değer Tipi [Struct olduğundan]
 struct DegerTipi
 {
 public int x;
 }

public class Program
 {
 public static void Main(string[] args)
 {
 ReferansTipi r1 = new ReferansTipi(); // Yer Tahsisi - Heap
 DegerTipi d1 = new DegerTipi(); // Yer Tahsisi - Stack

r1.x = 5; // Pointer referansı
 d1.x = 5; // Stack içerisinde değişim

Console.WriteLine(r1.x); // 5
 Console.WriteLine(d1.x); // 5
 }
 }
}

Bu kod parçasını çalıştırdığımızda bilgisayarımızın bellek kısmında aşağıdaki resimde görülen bir durum oluşur:

stack-heap

Harika(!) bir çizer olduğumu da bu resimden anlamışsınızdır. Şimdi aşağıdaki kodları yukarıda belirttiğimiz kodun içerisindeki Main() metodunun sonuna ekleyelim ve bellek kısmında nasıl bir değişiklik olduğuna bakalım:

ReferansTipi r2 = r1; // Sadece referansı (pointer) kopyalama

DegerTipi d2 = d1; // Yer Tahsisi - Stack ve üyeyi kopyalama

r1.x = 6; // r1.x ve r2.x değerlerini değiştirir.
d1.x = 7; // d1.x'i değiştirir, d2.x'i değiştirmez.

Console.WriteLine(r1.x); //6
Console.WriteLine(r2.x); //6
Console.WriteLine(d1.x); //7
Console.WriteLine(d2.x); //5

stack-heap1

Bu kod içerisinde bazı satırlara değinmek istiyorum:

DegerTipi d1 = new DegerTipi(); // Yer Tahsisi – Stack

Bu koda direkt olarak baktığımızda belleğin heap bölgesinden yer tahsis edildiği bilgisine varılır. Fakat, C# DegerTipi örneğinin bir değer tipi olduğunu bilir ve bununiçin stack bölgesinden yer ayıracak kodu üretir. C# ayrıca bu değer tipinin içerisindeki tüm alanların sıfıra set edildiğine emin olur. Aynı satır kod şu şekilde de yazılabilir;

DegerTipi d1;

Bu kod aynı şekilde thread kısmındaki stack bölgesinden yer ayırır ve tüm alanları sıfıraatar. Bu iki kod arasındaki tek fark, eğer new operatörünü kullanırsak C# düşünür ki bu örnek ilk kullanıma hazırdır. Hemen bu konuyu daha da açık hale getirelim;

DegerTipi d3 = new DegerTipi(); // Bu iki satır derlenir çünkü
int a = d3.x; // C#, d3'ün alanlarını sıfıra atandığını bilir.

DegerTipi d3; // Bu iki satır derlenimez çünkü C#, d3'ün alanlarını sıfıra
int a = d3.x; // atanmadığı düşünür. Use of possibly unassigned field 'd3' hatası alırız.

Eğer .NET içerisinde kendi değişken tipinizi tasarlamak isterseniz, bu tipin referans tipi mi yoksa değer tipi mi olacağına dikkatle karar vermelisiniz. Bazı durumlarda değer tipleri daha iyi performans verebilir. Eğer aşağıdaki 3 özellikte tasarlamak istediğiniz tip için uygunsa bu tipi değer tipi olarak tasarlamalısınız;

  1. Tip ilkel bir tip olursa (primitive types). Burada bahsetmek istediğim bu tipin içerisindeki alanlarda herhangi bir düzenlemesi gereken üyesi yoksa mantığıdır.
  2. Bu tipin diğer tiplerden kalıtım almasına gerek yoksa.
  3. Bu tipten türetilecek başka tipler yoksa.
    Yeni değişken tipinizin örnek boyutu da burada hesaba katılmalıdır. Çünkü varsayılan olarak, argümanlar metodlara değer ile geçirilirler (pass by value). Böylece değer tipi örneğinin içindeki alan kopyalanır ki bu da performansı azaltır. Tekrardan, geriye bir değer tipi döndüren metodlar, metodu çağıran tarafından bellekte örneğin içindeki alananın kopyası için yer tahsisi yaparlar ki bu da performansı azaltır.

Değer tiplerinin temel avantajı, bir nesne olarak belleğin yönetimli heap kısmında yer kaplamazlar. Tabi ki değer tiplerinin, referans tiplerine göre birkaç sınırlaması mevcuttur. Şimdi bu durumlara bir göz atalım;

1. Değer tipi nesnelerinin iki farklı gösterimi vardır. Boxed ve unboxed. Referans tipleri her zaman boxed formdadırlar.

2. Değer tipleri System.ValueType sınıfından türetilmişlerdir. Bu tip System.Object’te tanımlanan aynı metodları sağlar. Fakat, System.ValueType Equals() metodunu override eder. Böylece iki nesnedeki alanların içindeki değerler eşleşirse geriye true döndürür. Ek olarak, System.ValueType GetHashCode() metodunu da override eder ki bu method bir değer tipi için algoritma kullanarak bir hash kodu üretir.

3.Değer tiplerini temel sınıf (base class) olarak, herhangi bir değer tipi veya referans tipi üretemeyeceğimiz için, bir değer tipine yeni bir sanal (virtual) metod tanımlamamalıyız. Hiçbir metod soyut (abstract) olmamalıdır.

4. Referans tipi değişkenler belleğin heap kısmındaki nesnenin bellek adresini içerirler. Default olarak, referans tipinde bir değişken oluşturulduğunda, null’a atanır ki bunun anlamı bu değişken henüz geçerli bir nesneyi göstermiyordur. Null olarak atanmış bir referans nesnesini kullanmaya çalıştığımızda NullReferanceException hatası alırız. Buna karşı, değer tipi değişkenleri her zaman tanımlandığı tipin değerini içerir ve bu değer tipinin tüm üyeleri 0’a atanır. Değer tipi değişkeni bir referans içermediği için, bir değer tipine ulaşırken NullReferanceException hatası almamız imkansızdır.

5.Bir değer tipi değişkenini başka bir değer tipi değişkenine atadığımızda, alandan alana kopyalama gerçekleşir. Bir referans tipi değişkenini başka bir referans tipi değişkenine atadığımızda sadece bellek adresi kopyalanır.

6.Bir önceki maddeden dolayı, referans tipleri heap bölgesinde aynı nesneye referans olabileceklerinden, bir referans tipindeki değişkenin üzerindeki değişiklik diğer bir referans tipindeki değişkeni değiştirebilir. Diğer taraftan, bir değer tipindeki değişkenin diğer değer tipindeki değişkeni etkilemesi imkansızdır.

Değer tiplerinde Equals() metodunun varsayılan uygulaması olarak bit bit karşılaştırma yapması bazı durumlarda performansı yükseltebilir. Eğer iki adet değer tipi değişkeninizin içerisi pozitif sıfır ve negatif sıfır ise, sırasıyla eşit değil olarak karşılaştırılırlar. Ama Equals() metodunu varsayılan davranışı için override edebilirsiniz. Örneğin;

using System;

namespace Program
{
    public class Program
    {
        struct S
        {
            public double X;
        }

        public static void Main(string[] args)
        {
            var i = new S { X = 0.0 };
            var j = new S { X = -0.0 };

            Console.WriteLine(i.X.Equals(j.X)); // True
            Console.WriteLine(i.Equals(j)); // False
        }
    }
}

C#’ta Alanlar (Fields)

C#’ta alanlar, bir sınıf ya da bir sınıf örneği ile ilişkilendirilmiş değişkenlerdir. Static değiştiricisi ile tanımlanmış alanlar static field olarak tanımlanır. Static field’lar, tam olarak bir bellek yeri tanımlarlar. Kaç tane sınıf örneği oluşturulursa oluşturulsun, static field’ın sadece bir tane kopyası vardır.

Önemli: Static field’lar her generic type için ayrı bir yapısal yapıdır. Örneğin elinizde;

class Stack<T>
{
public readonly static Stack<T> bos = tralalalala;
}

varsa, Stack<int>.bos ve Stack<string>.bos alanları farklı alanlardır.

Static değiştiricisiz tanımlanmış alanlar birer örnek alanlardır. Her bir sınıf örneği, o sınıfın her bir örnek alanın kopyasını içerir.

Aşağıdaki örnekte; her bir Color sınıfının örneği, her bir r (red), g (green), b (blue) alanlarına sahiptir ama sadece bir adet kopya Siyah, Beyaz, Kırmızı, Yeşil ve Mavi static (durağan) alanlar mevcuttur.

public class Color
{

public static readonly Color Siyah = new Color(0, 0, 0);
public static readonly Color Beyaz = new Color(255, 255, 255);
public static readonly Color Kırmızı = new Color(255, 0, 0);
public static readonly Color Yeşil = new Color(0, 255, 0);
public static readonly Color Mavi = new Color(0, 0, 255);

private byte r, g, b;
public Color(byte r, byte g, byte b)
{
this.r = r;
this.g = g;
this.b = b;
}
}

Yukarıda görüldüğü gibi sadece okunabilir alanlar readonly değiştiricisi ile tanımlanmıştır. Bir readonly alana atama, sadece o alanın tanımlamasındaki bir kısmından ya da aynı sınıftaki bir yapıcı (constructor) sayesinde gerçekleşebilir.

Önemli: Readonly kelimesi dışarıdaki tip yapıcısı tarafından o alanın konumunun değiştirilmesini önler fakat o konumdaki değeri korumaz. Örneğin, aşağıdaki gibi İsimler şeklinde bir sınıfımız olsun;

public class İsimler
{
public static readonly StringBuilder İlkDogan = new StringBuilder("İlker");
public static readonly StringBuilder İkinciDogan = new StringBuilder("Soner");
}

Bir yapıcının dışından direkt olarak İlkdoğan örneğinin sonucunu değiştirmek bize bir derleyici hatası verecektir.

İsimler.İlkDogan = new StringBuilder("Caner"); // Derleyici Hatası

Ama, StringBuilder örneğini modifiye ederek aynı sonuca aşağıdaki şekilde ulaşabilirim;

İsimler.İlkDogan.Remove(0,6).Append("Caner");

Console.WriteLine(İsimler.İlkDogan); // Output “Caner” olur.

Bu yüzden, read-only kullanımı değişmez tipler için sınırlı kullanılmalıdır şeklinde tavsiye edilir. Değişmez tipler (Immutable types), int, double, string gibi açıkça setter’lara (belirleyiciler) sahip değildirler.