Stack (Yığın) Veri Yapısı [Rehber]

Stack (Yığın) Nedir: Bilgisayar bilimlerinde ‘son giren ilk çıkar’ felsefesiyle çalışan ve verilere sadece bir uçtan erişimin sağlandığı doğrusal veri yapısına verilen isimdir. Yığın veri tipi günümüz bilgisayar programlarında ve bilgisayar dizgelerinde sıkça kullanılan veri yapılarından bir tanesidir.

Üst üste konulan kitaplar, üst üste konulan bozuk paralar ve üst üste konulan kutular günlük yaşamdaki yığın veri yapısına örnek olarak verilebilir. Bilgisayar bilimlerindeki yığınlar da tam olarak aynı şeydir ve gerçek hayata paralel bir prensiple çalışmaktadır. İşte bu yazıda da güncel örnekler eşliğinde, enine boyuna bu konuyu ele alacağız.

Stack (Yığın) Veri Yapısı [Rehber]

1- Stack Veri Yapısının Özellikleri Nelerdir?

.#. Yığın elemanlarına erişim sağlama konusunda “Last-In-First-Out (LIFO)” prensibi geçerlidir. Yani son giren eleman ilk başta çıkar, ilk giren eleman en sonda çıkar. Bunu üst üste dizilmiş kitapları en üstten yani en son konulandan almaya başlamaya benzetebiliriz. Yani stack veri yapısının çalışma prensibi aşağıdaki görseldeki gibidir:

.#. Yığınlarda da tıpkı dizilerdeki ve bağlı listelerdeki gibi çok boyutlu veri yapıları oluşturulabilir. Yığınlara farklı türden elemanlar eklemesi yapılabilir fakat bu durum her programlama dili için geçerli değildir. Ayrıca farklı veri yapılarıyla birlikte de kullanılabilir.

.#. Yığınlar diziler ve bağlı listeler kullanılarak oluşturulabilir. Dizilerle oluşturulan yığınlar sabit boyutlu iken bağlı listelerle oluşturulan yığınlar dinamik boyutludur.

.#. Dizilerle ve bağlı listelerle oluşturulan yığınların operasyonları arasında zaman kompleksliği açısından ciddi bir fark yoktur! Fakat dizilerle oluşturulan yığınlar bellek kullanımı açısından daha avantajlıdır. İki türün de operasyonların zaman komplekslikleri aşağıdaki tablodaki gibidir:

Yığın Operasyonları	Dizi Tabanlı Yığın	Bağlı Liste Tabanlı Yığın
push(T& Eleman)	O(1)	O(1)
pop()	O(1)	O(1)
peek()	O(1)	O(1)
reverse()	O(n)	O(n)
size()	O(1)	O(1)
isEmpty()	O(1)	O(1)
isFull()	O(1)	–
display()	O(n)	O(n)

2- Stack Nerelerde Kullanılır?

2.1 – Günlük Hayattan Örnekler

• Kargo kolileri (En üstteki koli ilk başta alınır.)
• Bulaşıklar (En üstteki tabak ilk başta yıkanır.)
• Hanoi kuleleri (Matematiksel zeka bulmacasıdır.)
• CD kutusu (En üstteki CD ilk başta alınır.)
• Dizilmiş madeni paralar (Teorik olarak yığındır.)
• Üst üste konmuş kitaplar (Teorik olarak yığındır.)

2.2 – Bilgisayarlar Dünyasından Örnekler

• Fonksiyon çağrıları ve özyinelemeli fonksiyonların inşası (Örneğin işletim sistemlerinde hafıza yönetimi)
• En son kullanılan dosya, öge, araç vb. bileşenlerin kaydını tutma (Örneğin internet tarayıcılarının tarihçeleri)
• Kod düzenleyicilerde syntax hatalarını tespit etme (Özellikle parantezlerle ilgili hatalar, örneğin:)

İfade	Dengeli Mi?
( )	Evet
{ ( ) ( ) }	Evet
{ ( ) ( )	Hayır
] ( ) ]	Hayır
{ )	Hayır

• Geri izleme işlemleri (Örneğin labirent çözümü gibi uygulamalarda hatalı adımlarda geri dönmek amacıyla yığın kullanımı işleri kolaylaştıracaktır)
• İşletim sistemleri başta olmak üzere zamanlama işlemleri
• Program yürütme işlemleri (execution) ve ayrıştırma işlemleri (parsing)
• Algoritma verimliliğini arttırma (Örneğin Graham tarama algoritması ve hisse senedi aralığı sorununun çözümü)
(Ayrıca Bakınız: Algoritma Nedir? Algoritma Örnekleri)

• Ters çevirme işlemleri
• Onluk tabandaki sayıyı ikilik tabandaki sayıya çevirme
• Postfix, prefix ve infix ifadelerini değerlendirme
• Yapılan işlemi geri alma ve yeniden yapma (undo & redo) işlemlerinin hafıza yönetimi (Örneğin tarayıcıların sekmelerinde ileri geri gitme işlemleri)

3- Stack’in Avantajları ve Dezavantajları Nelerdir?

3.1 – Stack Kullanmanın Avantajları Nelerdir?

✅ Dizilerde bellek dinamik olarak ayrılamaz ve bağlı listelerde de bellek kullanımı çok verimli değildir. Fakat yığınlarda verimli bir şekilde bellek dinamik olarak ayırılabilir. Bu durum da daha düşük donanım gereksinimi anlamına gelir.

✅ Dizilerde yeni bir eleman eklemek veya var olan bir elemanı silmek çaba gerektirirken, yığınlarda bu işlem kolaylıkla yapılabilir.
✅ Yığınlar öğrenmesi, implement etmesi ve uygulaması kolay olan veri yapılarıdır.

✅ Yığınlar doğru yerlerde doğru amaçlar için kullanıldıkları taktirde işleri önemli ölçüde kolaylaştırabilirler.
✅ Statik ve dinamik boyutlu olarak tasarlanabilir. Üstelik dinamik boyutlu olarak tasarlandığında algoritmanın zaman kompleksliği artmaz.

3.2 – Stack Kullanmanın Dezavantajları Nelerdir?

❌ Dinamik bellek tahsisi sebebiyle, tüm bellek alanının kullanılmaması halinde bellek alanı israfına sebep olunabilir.
❌ Dinamik boyutlu yani bağlı liste tabanlı yığınların bellek gereksinimi yüksektir.

❌ Yığınlar esnek veri yapıları değildir (not-flexibile), ayrıca yığınlar ölçeklenebilir veri yapıları da değildir (not-scalable). Bu özelliklerinden dolayı doğru yerlerde ve dikkatli bir şekilde kullanılmaları önem taşımaktadır.
❌ Yığınlarda istenilen indexler üzerinde kopyala yapıştır işlemleri yapmak diğer veri yapılarına göre daha zor ve daha komplekstir.

4- Stack Fonksiyonları Nelerdir?

📌 Push(T& Eleman):
• Parametre olarak alınan elemanı yığına eklemek için kullanılır. (Push: İttirmek, sıkıştırmak)
• Push fonksiyonu herhangi bir değer döndürmez.

📌 Pop():
• Son eklenen elemanı yığından eleman çıkarmak için kullanılır. (Pop: Çıkmak)
• Son eklenen eleman çıkarılacağı için fonksiyon parametresizdir.
• Pop fonksiyonu herhangi bir değer döndürmez.

📌 Peek():
• Son elemana ve değerlerine erişmek için kullanılır. (Peek: Gözetlemek)
• Fonksiyon parametre içermez. Ayrıca son elemanı döndürür.
• Peek() fonksiyonu bazı kaynaklarda Top() fonksiyonu olarak da geçer.

📌 Reverse():
• Yığındaki bileşenlerin sırasını ters çevirmek için kullanılır. (Reverse: Tersine çevirmek)
• Fonksiyon parametre içermez. Ayrıca herhangi bir değer döndürmez.

📌 getSize():
• Yığının maksimum kapasitesini öğrenmek için kullanılır. (Size: Boyut)
• Bu metot sadece sabit boyutlu yani dizi tabanlı yığınlarda bulunmaktadır.
• Fonksiyon parametre içermez. Ayrıca sayısal bir değer döndürür.

📌 isFull():
• Yığının tamamen dolu olup olmadığını öğrenmek için kullanılır. (Full: Dolu)
• Bu metot sadece sabit boyutlu yani dizi tabanlı yığınlarda bulunmaktadır.
• Fonksiyon parametre içermez. Ayrıca bool türünde bir değer döndürür.

📌 isEmpty():
• Yığının tamamen boş olup olmadığını öğrenmek için kullanılır. (Empty: Boş)
• Fonksiyon parametre içermez. Ayrıca bool türünde bir değer döndürür.

📌 display():
• Yığın elemanlarını konsola yazdırmak için kullanılan metottur. (Display: Görüntülemek)
• Eğer yığın sınıfı farklı sınıfların nesneleri için kullanılacak ise, bu metot nesnelere göre güncellenmelidir.

5- Stack İmplementasyonu Nasıl Yapılır?

5.1 – Dizi Tabanlı Yığın (Array Based Stack)

/*
 * Dosya: Stack.h
 * Author: technogezgin.com
 */

using namespace std;

template <typename T>
class Stack {
	private:
		// Yığın Bileşenleri (Properties)
		T* elemanlar;
		int ust;
		int boyut;

	public:
		Stack(const int x); // Yapıcı metot (Constructor)
		~Stack(); // Yıkıcı metot (Destructor)

		// Yığın Fonksiyonları (Methods)
		void push(const T& eleman);
		void pop();
		T& peek();
		void reverse();
		int getSize();
		bool isEmpty();
		bool isFull();
		void display();
};

/*
 * Dosya: Stack.cpp (Array İmplementasyonu)
 * Author: technogezgin.com
 */

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

#include "Stack.h"

template <typename T>
Stack<T>::Stack(const int x) {
    elemanlar = new T[x];
    ust = 0;
    boyut = x;
}

template <typename T>
Stack<T>::~Stack() {
    delete[] elemanlar;
}

template <typename T>
void Stack<T>::push(const T& eleman){
    if(isFull()){
        cout << "Hata: Dolu yığına eleman eklenemez!" << endl;
    } else {
        elemanlar[ust] = eleman;
        ust += 1;
    }
};

template <typename T>
void Stack<T>::pop(){
    if(isEmpty()) {
        cout << "Hata: Boş yığından eleman çıkarılamaz!" << endl;
    } else {
        // Diziyi kaydırarak elemanı silme çok daha kompleks bir işlemdir.
        ust -=1;
    }
};

template <typename T>
T& Stack<T>::peek(){
    return elemanlar[0];
};

template <typename T>
void Stack<T>::reverse(){
    for (int bas = 0, son = ust - 1; bas < son; bas++, son--) {
        swap(elemanlar[bas], elemanlar[son]);
    }
};

template <typename T>
int Stack<T>::getSize(){
    return boyut;
};

template <typename T>
bool Stack<T>::isEmpty(){
    return ust == 0;
};

template <typename T>
bool Stack<T>::isFull(){
    return boyut == ust;
};

template <typename T>
void Stack<T>::display(){
    if(isEmpty()){
        cout << "Yığın Elemanları: () (Yığın boş!)" << endl;
    }
    else {
        cout << "Yığın Elemanları: (";
        for(int i=0; i<ust; i++){
           cout << elemanlar[ust-i-1] << ", ";
        }
        cout << ")" << endl;
    }
};

5.2 – Bağlı Liste Tabanlı Yığın (Linked-List Based Stack)

/*
 * Dosya: Stack.h
 * Author: technogezgin.com
 */

using namespace std;

template <typename T>
class Stack {
	private:
		// Yığın Bileşenleri (Properties)
		struct ListNode {
			T deger;
			ListNode* sonrakiDeger;
			}; // Düğümler (Node) İle Oluşturulan Linked List
		ListNode* ilkNode;
		int boyut = 0;

	public:
		Stack(); // Yapıcı metot (Constructor)
		~Stack(); // Yıkıcı metot (Destructor)

		// Yığın Fonksiyonları (Methods)
		void push(const T& eleman);
		void pop();
		T& peek();
		void reverse();
		bool isEmpty();
		bool isFull();
		void display();
};

/*
 * Dosya: Stack.cpp (Linked List İmplementasyonu)
 * Author: technogezgin.com
 */

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

#include "Stack.h"

template <typename T>
Stack<T>::Stack() {
    ilkNode=NULL;
    boyut=0;
}

template <typename T>
Stack<T>::~Stack() {
    struct ListNode* temp;
    while (ilkNode != NULL){
        temp = ilkNode->sonrakiDeger;
        delete ilkNode;
        ilkNode = temp;
    }
}

template <typename T>
void Stack<T>::push(const T& eleman){
    ListNode *temp = new ListNode();
    temp->deger = eleman;
    if(ilkNode  == NULL){
        temp->sonrakiDeger = NULL;
    } else {
        temp->sonrakiDeger = ilkNode;
    }
    ilkNode = temp;
    boyut += 1;
};

template <typename T>
void Stack<T>::pop(){
    if(ilkNode==NULL)
        cout << "Hata: Boş yığından eleman çıkarılamaz!" << endl;
    else {
        ilkNode = ilkNode->sonrakiDeger;
        boyut -=1;
    }
};

template <typename T>
T& Stack<T>::peek(){
    return ilkNode->deger;
};

template <typename T>
void Stack<T>::reverse(){
    ListNode* simdikiNode = ilkNode;
    ListNode *onceki = NULL, *sonraki = NULL;
    while (simdikiNode != NULL) {
        sonraki = simdikiNode->sonrakiDeger;
        simdikiNode->sonrakiDeger = onceki;
        onceki = simdikiNode;
        simdikiNode = sonraki;
    }
    ilkNode = onceki;
};

template <typename T>
bool Stack<T>::isEmpty(){
    return boyut == 0;
};

// isFull() fonksiyonu dinamik boyutlu yığınlarda kullanılamaz!

template <typename T>
bool Stack<T>::getSize(){
    return size;
};

template <typename T>
void Stack<T>::display(){
    struct ListNode* ptr;
    if(ilkNode==NULL){
        cout << "Yığın Elemanları: () (Yığın boş!)" << endl;
    }
    else {
        ptr = ilkNode;
        cout << ("Yığın Elemanları: (");
        while (ptr != NULL) {
            cout << ptr->deger << ", ";
            ptr = ptr->sonrakiDeger;
        }
        cout << ")" << endl;;
    }
};

5.3 – Çoklu Yığın (Multiple Stack)

Yığınların içerisinde yığınlar oluşturarak tıpkı çok boyutlu dizilerde olduğu gibi çok boyutlu yığınlar da oluşturabilirsiniz. Tabi böyle bir kullanıma genellikle küçük ve orta çaplı projelerde ihtiyaç duyulmamaktadır.

6- Stack Konusunda Öğrendiklerimizi Test Edelim

📌 Soru-1: Yığınlarla ilgili aşağıda verilen ifadelerden hangileri doğrudur?
1- İlk giren ilk çıkar prensibine göre çalışan bir veri yapısıdır. (FIFO)
2- Fonksiyon çağrıları, hisse senedi aralığı sorununun çözümü gibi çeşitli amaçlarla kullanılır.
3- Dizi ile yapılanlar dinamik, bağlı liste ile yapılanlar statik boyutludur.
4- Dizi ve bağlı liste ile yapılanların hafıza gereksinimi aynıdır.

(A) Yalnız-2
(B) 1 ve 2
(C) 2 ve 3
(D) 1, 2 ve 4
Cevap: (A)

📌 Soru-2: Stack metotları ve “son giren ilk çıkar” prensibi ile ilgili aşağıda verilen ifadelerden hangileri yanlıştır? (Node: düğüm)
1- Dizi ve bağlı liste ile yapılanların temel metotlarında ciddi zaman kompleksliği farkı vardır.
2- Bağlı liste ile yapılanın push() operasyonunda node başa ekleniyorsa, pop() operasyonunda node sondan silinir.
3- Bağlı liste ile yapılanın push() operasyonunda node sona ekleniyorsa, pop() operasyonunda node baştan silinir.

(A) Yalnız-1
(B) 1 ve 2
(C) 1 ve 3
(D) 1, 2, 3
Cevap: (D)

📌 Soru-3: Aşağıda yığın veri yapısıyla yapılabilecek işlemler ile ilgili bir kod bloğu verilmiştir. Bu kod bloğu çalıştırıldığına konsola yazdırılacak olan çıktı aşağıdaki şıklardan hangisinde doğru bir şekilde verilmiştir?

(A) 2 22 66
(B) 2 22 44
(C) 66 22 2
(D) 44 22 2
Cevap: (C)

📌 Soru-4: Aşağıda stack veri yapısı ile ilgili iki farklı kod bloğu verilmiştir. Bu kod blokları ile ilgili olarak aşağıdaki ifadelerden hangisi yanlıştır?

(A) İlk kod bloğu hiç durmadan çalışır. (Does not halt!)
(B) İkinci kod bloğu, kodları işlemesi bitince durur.
(C) İkinci kod bloğu ’10 9 8 7 6 5 4 3 2 1′ çıktısını verir.
(D) İlk kod bloğu konsola hata mesajı bastırır.
Cevap: (D)

📌 Soru-5: Yığın veri tipinin kullanıldığı bir fonksiyon aşağıda verilmiştir. Fakat bu fonksiyonun kullanım amacı bilinmemektedir. Aşağıdaki fonksiyon ne işe yaramaktadır?

(A) N’in ikili tabandaki gösterimini yazdırır.
(B) N’in ikili tabandaki gösterimini ters sırayla yazdırır.
(C) Log(n) ifadesinin değerini yazdırır.
(D) Log(n) ifadesinin değerini ters sırayla yazdırır.
Cevap: (A)

📌 Soru-6: Aşağıda sahte kod formunda yığın veri yapısının kullanıldığı bir algoritma verilmiştir.
Adım-1: Karakterlerden oluşan bir yığın tanımlanır.
Adım-2: Kelimede okunmamış karakterler olduğu sürece karakter okunur. Ardından yığına eklenir.
Adım-3: Yığın boş olmadığı sürece pop() metodu çağırılarak karakterler konsola yazdırılır.
Eğer bu algoritma “technogezgin” girdisi ile çalıştırılırsa, algoritmanın vereceği çıktı ne olur?

(A) tttttttttttt
(B) nigzegonhcet
(C) technogezgin
(D) nnnnnnnnnnnn
Cevap: (B)

📌 Soru-7 (Gerçek Yaşam Uygulaması): Bir parantez dizisinin dengeli olup olmadığını test etmesi beklenen buglu bir algoritma aşağıda sözde kod formunda verilmiştir. Bu algoritma aşağıdaki parantez dengesiz karakter dizilerinden hangisinin dengeli olduğunu düşünür?
(Ayrıca Bakınız: Bug Nedir? Debugging Nasıl Yapılır? [Rehber])

(A) ((())
(B) ())(()
(C) (()()))
(D) (()))()
Cevap: (A)