/**
* @brief C语言实现的顺序结构类型的栈
* @author wid
* @date 2013-10-29
*
* @note 若代码存在 bug 或程序缺陷, 请留言反馈, 谢谢!
*/
#include
#include
#include
#define TRUE 1
#define FALSE 0
typedef struct Point2D
{
int x;
int y;
}ElemType; //栈元素结构
typedef struct
{
ElemType *btm; //栈底
ElemType *top; //栈顶
int height; //栈高
int size; //栈总大小
}ArrStack; //栈结构
//栈方法声明
ArrStack *CreateStack( int nSize ); ///创建一个大小为nSize的栈
void DestroyStack( ArrStack *pStack ); ///销毁栈 pStack
void ClearStack( ArrStack *pStack ); ///清空栈 pStack 内的元素
int GetHeight( ArrStack *pStack ); ///获取栈 pStack 的高度
int GetSize( ArrStack *pStack ); ///获取栈 pStack 的总容量
int IsEmpty( ArrStack *pStack ); ///检测栈 pStack 是否为空栈
int Push( ArrStack *pStack, ElemType *pt ); ///将元素 pt 压入栈 pStack
int Pop( ArrStack *pStack, ElemType *pt ); ///将栈顶元素出栈到 pt
int GetTop( ArrStack *pStack, ElemType *pt ); ///获取栈顶元素到 pt
void ForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) ); ///从栈底到栈顶的每个元素依次执行 func 函数
void ReForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) ); ///从栈顶到栈底的每个元素依次执行 func 函数
//栈方法实现
/**
* @brief 创建一个大小为 nSize 的栈
*
* @param nSize 栈的初始大小
*
* @return 返回指向创建的栈的指针
*
* @note nSize 初始大小需大于0
*/
ArrStack *CreateStack( int nSize )
{
//根据栈结构创建一个栈
ArrStack *pStack = (ArrStack *)malloc( sizeof(ArrStack) );
//申请栈初始空间
pStack->btm = (ElemType *)calloc( nSize, sizeof(ElemType) );
//令栈顶指向栈底元素
pStack->top = &pStack->btm[0];
//初始化栈高度为 0
pStack->height = 0;
//初始化栈大小为初始大小
pStack->size = nSize;
return pStack;
}
/**
* @brief 销毁栈 pStack
*
* @param pStack 指向待销毁的栈的指针
*
* @return void
*/
void DestroyStack( ArrStack *pStack )
{
//释放栈内元素
free( pStack->btm );
//释放栈
free( pStack );
}
/**
* @brief 清空栈内元素
*
* @param pStack 指向待清空元素的栈的指针
*
* @return void
*/
void ClearStack( ArrStack *pStack )
{
//令栈顶指向栈底
pStack->top = &pStack->btm[0];
//将栈高度置为 0
pStack->height = 0;
}
/**
* @brief 获取栈 pStack 的高度
*
* @param pStack 指向待获取高度的栈的指针
*
* @param 返回当前栈的高度
*/
int GetHeight( ArrStack *pStack )
{
return pStack->height;
}
/**
* @brief 获取栈 pStack 的总容量
*
* @param pStack 指向待获取总容量的栈的指针
*
* @return 返回栈的当前总容量
*/
int GetSize( ArrStack *pStack )
{
return pStack->size;
}
/**
* @brief 检测栈 pStack 是否为空栈
*
* @param pStack 指向待检测的栈的指针
*
* @return 若栈为空, 则返回 TRUE, 否则返回 FALSE
*/
int IsEmpty( ArrStack *pStack )
{
return pStack->height == 0 ? TRUE : FALSE;
}
/**
* @brief 将元素 pt 压入栈 pStack
*
* @param pStack 指向待压入元素的栈的指针
* @param pt 指向待压入元素的指针
*
* @return 返回成功压入后栈的高度
*/
int Push( ArrStack *pStack, ElemType *pt )
{
///检测是否需要扩容
if( pStack->height == pStack->size )
{ //需要扩容
//重新申请于原栈大小2倍大小的栈空间
ElemType *pe = (ElemType *)calloc( pStack->size * 2, sizeof(ElemType) );
//将旧栈内容拷贝到新栈内容
memcpy( pe, pStack->btm, pStack->size * sizeof(ElemType) );
//重置栈总容量大小
pStack->size = pStack->size * 2;
//释放旧栈空间
free( pStack->btm );
//将栈底指向新开辟的栈空间
pStack->btm = pe;
//栈顶指向新栈最后一个元素
pStack->top = &pe[pStack->height-1];
}
//将新元素压入栈
pStack->btm[pStack->height].x = pt->x;
pStack->btm[pStack->height].y = pt->y;
//栈高度自增一
++pStack->height;
//栈顶指向最新栈元素
pStack->top = &pStack->btm[pStack->height-1];
return pStack->height;
}
/**
* @brief 将栈顶元素出栈 到 pt
*
* @param pStack 指向待弹出元素的栈的指针
* @param pt 指向接收弹出的元素的指针
*
* @return 出栈成功则返回出栈后栈的高度, 否则返回 -1
*/
int Pop( ArrStack *pStack, ElemType *pt )
{
///是否为空栈
if( pStack->height == 0 )
return -1;
//将栈顶元素赋值到 pt
pt->x = pStack->top->x;
pt->y = pStack->top->y;
//栈高度减一
--pStack->height;
//栈顶指向栈顶元素的上一个元素
pStack->top = &pStack->btm[pStack->height-1];
return pStack->height;
}
/**
* @brief 获取栈顶元素到 pt
*
* @param pStack 指向待弹出元素的栈的指针
* @param pt 指向接收弹出的元素的指针
*
* @return 获取成功则返回栈顶元素的位置, 否则返回 -1
*
* @note 元素位置由 0 计起
*/
int GetTop( ArrStack *pStack, ElemType *pt )
{
pt->x = pStack->top->x;
pt->y = pStack->top->y;
return pStack->height;
}
/**
* @brief 从栈底到栈顶的每个元素依次执行 func 函数
*
* @param pStack 指向待处理的栈的指针
* @param func 需要执行的函数的指针
*
* @return void
*/
void ForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) )
{
int i = 0;
for( i = 0; i height; ++i )
{
func( &pStack->btm[i] );
}
}
/**
* @brief 从栈顶到栈底的每个元素依次执行 func 函数
*
* @param pStack 指向待处理的栈的指针
* @param func 需要执行的函数的指针
*
* @return void
*/
void ReForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) )
{
int i = pStack->height - 1;
for( i; i >= 0; --i )
{
func( &pStack->btm[i] );
}
}
//测试
void display( ElemType *pt )
{
printf( "(%d,%d) ", pt->x, pt->y );
}
int main()
{
///测试创建初始大小为 5 的栈
ArrStack *psk = CreateStack( 5 );
///测试 IsEmpty、GetSize、GetHeight
if( IsEmpty(psk) == TRUE )
printf( "Stack Size=%d, Stack Height=%dn", GetSize(psk), GetHeight(psk) );
ElemType pt;
int i = 0;
///测试Push, 向栈内压入8个元素
printf( "n向栈内压入8个元素后:n" );
for( i = 0; i < 8; ++i )
{
pt.x = pt.y = i;
Push( psk, &pt );
}
//输出压入8个元素后的栈状态
printf( "Is empty = %dn", IsEmpty(psk) );
printf( "Stack size = %dn", GetSize(psk) );
printf( "Stack height = %dn", GetHeight(psk) );
///测试 ForEachStack、ReForEachStack
printf( "n测试 ForEachStack、ReForEachStack:n" );
ForEachStack( psk, display );
putchar('n');
ReForEachStack( psk, display );
putchar('n');
///测试getTop
GetTop( psk, &pt );
printf( "n栈顶元素为: (%d,%d)n", pt.x, pt.y );
///测试 Pop
Pop( psk, &pt );
printf( "nPop弹出的元素为(%d,%d), 弹出后栈高:%dn", pt.x, pt.y, GetHeight(psk) );
Pop( psk, &pt );
printf( "nPop弹出的元素为(%d,%d), 弹出后栈高:%dn", pt.x, pt.y, GetHeight(psk) );
///测试Push
pt.x = pt.y = 100;
Push( psk, &pt );
printf( "nPop压入的元素为(%d,%d), 压入后栈高:%dn", pt.x, pt.y, GetHeight(psk) );
///执行全面出栈操作
printf( "n执行全面出栈:n" );
int n = GetHeight(psk);
for( i = 0; i < n; ++i )
{
Pop( psk, &pt );
printf( "Pop弹出的元素为(%d,%d), 弹出后栈高:%dn", pt.x, pt.y, GetHeight(psk) );
}
///销毁栈
DestroyStack( psk );
return 0;
}
测试结果: