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

typedef struct  Node{
    int data;
    struct Node* pNext;
} NODE,*PNODE;

typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
}STACK,*PSTACK;

//申明函数
 void initStack(PSTACK);
 void push(PSTACK,int);
 void traverse(PSTACK);
 bool isEmpty(PSTACK);
 bool pop(PSTACK,int*);
 void clear(PSTACK);

int main(void){
    STACK stack;//STACK等价于struc Stack
    int val;
    //初始化栈
    initStack(&stack);
    //压栈
    push(&stack,1);
    push(&stack,2);
    push(&stack,3);
    push(&stack,4);
    push(&stack,5);
    push(&stack,6);
    traverse(&stack);
    //出栈
    if(pop(&stack,&val)){
        printf("出栈的元素为：%d \n",val);
    }else{
        printf("出栈失败！\n");
    }
    //遍历栈
    traverse(&stack);
    clear(&stack);
    traverse(&stack);
    

    return 0;
}

//初始化栈
void initStack(PSTACK stack){
    stack->pTop = (PNODE)malloc(sizeof(NODE));
    if(NULL == stack->pTop){
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    else{
        stack->pBottom = stack->pTop;
        stack->pTop->pNext = NULL;//stack->pBottom->pNext = NULL
    }
}

//判断栈是否为空
bool isEmpty(PSTACK stack){
    if(stack->pTop == stack->pBottom){
        return true;
    }
    else
        return false;
}

//压栈
void push(PSTACK stack, int val){
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data = val;
    pNew->pNext = stack->pTop;//stack->pTop不能写成stack->pBottom
    stack->pTop = pNew;
}

//遍历栈
void traverse(PSTACK stack){
    if(isEmpty(stack)){
        printf("栈为空！\n");
    }else{
        PNODE p = (PNODE)malloc(sizeof(NODE));
        p = stack->pTop;
        while(p != stack->pBottom){
            printf("%d ", p->data);
            p = p->pNext;
        }
        printf("\n");  
    }

}

//出栈,删除顶部第一个元素
bool pop(PSTACK stack, int* val){
    if(isEmpty(stack)){
        return false;
    }else{
        PNODE p = stack->pTop;
        *val = p->data;
        stack->pTop = p->pNext;
        free(p);
        return true;
    }
}

//清空栈
void clear(PSTACK stack){
    if(isEmpty(stack)){
        printf("清空栈失败！\n");    
    }else{
        PNODE p = stack->pTop;
        PNODE q = p->pNext;
        while(p != stack->pBottom){
            q = p->pNext;
            free(p);
            p = q;
        }
        stack->pTop = stack->pBottom;
        printf("栈已经清空！\n");
    }

}