链式栈————出栈、入栈

以链表作为基础实现栈空间（链式栈）

如果打算实现链式栈，一般是以链表作为基础，一般是把链表头部作为栈顶，方便数据的插入和删除（头插+头删），链式栈相当于是一个单向不循环的链表。

链式栈要注意的点：

• 出栈要考虑栈是否为空
• 入栈要考虑栈中是否有数据

以下是我的代码：

/*******************************************************************
 *
 *	file name:	Linkstack.c
 *	author	 :  Dazz
 *	date	 :  2024/04/25
 *	function : 该程序实现链式栈元素的增删改查，目的是提高设计程序的逻辑思维，
 *             另外为了提高可移植性，所以顺序栈中元素的数据类型为DataType_t，
 *             用户可以根据实际情况修改链式栈中元素的类型。
 *
 * 	note	 :  None
 *
 *	CopyRight (c)  2024-202x   [email protected]   All Right Reseverd
 *
 * *****************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// 指的是链式栈中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;

// 构造记录链式栈LinkStack各项参数(栈底地址+栈容量+栈顶元素的下标)的结构体
typedef struct LinkStack
{
	struct LinkStack *next; // 结点的指针域，指向下一个结点
	DataType_t data;		// 结点的数据域
} LinkStack_t;

/******************************************************
 *
 *  name      : LinkStack_Create
 *	function  : 创建一个空栈链表，空链表应该有一个头结点，对链表进行初始化
 *  argument  ：None
 *  retval    : 头结点的地址
 *  author    : Dazz
 *  date      : 2024/4/25
 *  note      : None
 *
 * *******************************************************/
LinkStack_t *LinkStack_Create(void)
{
	// 利用calloc为链栈的管理结构体申请一块堆内存
	LinkStack_t *Head = (LinkStack_t *)calloc(1, sizeof(LinkStack_t));

	if (NULL == Head)
	{
		perror("calloc memory for Head is failed");
		exit(-1); // 程序异常终止
	}

	// 对结点进行初始化
	Head->next = NULL;

	return Head;
}

/******************************************************
 *
 *  name      : LinkStack_NewNode
 *	function  : 创建一个新的结点，并对该结点进行初始化（数据域 + 指针域）
 *  argument
 * 				@data :需要传入结点中的数据
 *
 *  retval    : 新结点的地址
 *  author    : Dazz
 *  date      : 2024/4/25
 *  note      : None
 *
 * *******************************************************/
LinkStack_t *LinkStack_NewNode(DataType_t data)
{
	LinkStack_t *New = (LinkStack_t *)calloc(1, sizeof(LinkStack_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	// 对新结点进行初始化
	New->next = NULL;
	New->data = data;

	return New;
}

/******************************************************
 *
 *  name      : LinkStack_Print
 *	function  : 对链式栈进行遍历并打印每个结点的数据域
 *  argument
 * 				@Head :链式栈的头结点
 *
 *  retval    : None
 *  author    : Dazz
 *  date      : 2024/4/25
 *  note      : None
 *
 * *******************************************************/
void LinkStack_Print(LinkStack_t *Head)
{
	// 判断链式栈是否为空
	if (NULL == Head->next)
	{
		printf("栈为空\n");
		return;
	}

	// 备份头结点
	LinkStack_t *phead = Head;

	// 对链式栈做遍历
	while (phead->next)
	{
		phead = phead->next;
		printf("%d\n", phead->data);
	}
	return;
}

/******************************************************
 *
 *
 *  name      : LinkStack_Push
 *	function  : 创建新的结点，并对新结点压栈
 *  argument
 * 				@Head :链式栈的头结点
 * 				@Data ：入栈结点的数据
 *
 *  retval    : 成功为1，否则为0
 *  author    : Dazz
 *  date      : 2024/4/25
 *  note      : None
 *
 * *******************************************************/
bool LinkStack_Push(LinkStack_t *Head, DataType_t Data)
{
	// 创建新的结点
	LinkStack_t *New = LinkStack_NewNode(Data);
	if (NULL == New)
	{
		return false;
	}

	if (NULL == Head->next)
	{
		Head->next = New;
	}
	else
	{
		LinkStack_t *temp = Head->next; // 备份首结点
		Head->next = New;				// 将头节点的指针域指向新结点
		New->next = temp;				// 将新结点的指针域指向首结点
	}

	return true;
}

/******************************************************
 *
 *
 *  name      : LinkStack_Pop
 *	function  : 对链式栈进行出栈
 *  argument
 * 				@Head :链式栈的头结点
 *
 *  retval    : 成功为1，否则为0
 *  author    : Dazz
 *  date      : 2024/4/25
 *  note      : None
 *
 * *******************************************************/
bool LinkStack_Pop(LinkStack_t *Head)
{
	// 判断链式栈是否为空
	if (NULL == Head->next)
	{
		printf("栈为空,无法出栈\n");
		return false;
	}

	// 栈中只有一个结点的情况
	if (NULL == Head->next->next)
	{
		LinkStack_t *temp = Head->next; // 备份该结点
		Head->next = NULL;				// 将头结点的指针域指向NULL
		temp->next = NULL;				// 将该结点的指针域指向NULL
		free(temp);						// 释放该结点
	}
	else // 栈中不只有一个结点的情况
	{
		LinkStack_t *temp = Head->next; // 备份首结点
		Head->next = temp->next;		// 将头节点的指针域指向首结点的直接后继
		temp->next = NULL;				// 将该结点的指针域指向NULL
		free(temp);						// 释放该结点
	}
}

/******************************************************
 *
 *
 *  name      : LinkStack_IsEmpty
 *	function  : 判断栈是否为空
 *  argument
 * 				@Head :链式栈的头结点
 *
 *  retval    : 为空返回1，非空返回0
 *  author    : Dazz
 *  date      : 2024/4/25
 *  note      : None
 *
 * *******************************************************/
bool LinkStack_IsEmpty(LinkStack_t *Head)
{
	if (NULL == Head->next)
	{
		printf("链表为空\n");
		return true;
	}
	else
	{
		printf("链表不为空\n");
		return false;
	}
}

int main(int argc, char const *argv[])
{
	LinkStack_t *Head = LinkStack_Create();
	LinkStack_Print(Head);

	LinkStack_Push(Head, 999);
	LinkStack_Push(Head, 888);
	LinkStack_Push(Head, 777);
	LinkStack_Print(Head);

	LinkStack_Pop(Head);
	LinkStack_Pop(Head);
	// LinkStack_Pop(Head);
	//  LinkStack_Pop(Head);
	LinkStack_Print(Head);

	LinkStack_IsEmpty(Head);

	return 0;
}