数据结构之栈--C实现笔记

#include <stdlib.h>
#include <stdio.h>
#define FatalError(str) fprintf(stderr, "%s\\n", str),exit(1);

#define Error(str) FatalError(str);
#ifndef _stack_h
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
typedef int ElementType;
Stack CreateStack(void);
int IsEmpty(Stack S);
void MakeEmpty(Stack S);
void Pop(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void _Test(void);
#endif

struct Node
{
    ElementType Element;
    PtrToNode Next;
};

Stack CreateStack(void)
{
    Stack S;
    S = malloc(sizeof(struct Node));
    if(S == NULL){
        FatalError("Out of space!!!");
    }
    S->Next = NULL;

    return S;
}

int IsEmpty(Stack S)
{
    return S->Next == NULL;
}

void MakeEmpty(Stack S)
{
    if(S == NULL){
        Error("Must use CreateStack first");
    }else{
        while(!IsEmpty(S)){
        Pop(S);
        }
    }
}

void Push(ElementType X, Stack S)
{
    PtrToNode TmpCell;
    TmpCell = malloc(sizeof(struct Node));
    if(TmpCell == NULL){
        FatalError("out of space!!!");
    }else{
        TmpCell->Element = X;
        TmpCell->Next = S->Next;
        S->Next = TmpCell;
    }
}

ElementType Top(Stack S)
{
    if(!IsEmpty(S)){
        return S->Next->Element;
    }
    Error("stack empty!");
    return 0;
}

void Pop(Stack S)
{
    PtrToNode TmpCell;

    if(IsEmpty(S)){
        Error("stack empty!");
    }else{
        TmpCell = S->Next;
        S->Next = S->Next->Next;
        free(TmpCell);
    }
}

void _Test(void)
{
    int a, b, c;
    Stack S;
    a = 1;
    b = 2;
    c = 3;

    S = CreateStack();
    if(S == NULL){
        FatalError("create stack err");
    }

    Push(a, S);
    printf("%d\\n", Top(S));
    Push(b, S);
    printf("%d\\n", Top(S));
    Pop(S);
    printf("%d\\n", Top(S));
    MakeEmpty(S);
    Push(c, S);
    printf("%d\\n", Top(S));
}