Stack(Yığın)
Stack(yığın), aynı türden verilerin bulunduğu lineer(doğrusal) bir veri yapısıdır. Stack, Son Giren İlk Çıkar (Last In First Out - LIFO) şekilinde çalışır yani stack'a eklenen son ögenin ilk kaldırıldığı anlamına gelir.
Last In First Out (LIFO):
Bu strateji, son eklenen ögenin ilk çıkarılacağını belirtir. Gerçek hayattan bir örnek olarak üst üste yerleştirilmiş tabak yığını düşünülebilir. En son koyduğumuz tabak en üsttedir ve en üstteki tabağı çıkardığımızda, en son konan tabak ilk çıkar diyebiliriz.
Eğer en alttaki tabağı istiorsak, önce üstteki tüm tabakları çıkartmamız gerekir. Stack(yığın) veri yapısı tam olark böyle çalışır.
Stack LIFO Prensibi
Programlama terimlerinde, bir öğeyi stack'ın üstüne koymaya push, bir öğeyi kaldırmaya ise pop denir.
Görselde, 3. öğe en sonda kalmasına rağmen, ilk olarak kaldırılmıştır.
Stack'ın Temel İşlemleri
Bir stack üzerinde farklı eylemler gerçekleştirmemizi sağlayan bazı temel işlemler vardır.
push: Bir stack'ın üstüne bir eğe ekler
pop: Bir stack'ın tepesinden bir öğeyi kaldırma
IsEmpty: Stack'ın boş olup olmadığını kontrol eder
IsFull: Stack'ın dolu olup olmadığını kontrol eder
peek: Üst öğenin değerini kaldırmadan alma
Stack Türleri
Register Stack(Kayıt Yığını)
Bu tür bir stack aynı zamanda bellek biriminde bulunan bir bellek öğesidir ve yalnızca az miktarda veriyi işleyebilir. Register stack'nın boyutu belleğe kıyasla çok küçük olduğundan, register stack'nın yüksekliği her zaman sınırlıdır.
Memory Stack(Bellek Yığını)
Bu tür bir stack, büyük miktarda bellek verisini işleyebilir. Memort stack'nın yüksekliği, büyük miktarda bellek verisi kapşadığından esnektir.
Stack Uygulaması
1. Dizi Kullanarak
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// stack'ı temsil edecek bir struct
struct Stack{
int top;
unsigned capacity;
int* array;
};
// verilen kapasitede bir stack oluşturma. Stack boyutu 0 olarak başlatılır
struct Stack* createStack(unsigned capacity){
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*) malloc(stack->capacity*sizeof(int));
return stack;
}
// top son indekse eşit olduğında stack dolu
int isFull(struct Stack* stack){
return stack->top == stack->capacity - 1;
}
// top -1'e eşit olduğunda stack boştur
int isEmpty(struct Stack* stack){
return stack->top == -1;
}
// Stack'a bir öğe ekleme, top'u 1 artırır
void push(struct Stack* stack,int item){
if(isFull(stack)) return;
stack->array[++stack->top] = item;
printf("%d stack'a eklendi\n",item);
}
// Stack'tan bir öğe kaldırma, top 1 azaltılır.
int pop(struct Stack* stack){
if (isEmpty(stack)) return INT_MIN;
return stack->array[stack->top--];
}
// üst kısmı çıkarmadan stack'ı döndürme
int peek(struct Stack* stack){
if(isEmpty(stack)) return INT_MIN;
return stack->array[stack->top];
}
int main(){
struct Stack* stack = createStack(5);
push(stack,10);
push(stack,40);
push(stack,20);
push(stack,50);
printf("%d stack'tan kaldirildi\n",pop(stack));
return 0;
}
Çıktı:
Dizi Kullanmanın Avantajları:
- Uygulaması kolay.
Dizi Kullanmanın Dezavantajları:
- Dinamik değildir, yani çalışma zamanında ihtiyaca göre büyüyüp küçülmez.
- Stack'ın toplam boyutu önceden tanımlanır.
2. Linked List Kullanarak
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// stack'ı temsil edecek bir struct
struct StackNode{
int data;
struct StackNode* next;
};
struct StackNode* newNode(int data){
struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
int isEmpty(struct StackNode* root){
return !root;
}
void push(struct StackNode** root, int data){
struct StackNode* stackNode = newNode(data);
stackNode->next = *root;
*root = stackNode;
printf("%d stack'a eklendi\n",data);
}
int pop(struct StackNode** root){
if(isEmpty(*root)) return INT_MIN;
struct StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);
return popped;
}
int peek(struct StackNode* root){
if(isEmpty(root)) return INT_MIN;
return root->data;
}
int main(){
struct StackNode* root = NULL;
push(&root,10);
push(&root,40);
push(&root,20);
push(&root,50);
printf("%d stack'tan kaldirildi\n",pop(&root));
printf("En ustteki eleman %d\n", peek(root));
return 0;
}
Çıktı:
Linked List Kullanmanın Avantajları:
- Dinamiktir, yani çalışma zamanındaki ihtiyaçlara göre büyüyebilir ve küçülebilir.
Linked List Kullanmanın Dezavantajları:
- Pointer'ların dahil olması nedeniyle ekstra bellek gerektirir.
- Stack içinde rastgele erişim mümkün değildir.
Kaynaklar:
https://www.geeksforgeeks.org/introduction-to-stack-data-structure-and-algorithm-tutorials/
https://www.digitalocean.com/community/tutorials/stack-in-c
https://www.programiz.com/dsa/stack
https://www.tutorialspoint.com/data_structures_algorithms/stack_program_in_c.htm
