如何使用C语言写: Generic Stack


		实现一个简单的栈,并非难事,但是使用C语言编写一个GenericStack还是有挑战.本文使用自增长数组的方式实现栈.同样遵循上篇("genericlist篇")所写的C语言泛型设计的原则,再次不赘述.
 
模型
------------------------------------------------------------------------------------------------------------------------
 

 
核心代码
------------------------------------------------------------------------------------------------------------------------
完整代码详见我的github(https://github.com/gnudennis/ds_c)(genric-stack.h generic-stack.c generic-stack-test.c)
 
0. Generic Stack定义
[cpp]  
typedef void *ElementAddr;  
typedef void (*PfCbFree)(ElementAddr);  
  
typedef struct StackRecord  
{  
        ElementAddr *array;  
        int     elemsize;  
        int     loglength;  
        int     alloclength;  
        PfCbFree    freefn;  
} *Stack;  
 
1. API的设计
[cpp]  
/* Create a new stack */  
Stack stack_create(int elemsize, PfCbFree freefn);  
  
/* Dispose the stack */  
void stack_dispose(Stack stk);  
  
/* Make the given stack empty */  
void stack_make_empty(Stack stk);  
  
/* Return true if the stack is empty */  
int stack_is_empty(Stack stk);  
  
/* Insert a new element onto stack */  
void stack_push(Stack stk, ElementAddr elemaddr);  
  
/* Delete the top element off the stack */  
void stack_pop(Stack stk);  
  
/* Fetch the top element from the stack */  
void stack_top(Stack stk, ElementAddr elemaddr);  
  
/* Fetch & Delete the top element from the stack */  
void stack_top_and_pop(Stack stk, ElementAddr elemaddr);  
将pop和top分开的目的是为了满足不同的需求,同时添加了stack_top_and_pop作为补充.
 
2.实现
[cpp]  
#define MIN_STACK_SIZE (4)  
  
/* Create a new stack */  
Stack   
stack_create(int elemsize, PfCbFree freefn)  
{  
        Stack stk;  
          
        stk = malloc(sizeof(struct StackRecord));  
          
        if ( stk == NULL) {  
                fprintf(stderr, "Out of memory\n");  
                exit(1);  
        }  
          
        stk->array = malloc(elemsize * MIN_STACK_SIZE);  
        if (stk->array == NULL) {  
                fprintf(stderr, "Out of memory\n");  
                exit(1);  
        }  
        stk->elemsize = elemsize;  
        stk->loglength = 0;   
        stk->alloclength = MIN_STACK_SIZE;  
}  
  
/* Dispose the stack*/  
void   
stack_dispose(Stack stk)  
{  
        stack_make_empty(stk);  
        free(stk->array);  
        free(stk);  
}  
  
/* Make the given stack empty*/  
void   
stack_make_empty(Stack stk)  
{  
        if ( stk->freefn ) {  
                int i;  
                for ( i = 0; i < stk->loglength; ++i) {  
                        stk->freefn((char *)stk->array +   
                                    i * stk->elemsize);  
                }  
        }  
        stk->loglength = 0;  
}  
  
/* Return true if the stack is empty*/  
int   
stack_is_empty(Stack stk)  
{  
        return stk->loglength == 0;  
}  
  
static void   
stack_grow(Stack stk)  
{  
        stk->alloclength *= 2;  
        stk->array = realloc(stk->array,   
                             stk->alloclength * stk->elemsize);  
}  
  
/* Insert a new element onto stack */  
void   
stack_push(Stack stk, ElementAddr elemaddr)  
{  
        ElementAddr target;  
        if ( stk->loglength == stk->alloclength )  
                stack_grow(stk);  
        target = (char *)stk->array + stk->loglength * stk->elemsize;  
        memcpy(target, elemaddr, stk->elemsize);  
        stk->loglength++;      
}  
  
/* Delete the top element off the stack */  
void   
stack_pop(Stack stk)  
{  
        ElementAddr target;  
        if ( stack_is_empty(stk) ) {  
                fprintf(stderr, "Empty stack\n");  
                exit(1);  
        }  
        if ( stk->freefn ) {  
                target = (char *)stk->array +   
                         (stk->loglength-1) * stk->elemsize;  
        stk->freefn(target);

补充：软件开发 , C语言 ,