/*
Name: stack.h
Copyright: 1.0
Author: avalon
Date: 02-10-04 19:48
Description: 泛型设计的栈
*/
#ifndef AVALON_STACK_H
#define AVALON_STACK_H
#include <stdio.h>
#ifndef AVALON_BOOL
#define AVALON_BOOL
#define TRUE 1
#define FALSE 0
typedef int BOOL;/*自定义的BOOL型*/
#endif
typedef struct Stack * StackHandle;/* 栈HANDLE */
/*******
接口
*******/
StackHandle InitStack(size_t size);
/*构造一个空栈*/
BOOL GetTop(StackHandle S,void * elem);
/*若栈不空,则用elem返回S的栈顶元素,并返回TRUE*/
BOOL Push(StackHandle S,void * elem);
/*插入元素,elem为新的栈顶元素*/
BOOL Pop(StackHandle S, void * elem);
/*若栈不空,则删除S的栈顶元素,并用elem返回其值,
并返回TRUE.elem也可取NULL值,则仅做弹出动作*/
BOOL ClearStack(StackHandle S);
/*把S置为空栈*/
BOOL DestroyStack(StackHandle * S);
/*销毁栈S*/
BOOL StackEmpty(StackHandle S);
/*栈空?*/
int StackLength(StackHandle S);
/*栈长*/
#endif
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
Name: stack.c
Copyright: 1.0
Author: avalon
Date: 02-10-04 19:48
Description: 泛型设计的栈
*/
#include <stdio.h>
#include <assert.h>
#include <mem.h>
#ifndef AVALON_BOOL
#define AVALON_BOOL
#define TRUE 1
#define FALSE 0
typedef int BOOL;
#endif
/*******
数据结构
*******/
typedef struct Node{
struct Node * prior ;/*前位置*/
void * data ;/**/
}Node, * NodeHandle;
typedef struct Stack{
NodeHandle base ;/*栈底*/
NodeHandle top ;/*栈顶*/
int size_of_stack;/*栈长*/
size_t size_of_data ;/**/
}Stack, * StackHandle;
/******
内部函数
******/
NodeHandle AllocNode(StackHandle S,void * elem)
{/*仅供内部使用专为分配空间*/
NodeHandle temp ;
size_t size;
assert( NULL!=S && NULL != elem);/**/
size = S->size_of_data;
temp= (NodeHandle)malloc(sizeof(Node));
assert( NULL != temp);
(temp->data) = (void *)malloc( size);
memcpy( temp->data, elem , size);
return temp;
}
BOOL FreeNode(NodeHandle * N)
{/*删除结点*/
assert( NULL != *N && NULL !=N);/**/
free( (*N)->data);
free( *N);
return TRUE;
}
/*******
外部接口
*******/
StackHandle InitStack( size_t size)
{/*构造一个空栈*/
StackHandle S = (StackHandle)malloc(sizeof(Stack));
assert( NULL !=S);/**/
S->top = S->base = NULL;
S->size_of_stack = 0;
S->size_of_data = size;
return S;
}
BOOL GetTop(StackHandle S,void * elem)
{/*若栈不空,则用elem返回S的栈顶元素,并返回TRUE*/
if(S==NULL || S->base == S->top)
return FALSE;
memcpy( elem,S->top->data, S->size_of_data);
return TRUE;
}
BOOL Push(StackHandle S,void * elem)
{/*插入元素,elem为新的栈顶元素*/
NodeHandle temp;
assert(NULL !=S);
assert(NULL !=elem);
temp= AllocNode(S,elem);/*分配一个结点*/
(S->size_of_stack)++;
temp->prior = S->top;
S->top = temp;
return TRUE;
}
BOOL Pop(StackHandle S, void * elem)
{/*若栈不空,则删除S的栈顶元素,并用elem返回其值,并返回TRUE
elem也可取NULL值,仅做弹出动作*/
NodeHandle temp;
if(0==S->size_of_stack)/*栈空*/
return FALSE;
temp=S->top->prior;
(S->size_of_stack)--;
if( NULL != elem)/*如果参数为NULL,则直接弹出*/
GetTop(S,elem);
FreeNode( &(S->top));
S->top = temp;
return TRUE;
}
BOOL ClearStack(StackHandle S)
{/*把S置为空栈*/
assert( NULL !=S);
while(0!=S->size_of_stack){
Pop(S,NULL);
}
return TRUE;
}
BOOL DestroyStack(StackHandle * S)
{/*销毁栈S*/
assert(NULL !=S);
assert(NULL != *S);
if(0!=(*S)->size_of_stack)
ClearStack(*S);
free( *S);
*S=NULL;
return TRUE;
}
BOOL StackEmpty(StackHandle S)
{/*栈空?*/
assert( NULL !=S );
if(0==S->size_of_stack)return TRUE;
return FALSE;
}
int StackLength(StackHandle S)
{/*栈长*/
assert(NULL !=S);
return S->size_of_stack;
}