数据结构 ——进出栈操作的算法

栈操作的算法：

#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);                 //初始化栈
void push(PSTACK,int);             //入栈
void traverse(PSTACK);             //遍历栈
bool pop(PSTACK,int *);            //出栈
void clear(PSTACK pS);             //清空栈 函数声明时形参可以不用写，形参的类型要写

int main(void)
{
STACK S;                   //S和pS是一个地址
int val;

init(&S);                  //造成一个空栈
push(&S,1);
push(&S,2);
push(&S,3);
push(&S,4);
push(&S,5);
push(&S,6);
traverse(&S);

if(pop(&S,&val))
printf("出栈成功，出栈的元素是%d\n",val);
else
printf("出栈失败!\n");
traverse(&S);

clear(&S);
printf("元素将被清空！\n");
traverse(&S);

return 0;
}

void init(PSTACK pS)
{
pS->pTop=(PNODE)malloc(sizeof(NODE));
if(NULL==pS->pTop)
{
printf("分配内存失败,程序终止！\n");
exit(-1);
}

pS->pBottom=pS->pTop;
pS->pTop->pNext=NULL;

return ;
}

void push(PSTACK pS,int val)
{
PNODE pNew=(PNODE)malloc(sizeof(NODE));
pNew->data=val;

pNew->pNext=pS->pTop;
pS->pTop=pNew;

return ;
}

void traverse(PSTACK pS)
{
PNODE p=pS->pTop;

while(p!=pS->pBottom)
{
printf("%d ",p->data);
p=p->pNext;
}
printf("\n");

return ;
}

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

bool pop(PSTACK pS,int *pVal)
{
if(empty(pS))
{
return false;
}
else
{
PNODE r=pS->pTop;             
*pVal=r->data;
pS->pTop=r->pNext;
free(r);
r=NULL;

return true;
}
}

void clear(PSTACK pS)
{
if(empty(pS))
{
return ;
}
else
{
PNODE p=pS->pTop;
PNODE q=NULL;

while(p!=pS->pBottom)
{
q=p->pNext;
free(p);
p=q;
}
}
pS->pTop=pS->pBottom;            //必须有不然是乱数字
}