【数据结构】顺序栈与链栈的实现

整理数据结构代码，回顾两种栈的实现方法。

栈的定义

栈(Stack)是限定仅在表尾进行插入与删除操作的线性表。于是栈也有两种实现方式，顺序栈和链栈。

代码实现

顺序栈(SqStack)

#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//顺序栈定义
typedef struct
{
    SElemType *top; //栈顶指针
    SElemType *base; //在栈构造之前和销毁之后为NULL
    int stacksize; //当前已分配大小
}SqStack;

//初始化
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->top == S->base)
        return OK;
    return ERROR;
}

//栈满
Status StackFull(SqStack *S)
{
    if (S->top - S->base >= S->stacksize)
        return OK;
    return ERROR;
}

//栈顶
Status GetTop(SqStack *S, SElemType* e)
{
    if (StackEmpty(S))
        return ERROR;
    (*e) = *(S->top - 1);
    return OK;
}

//压栈
Status PushStack(SqStack *S, SElemType e)
{
    if (StackFull(S))
    {
        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 PopStack(SqStack *S, SElemType* e)
{
    if (StackEmpty(S)) return ERROR;
    (*e) = *(--S->top);
    return OK;
}

//清空
Status ClearStack(SqStack *S)
{
    S->top = S->base;
    S->stacksize = 0;
    return OK;
}

//销毁
Status DestroyStack(SqStack *S)
{
    free(S->base);
    S->top = NULL;
    S->base = NULL;
    S->stacksize = 0;
    return OK;
}

//长度
int Length(SqStack *S)
{
    return S->top - S->base;
}

//遍历栈
Status Traverse(SqStack *S)
{
    SElemType *p;
    p = S->top - 1;
    while (p >= S->base)
    {
        printf("%d ", *p);
        p--;
    }
    printf("\n");
    return OK;
}

链栈(LinkStack)

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//栈节点定义
typedef struct SNode
{
    SElemType data;
    struct SNode *next;
}SNode, *LinkStack;

//初始化
Status InitStack(LinkStack *S)
{
    *S = (SNode *)malloc(sizeof(SNode));
    if (!(*S)) return ERROR;
    (*S)->next = NULL;
    return OK;
}

//栈空
Status StackEmpty(LinkStack S)
{
    if (!S->next)
        return OK;
    return ERROR;
}

//压栈
Status PushStack(LinkStack S, SElemType e)
{
    SNode *p;
    p = (SNode *)malloc(sizeof(SNode));
    if (!p) return ERROR;
    p->data = e;
    p->next = S->next;
    S->next = p;
    return OK;
}

//弹栈
Status PopStack(LinkStack S, SElemType *e)
{
    SNode *p;
    if (StackEmpty(S))
        return ERROR;
    p = S->next;
    S->next = p->next;
    (*e) = p->data;
    free(p);
    return OK;
}

//遍历栈
Status Traverse(LinkStack S)
{
    SNode *p;
    p = S->next;
    while (p)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

DONE！
所示代码如有错误请多加指正，谢谢