栈

栈的基本定义

栈（stack）是限定于在表尾进行插入或删除操作的线性表。特点为后进先出
栈的顺序存储结构为：

typedef struct{
SElemType *base;//在栈构造之前和销毁之后，base的值为NULL
SElemType *base;//栈顶指针
int stacksize;//当前已分配的存储空间，以元素为单位
}SqStack;

栈的最开始为空时如图一所示，top和base指向同一内存单元，当A进栈top指针上移，base指针不动，如图2所示。

栈的基本操作

typedef int Status;
#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACKINCREMENT 10  //存储空间分配增量
#define OK 1
#define ERROR 0
//SElemType 为自己所需要的的任意定义类型

构造一个空栈

Status InitStack(SqStack &S)
{
    S.base= (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!S.base)
        return ERROR;//存储分配失败
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

判断栈是否为空

Status StackEmpty(SqStack S)
{
    if(S.base==S.top)
        return OK;
    else
        return ERROR;
}

入栈

Status Push(SqStack &S,SElemType e)
{
    if(S.top-S.base>=S.stacksize)
    {//栈满，追加存储空间
        S.base = (SElemType *)realloc(S.base,（S.stacksize+STACKINCREMENT）*sizeof(SElemType));
        if(!S.base)
            return ERROR;
        S.top = S.base+S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top ++=e;
    return OK;
}

出栈

Status Pop(SqStack &S,SElemType &e)
{
    if(S.base==S.top)
        return ERROR;
    e = *--S.top;
    return OK;
}

获取栈顶元素

Status GetTop(SqStack S,SElemType e)
{
    if(S.base==S.top) return ERROR;
    e = *--S.top;
    return OK;
}