数据结构：链栈

链栈.c

//
// Created by 方朋 on 16/12/20.
//


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

/*
 * ADT 栈(stack)
 * InitStack(*S)    // 初始化一个空栈S
 * DestoryStack(*S) // 若栈存在则销毁
 * ClearStack(*S)   // 将栈清空
 * StackEmpty(S)    // 是否为空
 * GetTop(S, *e)    // 若栈存在且非空则用e返回S的栈顶元素
 * Push(*S, e)      // 入栈
 * Pop(*S, *e)      // 出栈
 * StackLength(L)   // 元素个数
 */

#define MAXSIZE 10

typedef int SElemType;
// 定义栈结点
typedef struct StackNode
{
    SElemType data;         // 结点数据
    struct StackNode *next; // 结点前驱指针
} StackNode, *LinkStackPtr;

// 定义链栈
typedef struct LinkStack
{
    LinkStackPtr top;   // 栈顶指针
    int count;          // 栈长度
}LinkStack;


Status InitStack(LinkStack *S)
{
    S->top = (LinkStackPtr)malloc(sizeof(StackNode));
    if (!S->top)
        return ERROR;

    // 注意不能直接就 S->top = NULL, 先要申请内存构造结点
    S->top = NULL;
    S->count = 0;
    return OK;
}

/* 把S置为空栈 */
Status ClearStack(LinkStack *S)
{
    LinkStackPtr p,q;
    p=S->top;
    while(p)
    {
        q=p;
        p=p->next;
        free(q);
    }
    S->count=0;
    return OK;
}

Status StackEmpty(LinkStack S)
{
    return S.top == NULL;   // or S.count == 0
}


Status StackTraverse(LinkStack S)
{
//    精简,但可读性差,不太好理解:
//    while (S.top)
//    {
//        printf("%d ", S.top->data);
//        S.top = S.top->next;
//    }

    LinkStackPtr p;
    p = S.top;      // 栈顶指针,也就是链表头指针
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }

    printf("\n");
    return OK;
}

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

Status Pop(LinkStack *S, SElemType *e)
{
    if (!S->top) return ERROR;  // 空栈
    *e = S->top->data;
    S->top = S->top->next;
    S->count--;
    return OK;

}

/* 返回S的元素个数，即栈的长度 */
int StackLength(LinkStack S)
{
    return S.count;
}


/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
Status GetTop(LinkStack S,SElemType *e)
{
    if (S.top==NULL)
        return ERROR;
    else
        *e=S.top->data;
    return OK;
}


int main()
{
    int j;
    LinkStack s;
    int e;
    if(InitStack(&s)==OK)
        for(j=1;j<=10;j++)
            Push(&s,j);
    StackTraverse(s);
    Pop(&s,&e);
    printf("POP e=%d\n",e);
    printf("IS StackEmpty %d(1:Y 0:N)\n",StackEmpty(s));
    GetTop(s,&e);
    printf("TOP e=%d StackLength=%d\n",e,StackLength(s));
    ClearStack(&s);
    printf("%d\n",StackEmpty(s));
    return 0;

}