关于栈的建立，入栈，出栈，遍历，清空等操作

#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 init(PSTACK);//初始化一个空栈，使pTop和pBottom都指向头结点
void push(PSTACK,int);//存元素，压栈
void traverse(PSTACK);//遍历
bool pop(PSTACK,int *);//出栈并且返回出栈元素，还要判断出栈是否成功
bool empty(PSTACK);//判断栈是否为空
void clear(PSTACK);//清空数据

int main(){
    STACK S;//等价于struct Stack S,分配一块内存空间名为S
          //里面有pTop和pBottom，暂时是垃圾值
   int val;       

    init(&S);//初始化一个空栈，使pTop和pBottom都指向头结点
    push(&S,1);//存元素，压栈
     push(&S,2);//存元素，压栈     
    traverse(&S);//遍历
    clear(&S);//清空

    if(pop(&s,&val)){//删元素，出栈
        printf("出栈成功，出栈元素的是%d\n",val);
    }
    else{
        printf("出栈失败");
    }

    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;//pS->pBottom->pNext==NULL
        //pS的成员pTop指向的头结点的指针域为空
    }
}

void push(PSTACK pS,int val){
    PNODE pNew = (PNODE)malloc(sizeof(NODE));//创建新结点
    pNew->data = val;
    pNew->pNext = pS->pTop;//使新节点的指针域指向原来的栈顶节点，
                           //不能是ps->pBottom
    pS->pTop = pNew;//使栈顶指向新节点地址

    return ;
}

void traverse(PSTACK pS){
    PNODE p = pS->PTop;//临时指针指向栈顶
    while(p != pS->pBototm){//若p还没有栈底pBottom，则遍历输出
        printf("%d ",p->data);//从栈顶开始输出
        p=p->pNext;
    }
    printf("\n");
    return ;
}

bool empty(PSTACK pS){
    if(pS->pTop == pS->pBottom) return true;//当栈底和栈顶指向同一块地址，为空栈
    esle return false;
}

//把pS所指向的栈出栈一次，并把出栈的元素存入val形参所指向的变量中，
//出栈成功返回true,失败返回false
bool pop(PSTACK pS,int * val){
    if(empty(pS)) return false;
    els{
        *val = pS->data;//主函数里输出出栈元素
        PNODE r = pS->pTop;//临时指针r指向出栈元素位置：栈顶，方便最后释放内存
        ps->pTop = r->pNext;//栈顶指针指向原来栈顶的下一个节点地址
        free(r);
        r = NULL;
        return true;
    } 
}

void clear(PSTACK pS){//清空数据,最终使栈顶和栈底指向同一个地址
        if(empty(pS)){//如果栈本身为空，不需要清空
            return ;
        }
        else{
            PNODE p = pS->pTop;//临时指针P指向栈顶
            PNODE q = NULL;//临时指针q暂时设为NULL
            while(p != pS->pBottom){//当栈顶指针不指向栈底时，栈不为空
                q = p->pNext;//临时指针q指向下一个节点
                free(p);//释放p的内存
                p = q;//再使p指向下一节点地址
            }
        }
    pS->pTop = pS->pBottom;//最后数据全部清空，栈顶和栈底指向同一个地址
}