#数据结构 链式栈

1. 概念

链式栈LinkStack

1. 逻辑结构：线性结构
2. 物理结构：链式存储
3. 栈的特点：后进先出

栈具有后进先出的特点，我们使用链表来实现栈，即链式栈。那么栈顶是入栈和出栈的地方，单向链表有头有尾，那我们将链表的头作为栈顶还是链表的尾作为栈顶呢？如果每次在链表的尾部进行插入或删除，就需要遍历整个链表来找到尾结点即终端结点。而在头部即起始结点进行插入或删除时，仅需头指针找到链表的起始结点，而无需遍历整个链表。

所以链式栈的入栈、出栈都是通过对链表进行头插、头删来实现。

既然要对单向链表进行头插、头删，那么头结点的存在会让操作变得复杂，故我们使用无头单向链表。

无头单向链表的头就是栈顶，故栈针是指向无头单向链表的起始结点的，所以我们在链式栈中将头指针H称做栈针top。top栈针永远指向无头单向链表的第一个节点，栈空的时候除外。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间。

对于空栈来说，链表即H == NULL，链式栈即top == NULL

2. 接口实现

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
#include <stdio.h>
#include <stdlib.h>
//入栈和出栈只在第一个节点位置操作
typedef int datatype;
typedef struct linkstack
{
	datatype data;//数据域
	struct linkstack *next;//指针域
}linkstack_t;
//1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop);
//2.入栈   data是入栈的数据
//参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，那么修改main函数中的top，我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data);
//3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top);
//4.出栈
datatype PopLinkStack(linkstack_t **ptop);
//5.清空栈
void ClearLinkStack(linkstack_t **ptop);//用二级指针，是因为清空后需要将main函数中的top变为NULL
//6.求栈的长度
int LengthLinkStack(linkstack_t *top);//用一级指针，是因为我只是求长度，不需要修改main函数中top指针的指向
//7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top);
#endif

2.1. 定义操作链式栈的结构体

//入栈和出栈只在第一个节点位置操作
typedef int datatype;
typedef struct linkstack
{
	datatype data;//数据域
	struct linkstack *next;//指针域
}linkstack_t;

2.2. 创建空的链式栈

#include "linkstack.h"
void CreateEpLinkStack(linkstack_t **ptop)
{	
	//top = NULL;
	*ptop = NULL;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{
	linkstack_t *top;
	CreateEpLinkStack(&top);
	return 0;
}

2.3. 入栈

思想：

开辟新结点存放入栈数据

每次都将新结点链接到无头单向链表的头

栈针top永远指向无头单向链表的头，栈空时除外

顺序栈需要判满，但链式栈无需判满

/*2.入栈   data是入栈的数据
//参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，
//那么修改main函数中的top，我们采用地址传递*/
int PushLinkStack(linkstack_t **ptop, datatype data)
{	
	linkstack_t *pnew = (linkstack_t *)malloc(sizeof(linkstack_t));
	if(NULL == pnew)
	{
		printf("PushLinkStack pnew malloc failed\n");
		return -1;
	}
	//给新节点初始化
	pnew->data = data;
	pnew->next = *ptop;      
	*ptop = pnew;
  
	return 0;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{
	linkstack_t *top;
	CreateEpLinkStack(&top);
	int i;
	for(i = 0; i < 5; i++)
	{
		PushLinkStack(&top,i);
	}
	return 0;
}

2.4. 出栈

顺序栈需要判空即PS->top==-1

链式栈也需要判空即top == NULL

判空无需改变主函数栈针top的指向，故无需传递top的地址。

但出栈后需要移动栈针，改变top的指向，故需要传递栈针top的地址&top。

综上，出栈函数需要传递栈针top的地址&top。

//3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top)
{
	return top == NULL;
}
//4.出栈
datatype PopLinkStack(linkstack_t **ptop)
{
	if(IsEpLinkStack(*ptop))
	{
		printf("PopLinkStack failed\n");
		return -1;
	}
	datatype temp;
	linkstack_t *pdel = NULL;
#if 0
	pdel = *ptop;
	temp = pdel->data;
	*ptop = pdel->next;
	free(pdel);
	pdel = NULL;
	return temp;
#endif
#if 1
	temp = (*ptop)->data;
	pdel = *ptop;
	*ptop = (*ptop)->next;
	free(pdel);
	pdel = NULL;
	return temp;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{
	linkstack_t *top;
	CreateEpLinkStack(&top);
	int i;
	for(i = 0; i < 5; i++)
	{
		PushLinkStack(&top,i);
	}
#if 0
	for(i = 0; i < 5; i++)	
		printf("%d ",PopLinkStack(&top));
	}
	printf("\n");		
#endif
	return 0;
}

4 3 2 1 0 

2.5. 栈长

问：求栈长是否需要传递栈针的地址？ 无需

问：求栈长能否传递栈针的地址？ 可以

//6.求栈的有效长度
int LengthLinkStack(linkstack_t *top)//用一级指针，是因为我只是求长度，不需要修改main函数中top指针的指向
{
	int len = 0;
	while(top != NULL)
	{
		len++;
		top = top->next;
	}
	return len;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{
	linkstack_t *top;
	CreateEpLinkStack(&top);
	int i;
	for(i = 0; i < 5; i++)
	{
		PushLinkStack(&top,i);
	}
#if 0
	for(i = 0; i < 5; i++)
	{
		printf("%d ",PopLinkStack(&top));
	}
	printf("\n");		
#endif
	printf("len:%d\n",LengthLinkStack(top));
return 0;
}

2.6. 获取栈顶数据

问：获取栈顶数据是否需要移动栈针？

问：获取栈顶数据是否需要传递栈针地址？

获取栈顶数据，部署出栈，无需移动栈针，故无需传递栈针top的地址&top

//7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top)
{
	if(!IsEpLinkStack(top))
	{
		return top->data;
	}
	return -1;
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{
	linkstack_t *top;
	CreateEpLinkStack(&top);
	int i;
	for(i = 0; i < 5; i++)
	{
		PushLinkStack(&top,i);
	}
#if 0
	for(i = 0; i < 5; i++)
	{
		printf("%d ",PopLinkStack(&top));
	}
	printf("\n");		
#endif
	printf("len:%d\n",LengthLinkStack(top));
	printf("top_data%d\n",GetTopLinkStack(top));
	return 0;
}

2.7. 清空

只要不空一直出栈

//5.清空栈
void ClearLinkStack(linkstack_t **ptop)//用二级指针，是因为清空后需要将main函数中的top变为NULL
{	
	while(!IsEpLinkStack(*ptop))
	{
		PopLinkStack(ptop);
	}
}

#include "linkstack.h"
int main(int argc, const char *argv[])
{
	linkstack_t *top;
	CreateEpLinkStack(&top);
	int i;
	for(i = 0; i < 5; i++)
	{
		PushLinkStack(&top,i);
	
#if 0
	for(i = 0; i < 5; i++)
	{
		printf("%d ",PopLinkStack(&top));
	}
	printf("\n");		
#endif
	printf("len:%d\n",LengthLinkStack(top));
	printf("top_data%d\n",GetTopLinkStack(top));
	ClearLinkStack(&top);
	return 0;
}