Takıldığınız bir şey mi var?

.NET, front-end development, data structures veya desing patterns gibi konularda sorular açın ve en kısa zamanda cevaplayalım...


2
Şubat

LIFO çalışma prenbisini anlamak için C++ dili ile Template Stack örneği.

Bu makalemizde Stack veri yapısını C++ dili ile basit bir örnek altında inceleyeceğiz. Stack veri yapısına dokunmadan evvel programlama dünyası için oldukça anlamlı bir ifade olan LIFO hakkında konuşalım. LIFO, “Last In First Out” kelimelerinin baş harflerinden oluşmuş bir kısaltma olup “Son giren ilk çıkar” anlamına gelmektedir? LIFO, ilgili koleksiyon türü içine en son dahil edilen elemanın ilk önce dışarı çıkmasını prensip edinmiş bir çalışma biçimidir. Ne demek istediğimi anlamak adına aşağıdaki görseli mercek altına alalım.



LIFO mantığı için son derece klişe olsa da verilmeye değer bir örnek olarak resimdeki üst üste yığılmış kitapları düşünebiliriz. Üst üste yığılan kitapları bir yığın olarak düşündüğümüzde bu kitapları bulundukları yerden almak için ilk önce en üstteki kitaba elimizi uzatırız. Aslında en üstteki kitabın yığına en son eklenen kitap olması, son eklenen kitabın ilk önce çıkması gibi bir sonuç ortaya koyar. LIFO prensibinin çalışma mantığı aynen bu şekildedir ve LIFO prensibinde çalışan bir koleksiyonun içindeki elemana ulaşmak istediğinizde en yukarıdaki eleman ilgili koleksiyon içine dahil edilmiş en son eleman olur.



LIFO prensibini anladığımıza göre artık Stack yani yığın veri yapısı hakkında konuşmaya başlayabiliriz. Stack, LIFO prensibinde çalışan, temel olarak push, pop ve peek fonksiyonlarını içeren bir veri yapısıdır.


  • Push ---> Yığına eleman ekler.
  • Pop ---> Yığının sıradaki elemanını teslim eder, elemanı yığından siler.
  • Peek ---> Yığının sıradaki elemanını teslim eder.


Stack veri yapısını C++ programlama dili ile Array veya Linked List temelli olarak tanımlayabilmekteyiz. Array ile çalışmanın getireceği kapasite sorunu nedeniyle örneğimi Linked List temelli olarak yapmak istiyorum. Öncelikle uygulamamıza aşağıdaki sınıf kitaplıklarını include edelim.

#include <iostream>
#include <string>
#include <sstream>
using namespace std;


Linked List yani bağlı listeler ile çalıştıysanız Node kavramı hakkında iyi kötü bilgi sahibi olmanız kaçınılmazdır. Ancak yine de kısa bir açıklama yapmak gerekirse, verileri birbirine bağlamak adına düğümler kullanılır diyebiliriz. Veriler, birbirlerine pointer ile bağlı olmak koşuluyla run time esnasında belleğin herhangi bir yerine çıkabilir. Bu sayede birden çok eleman ile çalışılırken kapasite sorunu yaşanmaz.


template<class T>
struct stackNode
{
       T data;
       stackNode *pointer = nullptr;
};


Gelişmiş bir Stack tanımı yapabilmek adına düğüm veri tipini template olarak bildirmekte fayda var. Linked List için tanımlanacak bir düğüm tipinin verinin kendisini ve bağlantılı olacağı bir sonraki düğümü tutan bir pointer içermelidir. StackNode isimli yapıya baktığınızda template bir T verisi ile yine stackNode tipinde bir pointer içerdiğini göreceksiniz.


Şimdi yine template bir sınıf tasarımı ile Stack veri yapısı oluşturmaya çalışalım. Stack içinde private olarak en tepedeki yani son giren elemanı tutmak ile görevli bir stackNode ve yığının eleman sayısını tutmak ile görevli bir int alanı bulunsun.


template<class T>
class MyStack
{
private:
       stackNode<T> *node; //düğüm
       unsigned int count = 0; //eleman sayısı

public:
       MyStack()  {}
       ~MyStack() {}

       void push(T element) {

             stackNode<T> *newNode = new stackNode<T>(); //yeni bir düğüm oluştur
             newNode->data = element; //veriyi düğüme ekle.

             if (node == nullptr) { //ilk eleman eklenmedi ise:
                    node = newNode;
                    count++;
                    return;
             }

             stackNode<T> *head = node; //düğümü al.
             newNode->pointer = head; //yeni elemanın işaretçisi düğüm olsun.
             node = newNode; //düğüm yeni eleman olsun.
             count++;
       }

       T pop() {

             if (node == nullptr)
                    throw exception("stack is empty!");

             stackNode<T> *top = node; //tepedeki elemanı al.
             T data = top->data; //veriyi al

             node = top->pointer; //düğüm bir önceki eleman olsun.
             delete top; //düğümü bellekten sil.

             count--;
             return data;
       }

       T peek() {

             if (node == nullptr)
                    throw exception("stack is empty!");

             return node->data;
       }

       bool hasNext() {
             return count > 0;
       }
};


Temel bir yığında push, pop ve peek fonksiyonları olmalıdır. Ayrıyeten yığın içinde eleman olup olmadığını anlamak için kullanmak üzere hashNext isimli bir fonksiyonu sınıfım içine deklare ediyorum.

LIFO mantığınca bir eleman yığın içine girdiğinde bu elemanı en üste almam gerekiyor. Dolayısıyla push fonksiyonu içinde ilk eleman içeri girmediyse yani yığın henüz boş ise yeni elemanı tepeye alıyorum. Şayet ilk eleman girdiyse ekleyenecek yeni eleman tepe elemana işaret etmeli ve tepe eleman yeni eleman olarak değiştirilmelidir. Bu durumda en son giren eleman bir önceki adımın en son elemana işaret etmek koşuluyla en tepeye alınmış olunur. Pop fonksiyonu görev gereği en tepedeki elemanı verirken bu elemanı aynı zamanda yığın içinden atmak ile görevliydi… Mantık olarak push fonksiyonunun tersi şeklinde çalışan pop fonksiyonu içinde de en tepedeki elemanı alıp bu elemanı silmeden önce elemanının işaret ettiği diğer düğümü tepe eleman olarak atamalıyım. Böylelikle bir sonraki eleman RAM uzayında kaybolmamış olacaktır. Şimdi yığın veri yapımızı test edebilmek adına book isminde bir yapı tanımlaması yoluna gidelim.


typedef struct Book
{
       string title;
       unsigned int pages;

       static Book createBook(unsigned int pages, string title) {
             Book instance = Book();
             instance.title = title;
             instance.pages = pages;
             return instance;
       }

       string toString() {
             stringstream stream;
             stream << "TITLE: " << title << " PAGES: " << pages;
             return stream.str();
       }
} book;


Book türü, kitabın ismi ve sayfa sayısını tutan birer field, book türünde bir nesne oluşturan statik bir fonksiyon ve sınıfı string olarak sınıfı üyelerini özetleyen bir toString fonksiyonu içeriyor. Her şey hazır olduğuna göre kitap türünde birkaç örneği main fonksiyonumuz içinde oluşturmakla devam edelim.


book book1 = book::createBook(300, "Kitap 1");
book book2 = book::createBook(400, "Kitap 2");
book book3 = book::createBook(500, "Kitap 3");


Üç adet kitap örneği, yığın veri yapısını test emek için yeter de artar bile... Üzerinde çalıştığım veri tipi book türünde olduğundan ötürü yığın veri yapısından bir instance alırken book türü ile çalışmak istediğimi belirtmeliyim.


MyStack<book> *stack = new MyStack<book>();
stack->push(book1);
stack->push(book2);
stack->push(book3);


MyStack<book>, book tipinde veri tutan bir Linked List içeren yığın veri yapısını ifade ediyor. Push fonksiyonu ile sırasıyla book1, book2 ve book3 yapı örneklerini yığın içine alıyorum. Bu durumda son eklenen eleman en üste alınacağından ötürü yığından çıkma hakkı öncelikli olarak book3’e ait olacaktır. Bunu test etmek adına peek fonksiyonuna başvurabiliriz. 


book book = stack->peek();
cout << book.toString() << endl;
//'TITLE: Kitap 3 PAGES: 500' yazılır.


Peek fonksiyonu koleksiyonun en tepesindeki elemanı verir ancak pop fonksiyonundan farklı olarak tepedeki elemanı koleksiyondan dışarı çıkarmaz. Şayet koleksiyonun en tepesinde bulunan elemanı alırken aynı zamanda bu elemanı yığından atmak amacında iseniz pop fonksiyonunu kullanmalısınız. Benzer bir mantık ile tüm yığın içeriğini taramak ve aynı anda yığını boşaltmak için hashNext ve pop fonksiyonları birlikte kullanılabilir.


while (stack->hasNext()) {
      cout << stack->pop().toString() << endl;
      //sırasıyla kitap 3, kitap 2 ve kitap 1'e ait bilgiler yazılır.
}


HashNext fonksiyonu yığın içinde bir eleman daha olup olmadığını döndürmek ile görevlendirilmişti. O halde bu bilgiyi döngü şartı olarak kullanırken yığının bir sonraki elemanına pop fonksiyonu ile erişmeliyim. Eğer peek fonksiyonu ile aynı sonucu ulaşmak istersem peek ile tepedeki elemanı çağırdıktan sonra pop fonksiyonunu kullanarak o elemanın dışarı çıkmasını sağlamalıyım. Aksi halde programın sonsuz bir döngü içerisine girecektir.


while (stack->hasNext())
{
      book next = stack->peek(); //peek ile tepe elemanı alıyorum.
      cout << next.toString() << endl;
      stack->pop(); //tepe elemanı dışarı çıkarıyorum.
      //sırasıyla kitap 3, kitap 2 ve kitap 1'e ait bilgiler yazılır.
}


Yığın içeriğine iterasyon yapmanın iki farklı yolunu gördünüz. Tabi ki amacınız tüm yığın içeriğini alırken yığını boşaltmak ise peek ve pop fonksiyonunun farkını gözler önüne seren bu iki kullanım şeklinden ilkini tercih etmelisiniz.


Evet bu yazımızda Stack veri yapısı ve LIFO çalışma presibi hakkında bilgi edindik. Bir sonraki yazımızda görüşene dek iyi kodlamalar diliyorum.