栈的基本操作算法兑现(C语言)

栈的基本操作算法实现(C语言)

#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); //压栈
bool pop(PSTACK ,int *);//出栈
void traverse(PSTACK);//遍历栈
void clear(PSTACK ps);//清空栈


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

   init(&s);
   push(&s,1); 
   push(&s,2); 
   push(&s,3); 
   traverse(&s);

   pop(&s,&val);

   printf("%d\n",val);
   traverse(&s);
}

//初始化栈
void init(PSTACK ps)
{
  ps->pTop=(PNODE)malloc(sizeof(NODE));

  if(ps->pTop==NULL)
  {
	  printf("动态内存分配失败");
	  exit(-1);
  }
  ps->pBottom=ps->pTop;
  ps->pBottom->pNext=NULL;
}

//压栈
void push(PSTACK ps,int val)
{
  PNODE p=(PNODE)malloc(sizeof(NODE));
  p->data=val;
  p->pNext=ps->pTop;

  ps->pTop=p;
  return ;
}

//遍历栈
void traverse(PSTACK ps)
{
	PNODE p=ps->pTop;
   while(p!=ps->pBottom)
   {
     printf("%d  ",p->data);
	 p=p->pNext;
   }
   printf("\n");
   return;
}

//出栈,不需要返回值，因为直接操作存数据的变量的地址
bool pop(PSTACK ps ,int * val)
{
  if(ps->pBottom!=ps->pTop)
  {
     PNODE p=ps->pTop;
	 *val =p->data;
	 ps->pTop=p->pNext;
	 free(p);
	 p=NULL;

	 return true;
  }
  else
	  return false;
}

//清空栈
void clear(PSTACK ps)
{
	//定义一个临时指针q
  PNODE p=ps->pTop , q=NULL;
  
  while(p!=ps->pBottom)
  {
     q=p->pNext;
	 free(p);
	 p=q;
    
  }

  ps->pTop=ps->pBottom;
}