4-3.c

数据结构经典算法

#include "stdio.h"
typedef char DataType ;
typedef struct stacknode{
	DataType data;
	struct stacknode *next;
}StackNode;
typedef struct{
	StackNode *top;  //栈顶指针
}LinkStack;
//置栈空
void Initial(LinkStack *S)
{
	S->top=NULL;
}
//判栈空
int IsEmpty(LinkStack *S)
{
	return S->top==NULL;
}
//进栈
void Push(LinkStack *S,DataType x)
{//将元素x插入链栈头部
	StackNode *p=(StackNode *)malloc(sizeof(StackNode));
	p->data=x;
	p->next=S->top;//将新结点*p插入链栈头部
	S->top=p;
}
//退栈
DataType Pop(LinkStack *S)
{
	DataType x;
	StackNode *p=S->top;//保存栈顶指针
	if(IsEmpty(S))
    {
		printf("栈为空");  //下溢
		exit(1);
	}
	x=p->data;  //保存栈顶结点数据
	S->top=p->next;  //将栈顶结点从链上摘下
	free(p);
	return x;
}
//取栈顶元素
DataType Top(LinkStack *S)
{
	if(IsEmpty(S))
    {
		printf("栈为空");  //下溢
		exit(1);
	}
	return S->top->data;
}
void main()
{
	LinkStack s;
	DataType first,sec;
	Initial(&s);
	Push(&s,'a');
	Push(&s,'b');
	first=Top(&s);
	Pop(&s);
	sec=Top(&s);
	Pop(&s);
}