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

//节点结构
typedef struct Node
{
    int data;               //节点数据域
    struct Node * pNext;    //节点指针域，指向下一个NODE节点地址
}NODE, * PNODE;

//栈结构
typedef struct Stack
{
    PNODE pTop;         //栈的头节点
    PNODE pBottom;      //栈的底节点
}STACK, * PSTACK;

//创建一个栈
void init(PSTACK pS);
//压栈
void push(PSTACK pS,int val);
//判断栈是否为空
bool isEmpty(PSTACK pS);
//出栈
bool pop(PSTACK pS,int * val);
//遍历输出
void traverse(PSTACK pS);

int main(void)
{   
    STACK S;
    int val;

    init(&S);
    push(&S,1);
    push(&S,2);
    push(&S,3);
    push(&S,4);

    traverse(&S);

    if(pop(&S,&val)){
        printf("出栈的元素为%d \n", val);
    }else{
        printf("为空出栈失败 \n");
    }

    traverse(&S);

    return 0;
}

void init(PSTACK pS)        //栈的初始状态，栈的头部等于底部
{
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if(pS->pTop == NULL){
        printf("动态开辟内存失败");
        exit(-1);
    }else{
        pS->pBottom = pS->pTop;
        pS->pTop->pNext = NULL;  //指针域为空，表示没有指向下一个节点
    }
}

void push(PSTACK pS,int val)
{
    //首先创建一个新节点
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(pNew == NULL){
        printf("动态开辟内存失败");
        exit(-1);
    }else{

        pNew->data = val;        //数据域填入数据
        pNew->pNext = pS->pTop;  //指针域指向pTop;
        pS->pTop = pNew;         //新压栈进来的节点放在pTop上
    }
}

void traverse(PSTACK pS)
{   
    PNODE p = pS->pTop;
    while(p != pS->pBottom)     //栈头不等于栈底
    {   
        printf("%d ",p->data);
        p = p->pNext;
    }
    printf("\n");
}

bool isEmpty(PSTACK pS)
{
    if(pS->pTop == pS->pBottom){
        return true;
    }else{
        return false;
    }
}

//出栈一次
bool pop(PSTACK pS,int * val)
{
    if(isEmpty(pS)){
        return false;
    }else{
        PNODE r = pS->pTop;     //要删除的那个先存起来
        * val = r->data;        //要删除值
        pS->pTop = r->pNext;    //下一个变成top
        free(r);
        r = NULL;
        
        return true;
    }
}