C++ ile yığın (stack) veri yapısı

Tanım

Aynı tip veriler kümesinin düzenli bir şekilde tutulması için dizi, bağlı liste gibi doğrusal veri yapıları kullanılır. Bu veri yapılarında dizinin veya bağlı listenin sırasına yeni veri ekleme, istenen bir veriyi çıkarma işlemini yapmak mümkündür.

Yığın veri yapısında, yeni eleman ekleme ve çıkarma işlemi LIFO (Last In First Out/Son giren ilk çıkar) kuralı ile gerçekleşir. Yani yığına her zaman son eklenen eleman ilk önce çıkartılır.

Yığınlara eleman ekleme işlemi push() fonksiyonu ile, eleman çıkarma işlemi ise pop() fonksiyonu ile gerçekleştirilir.

Bir yığın veri yapısı; dizi veya bağlı liste veri yapıları kullanılarak oluşturulabilir.

Kriter	Dizi	Bağlı Liste
Boyut	Ön tanımlıdır. Çalışma zamanında değiştirilemez.	Boyutu her zaman eleman sayısına eşittir, yani çalışma zamanında sürekli değişebilir.
Bellek alanı	Fiziksel olarak ardışık bellek alanı gerekir.	Bellekte dağınık bir şekilde yerleşebilir.
Elemanların sırası	Dizinin indeks numarası ile tüm elemanlara erişilebilir.	Bir sonraki elemanın bellek adresi bilgisi bir önceki eleman tarafından tutulur.

Kaynak kod

Burada yalnızca bir tamsayı değer verisi taşıyan bir yığın veri yapısı bağlı liste kullanılarak oluşturulmuştur. Bunun için bu tipte veri yapısının tanımlanması gerekir.

struct eleman{
  int veri;
  eleman *sonraki;
};

Burada, eleman adında yeni bir veri yapısı tanımlanmıştır. Bu yapı bir adet tamsayı veri ve bir adet de işaretçi depolamaktadır. İşaretçi, yine eleman tipinde bir başka veri yapısının bellekteki başlangıç adresini göstermektedir.

eleman* ust = new eleman;
int stackboyutu = 0;

Yukarıda; ust adında global bir işaretçi ve yığının eleman sayısını tutacak stackboyutu tamsayı değişkeni tanımlanmıştır. ust işaretçisi her zaman yığının top (en üst) elemanını gösterecektir.

void push(int data)
{
  eleman *yeni = new eleman;
  yeni->veri = data;
  yeni->sonraki = ust;
  ust = yeni;
  cout<<data<<" stack'e eklendi."<<endl;
  stackboyutu++;
}

Yukarıdaki push() fonksiyonu adım adım;

1. Yığına eklenmek üzere yeni bir bellek alanı rezerve eder.
2. Yeni elemanın veri alanına saklanacak tamsayı değeri yazılır.
3. Yeni elemanın kendisinden sonraki eleman yığının bir önceki en üst elemanıdır ve yeni eklenen elemanın sonraki işaretçi alanına bir önceki en üst elemanın bellek adresi yazılır.
4. Artık top (en üst) eleman, yeni elemandır.
5. Yığın boyutunu tutan değişkenin değeri 1 arttırılır.

int pop()
{
  if(stackboyutu!=0)
  {
    cout<<"Eleman: "<<ust->veri<<" silindi."<<endl;
    ust = ust->sonraki;
    stackboyutu--;
  }
  else cout<<"Stack zaten bos!"<<endl; 
}

Yukarıdaki pop() fonksiyonu ile önce stackboyutu değişkeninin değerine bakılarak yığının boş olup olmadığı kontrol edilir. Eğer boş bir yığında pop() fonksiyonu çalıştırılırsa hata gösterilmelidir. Eğer yığında çıkarılabilecek eleman varsa ust işaretçisinin gösterdiği elemanı yığından çıkarmak için, ust işaretçisinin gösterdiği elemandan sonraki eleman ust->sonraki ust işaretçisine bağlanır. Böylece yığının top (en üst) elemanı artık bir sonraki elemandır.

Yığının ekrana yazdırılmasını, pop() ve push() fonksiyonlarının örnek kullanımını da içeren kaynak kod aşağıdaki şekildedir.

#include<iostream>
using namespace std;

struct eleman{
  int veri;
  eleman *sonraki;
};

eleman* ust = new eleman;
int stackboyutu = 0;

void push(int data)
{
  eleman *yeni = new eleman;
  yeni->veri = data;
  yeni->sonraki = ust;
  ust = yeni;
  cout<<data<<" stack'e eklendi."<<endl;
  stackboyutu++;
}

int pop()
{
  if(stackboyutu!=0)
  {
    cout<<"Eleman: "<<ust->veri<<" silindi."<<endl;
    ust = ust->sonraki;
    stackboyutu--;
  }
  else cout<<"Stack zaten bos!"<<endl; 
}

yazdir(eleman *ptr)
{
  cout<<"Stack son durumu:"<<endl;
  for(int i=1;i<=stackboyutu;i++)
  {
    cout<<i<<". eleman: "<<ptr->veri<<endl;
    ptr = ptr->sonraki;
  }
}

main()
{
  push(15);     // Yığına 15 elemanını ekler
  push(22);     // Yığına 22 elemanını ekler
  pop();        // Yığından 22 elemanını çıkarır
  push(54);     // Yığına 54 elemanını ekler
  pop();        // Yığından 54 elemanını çıkarır
  push(65);     // Yığına 65 elemanını ekler
  pop();        // Yığından 65 elemanını çıkarır
  pop();        // Yığından 15 elemanını çıkarır
  yazdir(ust);  // Yığının son durumunu ekrana yazdırır
}