/** * @brief C语言实现的顺序结构类型的栈 * @author wid * @date 2013-10-29 * * @note 若代码存在 bug 或程序缺陷, 请留言反馈, 谢谢! */ #include <stdio.h> #include <stdlib.h> #include <string.h> #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 <  pStack->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=%d\n", 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 = %d\n", IsEmpty(psk) );     printf( "Stack size = %d\n", GetSize(psk) );     printf( "Stack height = %d\n", 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), 弹出后栈高:%d\n", pt.x, pt.y, GetHeight(psk) );     Pop( psk, &pt );     printf( "\nPop弹出的元素为(%d,%d), 弹出后栈高:%d\n", pt.x, pt.y, GetHeight(psk) );     ///测试Push     pt.x = pt.y = 100;     Push( psk, &pt );     printf( "\nPop压入的元素为(%d,%d), 压入后栈高:%d\n", 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), 弹出后栈高:%d\n", pt.x, pt.y, GetHeight(psk) );     }     ///销毁栈     DestroyStack( psk );     return 0; }