LV050-链式栈简介

一、链式栈

1. 存储结构

当我们固定单链表的一端，只在一段进行操作，便构成了栈，我们可以将链表头部作为栈顶的一端，这样可以避免在实现数据入栈 " 和 出栈 操作时做大量遍历链表的耗时操作。

这样就意味着我们需要在头节后进行节点的插入和删除来完成入栈和出栈。

2. 结构体实现

我们通过单链表来实现栈，这样其实它还是一个单链表，仅仅是限制了插入和删除节点的位置罢了，所以结构体可以像这样定义：

typedef int data_t; /* 定义栈中数据元素的数据类型 */

typedef struct slstack_node 
{
	data_t data;
	struct slstack_node *next;
}slstacknode, * slstacklink;

3. 链式栈的基本操作

相关的源代码可以在这里下载：

数据结构	栈 (密码: du8k)

3.1 链栈创建

/**
 * @Function: slstack_create
 * @Description: 链式栈创建
 * @param   : none
 * @return  : 返回一个地址
 *            NULL, 创建失败;
 *            other, 创建成功
 */
slstacklink slstack_create()
{
	/* 定义一个链式栈的结构体指针变量 */
	slstacklink S;
	/* 1. 申请链式栈的内存空间 */
	S = (slstacklink)malloc(sizeof(slstacknode));
	/* 2. 判断是否申请成功 */
	if(S == NULL)
	{
		printf("slinked list stack malloc failed!\n");
		return NULL;
	}
	/* 3.初始化内存空间 */
	S->data = 0;
	S->next = NULL;
	
	return S;
}

3.2 链栈释放

/**
 * @Function: slstack_free
 * @Description: 链式栈释放
 * @param S : 链式栈地址
 * @return  : 返回一个 NULL
 *            NULL, 释放完成
 */
slstacklink slstack_free(slstacklink S)
{
	/* 定义一个链式栈的结构体指针变量 */
	slstacklink p;
	/* 1. 判断链式栈是否存在 */
	if (S == NULL) 
	{
		printf("slinked stack is not existed!\n");
		return NULL;
	}
	/* 2. 释放各个节点空间 */
	printf("slinked stack free:");
	while(S != NULL)
	{
		p = S;
		printf("%d ", p->data);
		S = S->next;
		free(p);
	}
	puts("");
	
	return NULL;
}

3.3 链栈显示

/**
 * @Function: slstack_show
 * @Description: 链式栈数据显示
 * @param S : 链式栈地址
 * @return  : 返回一个数值
 *            0, 显示成功;
 *            -1, 链式栈不存在
 */
int slstack_show(slstacklink S)
{
	/* 定义一个链式栈的结构体指针变量 */
	slstacklink p;
	/* 1. 判断链式栈是否存在 */
	if (S == NULL) 
	{
		printf("slinked stack is not existed!\n");
		return -1;
	}
	/* 2. 判断链式栈是否为空 */
	if (S->next == NULL) 
	{
		printf("slinked stack is empty!\n");
		return -1;
	}
	/* 3. 遍历所有节点 */
	p = S;
	printf("slinked stack:");
	while(p->next != NULL)
	{
		printf("%d ", p->next->data);
		p = p->next;
	}
	puts("");
	
	return 0;
}

3.4 链栈状态

/**
 * @Function: slstack_empty
 * @Description: 链式栈是否为空
 * @param S : 链式栈地址
 * @return  : 返回一个数值
 *            0, 链式栈非空;
 *            1, 链式栈为空;
 *            -1, 链式栈不存在
 */
int slstack_empty(slstacklink S)
{
	/* 1. 判断链式栈是否存在 */
	if (S == NULL) 
	{
		printf("slinked stack is not existed!\n");
		return -1;
	}
	/* 2. 判断链式栈头节点后是否有节点 */
	if(S->next == NULL)
		return 1;
	else
		return 0;
	/* 也可以写成下边的形式 */
	// return (S-> next == NULL ? 1 : 0);
}

3.5 数据入栈

/**
 * @Function: slstack_push
 * @Description: 入栈
 * @param S : 链式栈地址
 * @param value : 要入栈数据
 * @return  : 返回一个数值
 *            0, 入栈成功;
 *            -1, 入栈失败
 */
int slstack_push(slstacklink S, data_t value)
{
	/* 定义一个链式栈的结构体指针变量 */
	slstacklink p;
	/* 1. 判断链式栈是否存在 */
	if (S == NULL) 
	{
		printf("slinked stack is not existed!\n");
		return -1;
	}
	/* 2. 新建节点并初始化 */
	p = (slstacklink)malloc(sizeof(slstacknode));
	if(p == NULL)
	{
		printf("The new node malloc failed!\n");
		return -1;
	}
	p->data = value;
	p->next = NULL;
	/* 3.头部插入节点 */
	p->next = S->next;
	S->next = p;
	
	return 0;
}

3.6 数据出栈

【注意】这里出栈的时候不要做栈是否存在以及是否为空的判断，这两个判断若是有返回值的话程序会认为返回值就是出栈的元素，所以栈的存在性以及是否为空，要在使用出栈函数前进行判断。

/**
 * @Function: slstack_pop
 * @Description: 出栈
 * @param S : 链式栈地址
 * @return  : 返回一个数值
 *            0, 出栈成功;
 *            -1, 链式栈不存在或者链式栈为空
 */
data_t slstack_pop(slstacklink S)
{
	/* 定义一个链式栈的结构体指针变量 */
	slstacklink p;
	data_t temp;
	/* 1. 判断链式栈是否存在 */
	/* 这一步不需要，因为栈中元素可能是任意数值，所以这里做判断并不合适，需要在函数外判断 */
	/* 2. 判断链式栈是否为空 */
	/* 这一步不需要，因为栈中元素可能是任意数值，所以这里做判断并不合适，需要在函数外判断 */
	/* 3. 出栈 */
	p = S->next;
	S->next = p->next;
	
	temp = p->data;
	/* 4. 释放出栈节点的内存空间 */
	free(p);
	p = NULL;
	return temp;
}