Stack Nedir?
Stack,bir tür veri yapısıdır.Özetle bir konteynerdir.Modern bilgisayar sistemlerinin her seviyesinde kullanılabilmektedir.Ayrıca *LIFO kuralına göre çalışan bir data tipidir.Stackleri,üst üste sıralanmış tabaklar olarak düşünebiliriz;Yıkandıktan sonra tabak en üste konur,yemek koyabilmek için en üstteki tabak alınır.
Hardware Stack
Stack,memory de sabit bir bölümde,değişken boyutlarda bulunur.Genellikle başlangıçta stack boyutu sıfırdır.Stack boyutu sıfır iken stack pointer,stack başlangıç noktasının adresini tutar;Stack boyutu değiştiğinde ise stack pointer, her zaman aktif pencerelerin adresini tutar.Örneğin; Boyutu sıfır olan bir stack ele alırsak ve başlangıç adresinin 100 olduğunu varsayarsak;Eklediğimiz her veri boyutu kadar stack boyutu artıcaktır.Aynı zamanda stack pointer gelinen son adresi gösterecektir.
Stack(wikipedia)
Software Stack
Yazılım açısından bakıldığı zaman stack,üst seviye programlama metodudur.Stack kullanarak verilerimizi belirli sırada saklayabilir,tekrar kullanabiliriz.Temiz bir çöp kutusu hayal edersek,içine ne atarsak atalım,elimizle içinden çekip alabileceğimiz öge her zaman en son attığımız olucaktır.Bu düşünceden yola çıkarsak,aklımızda bazı fikirler oluşucaktır.Örneğin;
- pop (veri çıkarma)
- push(veri koyma)
- top(en üstteki veriye ulaşma)
- empty(konteynerimizin boş olup olmadığını kontrol etme)
Elbette bu işlevsellikler dışında stack kurallarını bozmadan,aklımıza gelen fonksiyonları ekleyebiliriz.Ancak print() fonksiyonu bu kuralı ne kadar ihlal etse de kullanmaya ihtiyaç duyabiliriz.
Özetlememiz gerekirse;
- Stack yapısı kurabilir,bu yapının bazı node(veri blokları) nı tutmasına,onlar arasında gezmesine izin verebiliriz.
- Stack yapısının boş olup olmadığını öğrenebilir,en son koyduğumuz veri blokunun içeriğini çekebiliriz.
- Stack yapısının en üstüne ekleme yapabilir ve ya en üstteki veri blokunu çekebiliriz.
- Stack yapısının içinde tek tek gezerek bütün veri bloklarının tuttuğu verileri yazdırabiliriz.
- Veri bloklarında sadece veri tutabiliriz,bu verileri döndürebiliriz.
- Veri blokları arasında bağlantı oluşturabilir,böylece bloklar arasında gezmemizi kolaylaştırabiliriz.
gibi bazı fikirlerimizi belirleyip bunları requirement(ihtiyaç) listemizde tutarak, kodumuzu fazla komplex düşünmeden yazmaya başlayabiliriz.
//Author:Murat UNAL - murproject@gmail.com
//Language:C
#include <stdio.h>
#include <conio.h>;
#define maxElement 10
//
//Type Definition
//
typedef int elemType;
//
//Node:data container
//
struct Node{
elemType data;//node data
struct Node *next;//next pointer
};
//
//Stack:Node container
//
struct Stack{
elemType size;//size of Stack
struct Node *top;//next pointers
};
//
//Functions for structures
// //
//initiliaze(void ):creates stack,initilies it's first data and returns it to main.(data type:struct Stack),(arguements:0)
//
struct Stack initiliazeStack(void){
struct Stack *mainStack;
mainStack=(struct Stack *)malloc(sizeof(struct Stack));
mainStack->size=0;
mainStack->top=NULL;
return *mainStack;
}
//
//push(struct Stack *,elemType ):will push data into stack max 10,create new node and initiliaze data into node's data. (data type:void),(arguements:2)
//
void push(struct Stack *mainStack,elemType data){
if(mainStack->size<maxElement){
struct Node *newNode=(struct Node *)malloc(sizeof(struct Node));
newNode->data=data;
printf("\npushing into stack...\t%d\n",newNode->data);
if(isEmpty(mainStack)){ //if it's the first element in stack
newNode->next=NULL;
mainStack->top=newNode;
}
else{
newNode->next=mainStack->top;
mainStack->top=newNode;
}
mainStack->size+=1;
}
else{
printf("\nYou can't push into stack more than %d element",maxElement);
}
}
//
//isEmpty(struct Stack*):will check stack if it has got any element inside and return 1/0.(data type:elemType),(arguements:1)
//Bug:datatype of function can be boolean.
//
elemType isEmpty(struct Stack*mainStack){
if(mainStack->top==NULL)
return 1;
else return 0;
}
//
//printStack(struct Stack*):will print the all node's data from top to bottom.(data type:void),(arguements:1)
//
void printStack(struct Stack*mainStack){
printf("\nprinting the stack...\n");
if(isEmpty(mainStack)) // if stack is empty
printf("\nYour Stack is Empty at the moment...\n");
else if (mainStack->size==1)//if just one element
printf("\n%d\n",mainStack->top->data);
else{
struct Node *walkerNode=(struct Node *)malloc(sizeof(struct Node));
for(walkerNode=mainStack->top;walkerNode->next!=NULL;walkerNode=walkerNode->next){
printf("\n%d\n",walkerNode->data);
}
printf("\n%d\n",walkerNode->data); //for last node's data preview
}
}
//
//pop(struct Stack*):will pop the top element from stack and preview it.(data type:elemType),(arguements:1)
//
elemType pop(struct Stack* mainStack){
if(isEmpty(mainStack)){// if stack is empty
printf("\nNot able to pop.Your Stack is Empty at the moment...\n");
}
else if(mainStack->size==1){//if just one element
printf("\npoping from stack...\t%d\n",mainStack->top->data);
free(mainStack->top);
mainStack->top=NULL;
mainStack->size-=1;
}
else{
struct Node* walkerNode=(struct Node*)malloc(sizeof(struct Node));
walkerNode=mainStack->top;
mainStack->top=walkerNode->next;
printf("\npoping from stack...\t%d\n",walkerNode->data);
free(walkerNode);
mainStack->size-=1;
}
}
//
//sizeOfStack(struct Stack*):will return the size of stack.(data type: elemtype),(arguements:1)
//
elemType sizeOfStack(struct Stack* mainStack){
return mainStack->size;
}
//
//Client(User):
//
int main(){
struct Stack *mainStack;
mainStack=(struct Stack *)malloc(sizeof(struct Stack));
*mainStack=initiliazeStack();
pop(mainStack);
push(mainStack,10);
pop(mainStack);
printStack(mainStack);
push(mainStack,10);
pop(mainStack);
push(mainStack,20);
pop(mainStack);
push(mainStack,30);
pop(mainStack);
push(mainStack,50);
pop(mainStack);
pop(mainStack);
pop(mainStack);
push(mainStack,50);
push(mainStack,60);
push(mainStack,70);
printStack(mainStack);
pop(mainStack);
pop(mainStack);
printStack(mainStack);
getch();
return 0;
}
Güvenlik
C dilinin veri ve prosedür çağrılarının geri dönüş adresleri için paylaşımlı stack kullanıyor olması ve gelen verinin boyutunu doğrulamaması sebebi ile güvenlik açığının meydana gelmesi mümkündür.Taşınan ve ya girilen veri, stack üzerinde yanlış bölüme aktarılırsa;Stack boyutunun kabul edemeyeceği bir veri girilmeye çalışılırsa,bu adreslerin bozulması,kaybolması ve programın düzgün çalışamaması mümkündür.
*LIFO(last in-first out):son giren,ilk çıkar.
murproject
