数据结构-栈(c链式实现)

/*
    时间：2012年3月11日 19:51:58
    目的：学习数据结构，学校c语言
    功能：栈的链式结构实现
*/

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

#define OK 1
#define FALSE 0
#define TRUE 1
#define ERROR 0

typedef int Status;
typedef int SElemType;

//结点类型
typedef struct Node
{
    SElemType data;
    struct Node *next;
}StackNode, *PStackNode;

//链表类型
typedef struct LinkStack
{
    StackNode * base; //栈底指针
    StackNode * top; //栈顶指针
} LinkStack, *PLinkStack;

Status InitLinkStack(LinkStack *s);

Status EmptyLinkStack(LinkStack *s);

void ClearLinkStack(LinkStack *s);

void DestroyStack(LinkStack *s);

int StackLength(LinkStack *s);

Status GetTop(LinkStack *s, SElemType *e);

Status Push(LinkStack *s, SElemType e);

Status Pop(LinkStack *s, SElemType *e);

void TrasverLinkStack(LinkStack *s);

Status InitLinkStack(LinkStack *s)
{
    s->base = (PStackNode)malloc(sizeof(StackNode));
    if (NULL == s->base)
    {
        printf("内存分配失败,程序退出\n");
        exit(-1);
    }
    s->top = s->base;
    s->base->next = NULL;

    return OK;
}

Status EmptyLinkStack(LinkStack *s)
{
    if (s->base == s->top)
        return TRUE;
    else
        return ERROR;
}

void ClearLinkStack(LinkStack *s)
{
    if (s->top == s->base)
    {
        exit(-1);
    }

    StackNode *p = s->top, *q;
    while(p != s->base)
    {
        q = p->next;
        free(p);
        p = q;
    }
    s->top = s->base;
}

void DestroyStack(LinkStack *s)
{
    StackNode *p = s->top, *q;

    while (p != s->base)
    {
        q = p->next;
        free(p);
        q = p;
    }
    s->top = s->base;
    free(s->base);
    s->base = NULL;
    s->top = NULL;
}

int StackLength(LinkStack *s)
{
    int i = 0;
    StackNode *p = s->top;
    while (p != s->base)
    {
        i++;
        p = p->next;
    }
    return i;
}

Status GetTop(LinkStack *s, SElemType *e)
{
    if (EmptyLinkStack(s))
    {
        printf("栈为空\n");
        exit(-1);
    }
    *e = s->top->data;
    return OK;
}

Status Push(LinkStack *s, SElemType e)
{
    PStackNode r = (PStackNode)malloc(sizeof(StackNode)); //建立新结点
    if (NULL == r)
    {
        printf("新结点建立失败,程序退出\n");
        exit(-1);
    }
    r->data = e;
    r->next = s->top;
    s->top = r;

    return OK;
}

Status Pop(LinkStack *s, SElemType *e)
{

    if (s->top == s->base)
    {
        printf("空栈\n");
        exit(-1);
    }

    StackNode *q = s->top;
    *e = q->data;
    s->top = q->next;
    free(q);
    q = NULL;

    return OK;
}

void TrasverLinkStack(LinkStack *s)
{
    if (EmptyLinkStack(s))
    {
        printf("空栈\n");
        exit(-1);
    }

    StackNode *p = s->top;
    while (p != s->base)
    {
        printf("%d ", p->data);
        p = p->next;
    }

    printf("\n");
}

int main(void)
{
    LinkStack s;
    SElemType e;

    //初始化栈
    if (InitLinkStack(&s))
    {
        printf("--->栈初始化成功\n");
    }
    else
    {
        printf("栈初始化失败\n");
    }
    printf("--->栈中元素个数: %d\n", StackLength(&s));

    //入栈
    Push(&s, 1);
    Push(&s, 2);
    Push(&s, 3);
    Push(&s, 4);
    Push(&s, 5);
    Push(&s, 6);
    printf("--->栈中元素个数: %d\n", StackLength(&s));
    TrasverLinkStack(&s);

    //清空栈
    printf("--->清空栈\n");
    ClearLinkStack(&s);
    printf("--->栈中元素个数: %d\n", StackLength(&s));


    Push(&s, 2);
    Push(&s, 4);
    Push(&s, 5);
    Push(&s, 6);
    Push(&s, 8);
    Push(&s, 9);

    //获取栈顶元素
    TrasverLinkStack(&s);
    GetTop(&s, &e);
    printf("--->栈顶元素: %d\n", e);

    //出栈
    printf("--->栈中元素个数: %d\n", StackLength(&s));
    while (!EmptyLinkStack(&s))
    {
        Pop(&s, &e);
        printf("出栈%d\n", e);
    }
    printf("--->栈中元素个数: %d\n", StackLength(&s));
    TrasverLinkStack(&s);

    DestroyStack(&s);
    return 0;
}