Yığın yapısı (stack), bilgisayarda girdi ve çıktı işlemi yapmak için işlemin son durumu referans alınırak yapılan bir yapıdır
Yığınlarda
•Yığındaki elemanlardan sadece en son eklenene erişim yapılır.
•Yığına ilk eklenen eleman en son elde edilir.
•FILO (First-in-Last-out) veya LIFO (Last-in-First-out) mantığıyla çalışır.
•İki temel işlem vardır;
o
push, yığının sonuna yeni bir eleman ekleme
o
pop, yığının en üstündeki elemanın alınması
•Dizilerle veya bağlı listelerle yapılabilir.
•Dizilerde boyut değiştirme ve yeni elemen ekleme zorluğundan dolayı genellikle bağlı dizilerle yapılır.
•En üst veya en son elemanı gösteren bir node tanımlanır (headNode).
Yığın mantığı bilgisayar donanım ve yazılım uygulamalarında yaygın olarak kullanılmaktadır.
Örnek kullanım yerleri:
•Yazılım uygulamalarındaki Undo işlemleri stack ile yapılır.
o
Undo işlemi için LIFO yapısı kullanılır.
•Web browser’lardaki Back butonu (önceki sayfaya) stack kullanır.
o
Buradada LIFO yapısı kullanılır
•Matematiksel işlemlerdeki operatörler (+,*,/,- gibi) ve operandlar için stack kullanılabilir.
•Yazım kontrolündeki parantezlerin kontrolünde stack kullanılabilir.
Günlük hayatımızda yığın örnekleri
•üst üste yerleştirilmiş kitaplar,
•üst üste yığılı kutular.
Üst üste yerleştirilmiş tabak örneğinde en son konulan tabak en önce alınacaktır. Veya tabak konulduğundan en üste konulacaktır.
Aynı şekilde üst üste yığılı kutulardan en sütteki kutu yerine aradan bir kutu alınamaz.
Yığın (stack) yapısına yeni bir eleman eklemek veya çıkarmak istenildiğinde, bu elemanı yapının (dizinin) en sonuna eklemek veya çıkarmak gerekir. Yapının (dizinin) ara yerlerine veya en altına eleman ekleme/çıkarma yapmak mümkün değildir.
Şekil Yığın yapısı
Sekil de yığın yapısını anlatan güncel örnekler görülmektedir. Yığın yapısındaki temel işlemler, eleman ekleme push (itme) ve en son eklenen elemanı alan pop (çekme) işlemleridir.
En son eklenen eleman, pop işlemiyle yığından silinmiş olur ve bir önceki eleman yığının sonuncu elemanı olur.
Yığın yapılarında iki işlem söz konusudur. Birincisi yığına eleman ekleme (Push) diğeri ise yığından eleman çıkarma (Pop) işlemidir. Ayrıca yığının boş veya dolu olup olmadığının kontrol edilmesi gerekir.
Örnek olarak aşağıdaki şekilde dizi boyutu 3 olan bir yığın yapısında sırasıyla yapılan işlemler gösterilmektedir.
Buna göre yapılan işlemleri sıralarsak;
(I) _ Yığına ‘5’ elemanı eklendi
(II) _ Yığına ‘8’ elemanı eklendi
(III) _ Yığından eleman çıkarıldı
(IV) _ Yığından eleman çıkarıldı
(V) _ Yığından eleman çıkarıldı ( “Yığın bos” Hata mesajı verir)
(VI) _ Yığına ‘6’ elemanı eklendi
(VII) _ Yığına ‘9’ elemanı eklendi
(VIII) _ Yığına ‘7’ elemanı eklendi
Ayrıca iki yığının eşit olması için:
•eşit sayıda elemana sahip olması,
•elemanların sıralamalarının aynı olması gerekir.
Yığınlar diziler ile gerçekleştirilirler. Ancak diziler belirli bir büyüklükte tanımlanırken, yığınlar dinamik bir yapıya sahiptir. Bu sebeple dizi boyutu yığının içeriği ile dinamik değişmek zorundadır.
Yığına ekleme (push) işleminin algoritması;
Eğer (Yığın dolu ise)
“Yığın dolu” mesajını yaz
Değilse
Veriyi yığına ekle
Yığın göstericiyi (Stack Pointer) 1 artır
Yığından eleman çıkarma (Pop) işleminin algoritması;
Eğer (Yığın boş ise)
“Yığın boş” mesajını yaz
Değilse
Yığın göstericiyi (Stack Pointer) 1 azalt
Yığından veriyi sil
Örnek. Aşağıda 4 eleman büyüklüğünde tamsayı yığını oluşturan program verilmektedir.
using System;
class OrnekYigin
{
static void Main()
{
int[] dizi = new int[4];
int isaretci;
isaretci = 1;
Console.WriteLine("dizi ielemanlarını giriniz");
for (int i = 0; i < 4; i++)
{
dizi[i] =Convert.ToInt32(Console.ReadLine());
isaretci++;
}
Console.WriteLine("Dizi elemanlarının yıgına atılmıs hali");
for (int i = 0; i < 4; i++)
{
isaretci = isaretci - 1;
Console.WriteLine(dizi[i]);
}
}
}
Örnek yığına sırasıyla (4 9 3 7 )elemanlarını girdiğimizi farz edersek, buna göre yığına ilk giren eleman ( ‘4’) dizinin en altına, son giren eleman (‘7’) ise dizinin en üstüne yerleştirildi. Programın çıktısı aşağıda görülmektedir.
Örnek
Ekleme, çıkarma işlemlerini gerçekleştiren ve yığının durumunu bildiren program.
using System;
class yigin
{
public int p;
public int[] veri;
public yigin()
{
this.p = p;
this.veri = new int[10];
}
}
class YiginUygulama
{
static yigin Yigin = new yigin();
static void ekle(int gelen)
{
if (Yigin.p >= 10)
Console.WriteLine("Yigin dolu");
else
{
Yigin.veri[Yigin.p] = gelen;
Yigin.p++;
}
}
static void al()
{
if (Yigin.p <= 0)
Console.WriteLine("Yigin Bos");
else
Yigin.p--;
}
static void listele()
{
if (Yigin.p > 0)
for (int i = Yigin.p - 1; i >= 0; i--)
Console.WriteLine(Yigin.veri[i].ToString());
else
Console.WriteLine("Yigin boş");
}
static void sil()
{
Yigin.p = 0;
}
static void Main()
{
listele();
ekle(3);
ekle(5);
listele();
al();
listele();
ekle(2);
listele();
sil();
listele();
}
}
C# Stack sınıfı
System.Collections isim alanındaki Stack sınıfı bulunmaktadır.
Bir Stack nesnesi şu yollardan biriyle oluşturulabilir.
Stack s1=new Stack();
Stack s2=new Stack(int kapasite);
Stack s3=new Stack(ICollection ic);
•Birincisinde klasik bir Stack nesnesi oluşturulur.
•İkincisinde kapasitesi kapasite olan bir Stack nesnesi oluşturulur. Kapasite aşılırsa otomatik olarak kapasite artırılır.
•Üçüncüsünde ICollection arayüzünü kullanan başka bir koleksiyon nesnesinden yeni bir Stack nesnesi oluşturulur.
Stack sınıfının önemli üye elemanları:
•object Pop() İlgili yığındaki en üstteki elemanı döndürür ve yığından çıkarır.
•object Peek() İlgili yığındaki en üstteki elemanı döndürür ama yığından çıkarmaz.
•void Push(object o) İlgili yığının en üstüne o elemanını ekler.
•void Clear() İlgili yığındaki bütün elemanları siler.
•object[] ToArray() İlgili yığındaki elemanlar object dizisi olarak döndürülür.
•bool Contains(object o) Eğer o nesnesi ilgili yığında varsa true, yoksa false döndürülür.
•int Count Bu özellik ilgili yığındaki eleman sayısını verir.
Örnek: Pop, Peek, Count
using System;
using System.Collections; // Stack sınıfı bu isim alanı içinde bulunur.
class YiginSinifi1
{
public static void Main(string[] args)
{
// Stack sınıfından yigin nesnemizi tanımlıyoruz.
Stack yigin = new Stack();
// Yigini değişik değerlerde dolduruyoruz..
yigin.Push(12);
yigin.Push(5);
yigin.Push(23);
yigin.Push(34);
yigin.Push(70);
yigin.Push(8);
Console.WriteLine("Yığımızın ilk hali...");
ElemanlariYaz(yigin);
// Yigininin tepesinden bir sayı aldık
// ve bunu sayi değişkenine atayıp ekrana yazdıralım
int sayi = (int)yigin.Pop();
Console.WriteLine("\n Yığından {0} sayısını aldık", sayi);
// Yigininin tepesinden bir sayı daha aldık
// ve bunu sayi değişkenine atayıp ekrana yazdıralım
sayi = (int)yigin.Pop();
Console.WriteLine("\n Yığından {0} sayısını aldık", sayi);
// Şimdi ise Yigininin tepesindeki sayıya bir bakalım
// bu sayıyı yığından çıkarmıyoruz.. Sadece ne olduğuna bakıyoruz..
sayi = (int)yigin.Peek();
Console.WriteLine("\n Yığının tepesindeki sayı şu anda : {0}", sayi);
Console.ReadLine();
}
public static void ElemanlariYaz(Stack yigin)
{
object obj = new Object();
Stack yeniYigin = (Stack)yigin.Clone();
if (yigin.Count != 0)
{
while (yeniYigin.Count > 0)
{
obj = yeniYigin.Pop();
Console.WriteLine("\t" + obj.ToString());
}
}
else Console.WriteLine("Yığın boş...!");
}
}
Örnek Contains(), Clear()
using System;
using System.Collections; // Stack sınıfı bu isim alanı içinde bulunur.
class YiginSinifi1
{
public static void Main(string[] args)
{
// Stack sınıfından yigin nesnemizi tanımlıyoruz.
Stack yigin = new Stack();
// Yığınımıza yeni elemanlar ekliyoruz.
yigin.Push("Ahmet");
yigin.Push("Sefer");
yigin.Push("Cemal");
yigin.Push("Onur");
yigin.Push("Aziz");
// Yığında kaç tane eleman bulunduğunu bulup yazalım.
int elemanSayisi = yigin.Count;
Console.WriteLine("\nYığınımızdaki eleman sayısı: {0}", elemanSayisi);
// Yığındaki elemanlar.
Console.WriteLine("\nYığındaki elemanlar: ");
ElemanlariYaz(yigin);
//Contains() metodunun kullanımı:
if (yigin.Contains("Sefer"))
Console.WriteLine("\nYığında Sefer elemanı var...");
else
Console.WriteLine("\nYığında Sefer elemanı yok...");
// Yığını boşaltalım.
yigin.Clear();
// Yığını boşalttıktan sonra kaç tane eleman bulunduğunu bulup yazalım.
elemanSayisi = yigin.Count;
Console.WriteLine("\nYığınımızdaki eleman sayısı: {0}", elemanSayisi);
Console.ReadLine();
}
public static void ElemanlariYaz(Stack yigin)
{
object obj = new Object();
Stack yeniYigin = (Stack)yigin.Clone();
if (yigin.Count != 0)
{
while (yeniYigin.Count > 0)
{
obj = yeniYigin.Pop();
Console.WriteLine("\t" + obj.ToString());
}
}
else Console.WriteLine("Yığın boş...!");
}
}
Örnek Clone(), Equals() ve ToArray()
using System;
using System.Collections; // Stack sınıfı bu isim alanı içinde bulunur.
class YiginSinifi1
{
public static void Main(string[] args)
{
// Stack sınıfından yigin nesnemizi tanımlıyoruz.
Stack yigin1 = new Stack();
// Yığınımıza yeni elemanlar ekliyoruz.
yigin1.Push("Ahmet");
yigin1.Push("Sefer");
yigin1.Push("Cemal");
yigin1.Push("Onur");
yigin1.Push("Aziz");
//İkinci yığınımızı tanımlıyor ve yigin1'in
// bir kopyasını yigin2'ye koyuyoruz..
Stack yigin2 = (Stack)yigin1.Clone();
// yigin1'den bir eleman çıkartıyoruz.
yigin1.Pop();
//yigin1 ve yigin2 nesnelerimizin en üstteki
// elemanlarına bir bakalım:
Console.WriteLine(" Peek of Yığın2: " + yigin2.Peek());
Console.WriteLine(" Peek of Yığın1: " + yigin1.Peek());
//yigin1 ve yigin2 eşit mi? Bir bakalım:
Console.WriteLine("\n yigin1 ve yigin2 eşit? --> " + yigin1.Equals(yigin2));
//yigin2'yi kopyalamak için yeni bir dizi oluşturalım:
Array arr = new Array[5];
// yeni oluşturduğumuz diziye yigin2'yi kopyalayalım:
arr = yigin2.ToArray();
// arr nesnesinin elemanları:
Console.WriteLine("\n\n arr nesnesinin elemanları:\n" +
"\n\t" + arr.GetValue(0) +
"\n\t" + arr.GetValue(1) +
"\n\t" + arr.GetValue(2) +
"\n\t" + arr.GetValue(3) +
"\n\t" + arr.GetValue(4));
Console.ReadLine();
}
public static void ElemanlariYaz(Stack yigin)
{
object obj = new Object();
Stack yeniYigin = (Stack)yigin.Clone();
if (yigin.Count != 0)
{
while (yeniYigin.Count > 0)
{
obj = yeniYigin.Pop();
Console.WriteLine("\t" + obj.ToString());
}
}
else Console.WriteLine("Yığın boş...!");
}
}