数据结构----链栈

链栈存储结构

链栈的存储结构跟单链表相同，但是由于只能在栈顶执行插入和删除操作，显然以单链表的头部做栈顶最方便，不必要想单链表那样为了运算方便而附加头结点。

链栈的实现

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

typedef int DataType;

//定义链栈的结构体
typedef struct Node{
	DataType data;
	struct Node * next;
	
}Node;

//初始化链栈
void InitStrack(Node ** top){
	
	*top = NULL;
}

//链栈的销毁
void DestroyStrack(Node ** top){
	
	Node * p;
	while(*top != NULL){
		
		p = *top;
		*top = (*top)->next;
		free(p);
	}
	
}

//入栈操作
//头插法进行入栈
//C 语言传入函数如果传参为top指针，
//则在函数体内进行的头插操作会在函数体外无效果。
//简单来记：
//想用函数改变某变量，就传入某变值的指针。这里想改变top指针的指向，所以传入top的指针（地址）


//避免措施：
//1):函数返回值变为top类型的指针
//2):函数传参变为指向top的指针，即传入top指针的地址

void Push(Node ** top,DataType x){
	
	printf("入栈操作前的top地址%p\n",*top);
	Node * s = (Node *)malloc(sizeof(Node));
	s->data = x;
	
	s->next = *top;
	
	*top = s;
	
	printf("入栈操作后的top地址%p",*top);
	printf("\n");
	
	
}


//出栈操作
int Pop(Node ** top,DataType * ptr){
	
	printf("出栈操作前的top地址：%p\n",*top);
	Node * p = *top;
	if(top == NULL){
		
		printf("下溢错误，删除失败\n");
		return 0;
	}
	*ptr = (*top)->data;
	*top = (*top)->next;
	free(p);
	printf("出栈操作后的top地址：%p\n",*top);
	return 1;
	
}

//取栈顶元素
int GetTop(Node * top,  DataType * ptr){
	
	if(top == NULL){
		
		printf("下溢错误，取栈顶失败\n");
		return 0;
	}
	
	*ptr = top->data;
	printf("函数中取栈顶元素%d\n",top->data);
	return 1;
	
}

//判空操作
int Empty(Node * top){
	
	printf("top指针地址%p\n",top);
	if(top == NULL){
		return 1;
	}else{
		return 0;
	}
}

//链栈的使用
int main(){
	
	DataType x;
	Node * top = NULL;
	
	InitStrack(&top);
	
	printf("对10 20 30 40进行入栈操作\n");
	
	Push(&top,10);
	Push(&top,20);
	Push(&top,30);
	Push(&top,40);
	

	if(GetTop(top,&x) == 1){
		
		printf("取栈顶元素%d\n",x);
	}
	
	//进行出栈操作
	if(Pop(&top,&x) == 1)
	{
		printf("出栈的元素为%d\n",x);
	}

	if(GetTop(top,&x) == 1){
		
		printf("取栈顶元素%d\n",x);
	}
	
	if(Empty(top) == 1){
		printf("栈为空\n");
	}else{
		printf("栈非空\n");
	}
	
	
	//链栈的销毁
	DestroyStrack(&top);
	
	if(Empty(top) == 1){
		printf("栈为空\n");
	}else{
		printf("栈非空\n");
	}
	return 0;
	
	
}