[ManHunter]

Salve a tutti,

oggi cercherò di spiegarvi come realizzare una struttura dati che si comporti come uno stack. Uno stack è una struttura dati che assume un comportamento particolare durante l'estrazione dei dati. Tale comportamento è detto L.I.F.O., acronimo di Last In First Out. In parole povere, in questa struttura l'ultimo elemento inserito sarà il primo ad essere estratto.
Per operare su questa struttura, utilizzeremo due funzioni principali: push() e pop(). La funzione di push si occuperà di inserire dati all'interno dello stack mentre la funzione pop si occuperà di estrarre dati da esso. Utilizzeremo, inoltre, altre funzioni di appoggio.
Iniziamo!

Per prima cosa, creiamo la nostra struttura:

Codice:

typedef int tInfo; /*dichiariamo un tipo di dato equivalente ad un intero. Potete cambiare da intero a qualsiasi tipo vogliate, anche una struttura.*/

struct tagStack{
    tInfo *stack;
    int stkPtr;
    int capacity;
    }; /*dichiariamo una struttura dati formata da un puntatore ad un tInfo, un un indice di stack e da un intero che indica la capacità massima*/
typedef struct tagStack tStack; /*definiamo un tipo di dato equivalente alla struttura appena dichiarata*/

Implementiamo ora le funzioni che operano sul nostro stack.
Abbiamo bisogno di:
- creazione dello stack
- distruzione dello stack
- inserimento di dati
- estrazione di dati
- funzioni di appoggio

Creazione stack - tStack* stackCreate( int );

Codice:

tStack* stackCreate( int ){
    tStack* tmp;

    tmp->stack = ( tInfo * ) malloc( size * sizeof( tInfo ) );
    tmp->capacity = size;
    tmp->stkPtr = 0;

    return tmp;
}

Distruzione stack - tStack* stackDelete( tStack * );

Codice:

tStack* stackDelete( tStack *stack ){
    stack->capacity = 0;
    stack->stkPtr = 0;
    free(stack);

    return stack;
}

Inserimento dati - void push( tStack*, tInfo );

Codice:

void push( tStack *stack, tInfo info ){
    stack->stack[stack->stkPtr] = info;
    stack->stkPtr++;
}

Estrazione dati - tInfo pop( tStack* );

Codice:

tInfo pop( tStack *stack ){
    stack->stkPtr--;
    return stack->stack[stack->stkPtr];
}

Funzione predicativa - bool isEmpty( tStack* );

Codice:

bool isEmpty( tStack *stack ){
    if( stack->stkPtr <= 0 )
        return true;
    return false;
}

Funzione predicativa - bool isFull( tStack* );

Codice:

bool isFull( tStack *stack ){
    if( stack->stkPtr == stack->capacity )
        return true;
    return false;
}

Queste dovrebbero essere le funzioni necessarie: nulla toglie che potete implementarne di altre...
Inserisco anche il progetto completo, compreso di main() per testare il funzionamento delle funzioni.

- stack.h -

Codice:

#ifndef STACK_H
#define STACK_H

#include <stdlib.h>
#include <stdbool.h>

typedef int tInfo;

struct tagStack{
    tInfo *stack;
    int stkPtr;
    int capacity;
    };
typedef struct tagStack tStack;

tStack* stackCreate( int );
tStack* stackDelete( tStack * );

tInfo pop( tStack * );
void push( tStack *, tInfo );

bool isEmpty( tStack * );
bool isFull( tStack * );

#endif

- stack.c -

Codice:

#include "stack.h"

tStack* stackCreate( int size ){
    tStack* tmp;

    tmp->stack = ( tInfo * ) malloc( size * sizeof( tInfo ) );
    tmp->capacity = size;
    tmp->stkPtr = 0;

    return tmp;
}

tStack* stackDelete( tStack *stack ){
    stack->capacity = 0;
    stack->stkPtr = 0;
    free(stack);
    return stack;
}

tInfo pop( tStack *stack ){
    stack->stkPtr--;
    return stack->stack[stack->stkPtr];
}

void push( tStack *stack, tInfo info ){
    stack->stack[stack->stkPtr] = info;
    stack->stkPtr++;
}

bool isEmpty( tStack *stack ){
    if( stack->stkPtr <= 0 )
        return true;
    return false;
}

bool isFull( tStack *stack ){
    if( stack->stkPtr == stack->capacity )
        return true;
    return false;
}

- main.c -

Codice:

#include <stdio.h>
#include "stack.h"

int main(){
    tStack *stack;
    int scelta, size;
    tInfo info;

    printf( "\t\tGestione di uno stack\n____________________________________________________\n\n" );
    printf( "Dimensione stack\t>" );
    scanf( "%d", &size );

    stack = stackCreate( size );

    do{
        system( "CLSC" );
        printf( "Scegli cosa fare:\n\n" );
        printf( "1) Inserire elemento\n" );
        printf( "2) Prelevare elemento\n" );
        printf( "3) isEmpty\n" );
        printf( "4) isFull\n" );
        printf( "5) Dealloca lista\n" );
        printf( "6) Esci\n\n" );
        printf( "__________________________________________\n\n" );
        scanf( "%d", &scelta );

        switch( scelta ){
            case 1:
                printf( "Informazione da inserire\t>" );
                scanf( "%d", &info );
                push( stack, info );
                printf( "\n" );
                break;
            case 2:
                printf( "L'elemento prelevato \212:\t%d\n", pop( stack ) );
                break;
            case 3:
                if( isEmpty( stack ) )
                    printf( "Lo stack \212 vuoto.\n" );
                else
                    printf( "Lo stack non \212 vuoto.\n" );
                break;
            case 4:
                if( isFull( stack ) )
                    printf( "Lo stack \212 pieno.\n" );
                else
                    printf( "Lo stack non \212 pieno.\n" );
                break;
            case 5:
                stack = stackDelete( stack );
                if( stack == NULL )
                    printf( "Stack deallocato\n" );
                else
                    printf( "Stack non deallocato\n" );
                break;
            case 6:
                printf( "Hai scelto di uscire!" );
                return EXIT_SUCCESS;
        }
        system( "PAUSE" );
    }while( scelta != 6 );

    return EXIT_SUCCESS;
}

E questo è tutto. Per eventuali malfunzionamenti o consigli potete contattarmi in privato oppure scrivere qui di seguito.



Saluti.

[friskon]

ancora grazie del gran contributo

[Skyline]

Che lavoro... xD

Bel post e sopratutto utile.

[steve]

Solitamente per gli stack si usa l'allocazione dinamica: con un realloc (da verificare, sono abbituato ad usare il new del c++) ad ogni pop e push si evita di assegnare delle dimensioni alla inizializzazione.

[ManHunter]

Solitamente per gli stack si usa l'allocazione dinamica: con un realloc (da verificare, sono abbituato ad usare il new del c++) ad ogni pop e push si evita di assegnare delle dimensioni alla inizializzazione.

Capisco... Sto cercando di applicare solamente quello che imparo a lezione all'università... Per ora tale argomento ci è stato presentato così, per questo cerco di non discostarmi troppo dall'esposizione del professore.
La funzione realloc non l'abbiamo ancora utilizzata, utilizziamo la malloc per l'allocazione dinamica...