【数据结构】栈的存储结构（三）链栈

链栈

• 链栈因为不是数组存储，所以需要有指向下一个结点的指针 。
• 链栈如果使用头插法是不需要栈顶指针，即栈顶指针就是头指针。操作和头插法链表一样。
• 链栈若用尾插法略麻烦。

代码收获

• 主要了解链栈的数据结构。
• 链栈的结构体中存储链接下一个结构体的指针，而顺序栈是使用的整形变量作为头指针。
• 链栈的结构体中若是用头插法则不需要栈顶指针，栈顶指针即头指针。

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

typedef struct stack{
	char data;
	struct stack* next;
}stack,*stackp;
void InitialStack(stackp *ST){
	(*ST)=(stackp)malloc(sizeof(stack));
	(*ST)->next = NULL;//next结点为null 
}
int PushStack(stackp ST){
	printf("输入插入的数据，$结束\n");
	int flag = 1;
	while(flag){
		char c;
		c=getchar();
		if(c!='$'){
			stackp newstack;
			newstack = (stackp)malloc(sizeof(stack));
			newstack->next = ST->next; // 新结点的下一个等于头结点的下一个
			newstack->data = c;
			ST->next = newstack;
		}else{
			flag=0;
		}
	}getchar();return 0;
}
void PrintStack(stackp ST){
	stackp move;
	printf("\n从栈顶到栈底依次为\n");
	for(move=ST;move->next!=NULL;move=move->next){
		printf("%c",(move->next)->data);
	}
}
int PopStack(stackp ST){
	printf("\n进行出栈\n");
	stackp move;
	move=ST->next;
	if (move==NULL){
		printf("栈空");
	}else{
	ST->next = move->next;
	free(move);
	}PrintStack(ST);
}
void main(){
	stackp ST;
	InitialStack(&ST);
	PushStack(ST);//不改变头结点，传值 
	PrintStack(ST);
	PopStack(ST);
}