C语言——顺序栈

#include<stdio.h>
#include<stdlib.h>
/*
 * 顺序栈的实现
 * 基本操作的函数原型
 * Status initStack(sqStack *S);
 * Status destroyStack(sqStack *S);
 * Status clearStack(sqStack *S);
 * BOOL isStackEmpty(sqStack S);
 * int stackLength(sqStack S);
 * Status getTop(sqStack S,SElemType &e);
 * Status push(sqStack *S,SElemType e);
 * Status pop(sqStack *S,SElemType *e);
 * Status stackTraverse(sqStack S,Status(*visit)());
 */

/*
 * definition:
 * STACK_INIT_SIZE 栈初始大小
 * STACK_INCREMENT 栈溢出时增加的容量大小
 */
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10

/*
 * self-definitional type
 * SElemType    栈内元素数据类型
 * sqStack      自定义栈类型
 * Status       自定定状态枚举类型
 */
typedef int SElemType;

typedef struct {
    SElemType *top;
    SElemType *base;
    int stack_size;
}sqStack;

typedef enum{
    OK = 0,
    ERROR = -1
}Status;

typedef enum{
    true = 1,
    false = 0
}BOOL;

/*
 * function     : initStack
 * description  : 初始化栈
 * input        : sqStack *S
 * output       : sqStack *S
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-4-18
 */

Status initStack(sqStack *S){
    (*S).base = (SElemType*)malloc(sizeof(SElemType)*STACK_INIT_SIZE);

    if (!(*S).base){
        exit(0);
    }

    (*S).top = (*S).base;
    (*S).stack_size = STACK_INIT_SIZE;

    return OK;
}

/*
 * function     : destroyStack
 * description  : 销毁栈
 * input        : sqStack *S
 * output       : sqStack *S
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-4-18
 */

Status destroyStack(sqStack *S){
    *(*S).top = -1;
    (*S).stack_size = 0;
    free((*S).base);
    (*S).base = NULL;
    return OK;
}

/*
 * function     : clearStack
 * description  : 清空栈
 * input        : sqStack *S
 * output       : sqStack *S
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-4-18
 */

Status clearStack(sqStack *S){
    
    *((*S).top) = 0;
    (*S).stack_size = 0;
    free((*S).base);
    return OK;
}

/*
 * function     : isStackEmpty
 * description  : 是否为空栈
 * input        : sqStack S
 * output       : N/A
 * return value : BOOL(true/false)
 * author       : HanyoungXue
 * date         : 2018-4-18 
 */

BOOL isStackEmpty(sqStack S){
    if (S.base == S.top){
        return true;
    }
    return false;
}

/*
 * function     : stackLength
 * description  : 获取栈长度
 * input        : sqStack S
 * output       : N/A
 * return value : int
 * author       : HanyoungXue
 * date         : 2018-4-18 
 */

int stackLength(sqStack S){
    if (!S.base){
        exit(0);
    }

    return S.top - S.base;
}
/*
 * function     : getTop
 * description  : 若栈不空，则用e返回S的栈顶元素。并返回ok；否则返回ERROR
 * input        : sqStack S,SElemType *e
 * output       : SElemType *e
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-4-18
 */

Status getTop(sqStack S,SElemType *e){
    if (S.base == S.top){
        return ERROR;
    }

    (*e) = *(S.top - 1);
    return OK;
}


/*
 * function     : push
 * description  : 插入元素e为新的栈顶元素
 * input        : sqStack *S,SElemType e
 * output       : sqStack *S
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-4-18
 */
Status push(sqStack *S,SElemType e){
    if ((*S).top - (*S).base>=(*S).stack_size){
        (*S).base = (SElemType *)realloc((*S).base,((*S).stack_size+STACK_INCREMENT)*sizeof(SElemType));
        if(!(*S).base){
            exit(0);
        }
        (*S).top = (*S).base + (*S).stack_size;
        (*S).stack_size+=STACK_INCREMENT;
    }

    *(*S).top = e;
    (*S).top++;
    return OK;
}
/*
 * function     : pop
 * description  : 若栈非空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
 * input        : sqStack *S, SElemType *e
 * output       : sqStack *S, SElemType *e
 * return value : Status(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-4-18
 */

Status pop(sqStack *S,SElemType *e){
    if((*S).top == (*S).base){
        return ERROR;
    }

    *e = *(--(*S).top);
    return OK;
}

Status visit(SElemType e){
    printf("%d\t", e);
    return OK;
}

/*
 * function     : stackTraverse
 * description  : 遍历栈
 * input        : sqStack S, Status (*visit)(SElemType)
 * output       : N/A
 * return value : Status(OK/ERROR)
 * author       : HanyoungXUe
 * date         : 2018-4-18
 */

Status stackTraverse(sqStack S,Status (*visit)(SElemType)){
    while(S.top!=S.base){
        visit(*(--S.top));
    }
    printf("\n");
    return OK;
}



int main(int argc, char const *argv[])
{
    sqStack S;
    initStack(&S);
    push(&S,1);
    push(&S,10);
    printf("stack is empty? %d\n",(int)isStackEmpty(S) );
    // printf("length==%d\n",stackLength(S));
    // SElemType i;
    // getTop(S,&i);
    // printf("%d\n",i );
    // pop(&S,&i);
    // printf("%d\n",i );
    // getTop(S,&i);
    // printf("%d\n",i );
    stackTraverse(S,visit);
    // clearStack(&S);
    // printf("stack is empty? %d\n",(int)isStackEmpty(S) );
    // destroyStack(&S);
    // printf("%d\n", (int)(S.base==NULL));
    return 0;
}
C语言——顺序栈

推荐阅读更多精彩内容
