【数据结构】链栈

链式栈是一种数据存储结构，可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。

入栈、出栈、获取栈顶、清空、获取size、是否为空

定义栈
先定义一个单向链表，再定义栈，栈里只存放链表的以一个节点地址，有点像单链表中的头结点的作用。

struct Node{
	T elem;
	struct Node* next;
}
typedef struct Stack{
	struct Node* first;
}stack;

初始化链栈，即将栈顶节点置NULL

void initStack(Stack *s){
	assert(s!=NULL);
	s->first=NULL;
}

入栈，需要传入入栈的元素，新申请一个节点的内存，将元素放进这个节点，然后将这个新节点接上去，注意要先将新节点的next指向栈顶，再去将新节点设置为栈顶。

int pushStack(Stack *s,T elem){
	assert(s!=NULL);
	struct Node* node=malloc(sizeof(Node));
	if(node==NULL){
		return FAILURE;
	}
	node->elem=elem;
	node->next=s->first;
	s->first=node;
	return SUCCESS;
}

出栈，这里传入一个元素的指针用于接受出栈的元素，当然也可以传空指针。将栈顶用一个节点记录，再将栈顶的下一个节点设置为栈顶，最后释放这个被记录的原栈顶。

int popStack(Stack *s,T *pelem){
	assert(s!=NULL);
	if(s->first==NULL){
		return FAILURE;
	}
	if(pelem!=NULL){
		*pelem=s->first->elem;
	}
	struct Node* node=s->first;
	s->first=node->next;
	free(node);
	return SUCCESS;
}

获取栈顶元素，传入一个元素地址用于接受栈顶元素。

int peekStack(Stack *s, T *pelem){
	assert(s!=NULL);
	if(pelem!=NULL){
		*pelem=s->first->elem;
	}

	return SUCCESS;
}

清空栈，这里需要定义两个节点，一个用于记录当前要删除的节点，另一个用于记录要删除节点的下一个。注意在每次循环里要先指定下一个（next）再删除当前节点。循环从栈顶开始，每次替换为被记录的next节点。

void clearStack(Stack *s){
	assert(s!=NULL);
	struct  Node* node,*next;
	for(node=s->first; node!=NULL; node=next){
		next=node->next;
		free(node);
	}
	s->first=NULL;
}

获取栈的大小（元素个数），定义一个size用于记录大小，从头结点开始遍历，每次size+1

size_t sizeStack(Stack *s){
	assert(s!=NULL);
	struct  Node* node=s->first;
	size_t size=0;
	while(node!=NULL){
		size++;
		node=node->next;
	}
	return size;
}

#include "list_stack.h"
#include
#include
void push(Stack *s){
	printf("input a elem n");
	int elem = 0;
	scanf("%d", &elem);
	if(pushStack(s, elem)==SUCCESS){
		printf("input SUCCESS!n");

	}
	else{
		printf("input FAILED!n");
	}

}

void pop(Stack *s){
	int elem =0;
	if(popStack(s, &elem)==SUCCESS){
		printf("pop SUCCESS! ,elem is %dn", elem);

	}
	else{
		printf("pop FAILED!n");
	}
}

void peek(Stack *s){
	int elem =0;
	if(peekStack(s, &elem)==SUCCESS){
		printf("peek SUCCESS! elem is %dn",elem);
	}
	else{
		printf("peek FAILED!n");
	}
}
void empty(Stack *s){
	if(emptyStack(s)){
		printf("Stack is empty!n");
	}
	else{
		printf("stack is not empty!n");

	}

}
void size(Stack *s){
	printf("size of stack is %u n",sizeStack(s));
}
void back(Stack *s){
	clearStack(s);
	exit(0);
}
typedef void(*FUNC)(Stack *s);
struct {
	char *text;
	FUNC func;
}ntfs[]={
	{"push ",push},
	{"pop",pop},
	{"peek ",peek},
	{"empty",empty},
	{"size ",size},
	{"back",back}
};
void menu(void){
	int i=0;
	printf("list_stack testn");
	
	for( i=0; i<(sizeof(ntfs)/sizeof(ntfs[0])); i++){
		printf("%d. %sn",i,ntfs[i].text);
	}
	printf(">>>>");
	

}
void run(void){
	Stack s;
	initStack(&s);
	while(1){
		menu();
		 int opt =0;
	scanf("%d",&opt);
	if(opt>=0&&opt
		ntfs[opt].func(&s);
	}else{
		printf("input FAILED!n");
	}
	}

}
 int main()
{
	run();

	return 0;
}