栈的定义及相关操作

typedef struct
{
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;

• 这里定义了一个顺序存储的栈，它包含了三个元素：base,top,stackSize。其中base是指向栈底的指针变量，top是指向栈顶的指针变量，stackSize指示栈的当前可使用的最大容量。

-（ElemType* base 和 ElemType* top）

typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int top;        // 用于标注栈顶的位置
int stackSize;
}

#define STACK_INIT_SIZE 100
initStack(sqStack *s)
{
    s->base = (ElemType *)malloc( STACK_INIT_SIZE * sizeof(ElemType) );
    if( !s->base )
        exit(0);
    s->top = s->base;   // 最开始，栈顶就是栈底
    s->stackSize = STACK_INIT_SIZE;
}

#define SATCKINCREMENT 10

Push(sqStack *s, ElemType e)
{
    // 如果栈满，动态增加空间
    if( s->top - s->base >= s->stackSize )
    {
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if( !s->base )
            exit(0);

        s->top = s->base + s->stackSize;              // 设置栈顶
        s->stackSize = s->stackSize + STACKINCREMENT; // 设置栈底
    }

    *(s->top) = e;
    s->top++;
}

• 出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。
• 每当从栈内弹出一个数据，栈的当前容量就-1。

Pop(sqStack *s, ElemType *e)
{
    if( s->top == s->base )  // 栈已空空是也
        return;
    *e = *--(s->top);
}

ClearStack(sqStack *s){
s->top = s->base;
}

DestroyStack(sqStack *s){
    int i, len;
    len = s->stackSize;
    for( i=0; i < len; i++ ){
        free( s->base );
        s->base++;
    }
    s->base = s->top = NULL;
    s->stackSize = 0;
}

int StackLen(sqStack s)
{
    return(s.top – s.base);  // 初学者需要重点讲解
}

teypedef struct StackNode
{
    ElemType data;  // 存放栈的数据
    struct StackNode *next;
} StackNode, *LinkStackPtr;
teypedef struct LinkStack
{
    LinkStackPrt top;   // top指针
    int count;      // 栈元素计数器
}

Status Push(LinkStack *s, ElemType e)
{
    LinkStackPtr p = (LinkStackPtr) malloc (sizeof(StackNode));
    p->data = e;
    p->next = s->top;
    s->top = p;
    s->count++;
    return OK;
}

Status Pop(LinkStack *s, ElemType *e)
{
    LinkStackPtr p;
    if( StackEmpty(*s) )  // 判断是否为空栈
        return ERROR;
    *e = s->top->data;
    p = s->top;
    s->top = s->top->next;
    free(p);
    s->count--;
    return OK;
}