Strutture Dati – Lo Stack
Ciao, oggi impareremo cosa è una struttura dati di tipo Stack, la sua implementazione con un Array in C, ed anche l’implementazione dinamica. Inoltre vedremo anche l’ambito di utilizzo.
Implementazione dello Stack usando gli Array
Uno Stack è una struttura dati che lavora sul principio LIFO (last in first out, ovvero l’ultimo ad entrare è il primo che esce).
Nel mondo informatico uno Stack può essere usato in molte applicazioni come ad esempio l’analisi della sintassi delle espressioni, nella gestione a run-time della memoria (usata nella Java virtual machine) e nell’intelligenza artificiale nella soluzione dei problemi tramite ricerca.
Operazioni sullo Stack
Push e pop sono le operazioni previste per l’inserimento e la rimozione di un elemento nello stack.
Codice per l’implementazione con Array
Di seguito il codice sorgente in C che mostra la struttura dati a Stack. Potete scaricarla e provarla sul vostro Pc.
Questo è l’header, salvatelo in un file chiamato “stack.h”
void push(int *s,int* top, int element);
int pop(int *s,int *top);
int full(int *top,const int size);
int empty(int *top);
void init(int *top);
Questa è l’implementazione dello stack, salvatela in un file chiamato “stack.c”
/*
initialize stack pointer
*/
void init(int *top)
{
*top = 0;
}
/*
push an element into stack
precondition: the stack is not full
*/
void push(int *s,int* top, int element)
{
s[(*top)++] = element;
}
/*
pop an element from stack
precondition: stack is not empty
*/
int pop(int *s,int *top)
{
return s[–(*top)];
}
/*
report stack is full nor not
return 1 if stack is full, otherwise return 0
*/
int full(int *top,const int size)
{
return *top == size ? 1 : 0;
}
/*
report a stack is empty or not
return 1 if the stack is empty, otherwise return 0
*/
int empty(int *top)
{
return *top == 0 ? 1 : 0;
}
Questo è il file di test, salvatelo come “teststack.c”
#include
#include
#include “stack.h”
#define size 3
void main()
{
int top,element;
int stack[size];
// initialize stack
init(&top);
// push elements into stack
while(!full(&top,size)){
element = rand();
printf(“push element %d into stack\n”,element);
push(stack,&top,element);
//press enter to push more
getchar();
}
printf(“stack is full\n”);
// pop elements from stack
while(!empty(&top)){
element = pop(stack,&top);
printf(“pop element %d from stack\n”,element);
//press enter to pop more
getchar();
}
printf(“stack is empty\n”);
getchar();
}
Implementazione Dinamica di uno Stack
Questa è un’altra versione di una struttura dati di tipo Stack. Con questa versione la dimensione dello Stack è dinamica e determinata a run-time.
Salvate il codice dell’header in un file chiamato “linkedstack.h”
int empty(struct node *s);
struct node* push(struct node *s,int data);
struct node* pop(struct node *s,int *data);
void init(struct node* s);
Salvate il codice della struttura dello stack dinamico nel file “linkedstack.c”
#include
struct node{
int data;
struct node* next;
};
void init(struct node* s){
s = NULL;
}
struct node* push(struct node* s,int data)
{
struct node* tmp = (struct node*)malloc(sizeof(struct node));
if(tmp == NULL){
// no memory available
exit(0);
}
tmp->data = data;
tmp->next = s;
s = tmp;
return s;
}
struct node* pop(struct node *s,int *element)
{
struct node* tmp = s;
*element = s->data;
s = s->next;
free(tmp);
return s;
}
int empty(struct node* s){
return s == NULL ? 1 : 0;
}
Ed infine il file per il test “testlinkedstack.c”
#include
#include
#include “linkedstack.h”
void main()
{
struct node* head = NULL;
int size,element,counter = 0;
/*
stack size is dynamic and
specified at runtime
*/
printf(“Enter stack size:”);
scanf(“%d”,&size);
printf(“Push elements to stack\n”);
init(head);
while(counter < size)
{
getchar();
element = rand();
printf(“push element %d into stack\n”,element);
head = push(head,element);
counter++;
}
printf(“Pop elements from stack\n”);
while(0 == empty(head))
{
head = pop(head,&element);
printf(“pop element %d from stack\n”,element);
getchar();
}
getchar();
}