链式栈设计

链式栈接口设计

/**
* @name: 链式栈接口设计
* @brief
* @author [email protected]
* @date 2024/04/28
* @version 1.0 ：版本
* @property ：类比于顺序栈，链式栈也有一个栈顶和栈底。根据链式表特性，将第一个插入的值作为栈底，即尾节点作为栈底。首节点作为栈顶。
* @note
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*/


typedef int DataType_t;	 // 指的是链式栈中的结点有效数据类型

//构造链式结点
typedef struct LinkStack // 构造结点,链表中所有结点的数据类型应该是相同的
{
	DataType_t data;		// 结点的数据域
	struct LinkStack *next; // 结点的指针域
} LStack_t;
LStack_t *LStack_Create(void) // 创建一个空链表，空链表应该有一个头结点，对链表进行初始化
{
	// 1.创建一个头结点即栈顶并对头结点申请内存
	LStack_t *Top = (LStack_t *)calloc(1, sizeof(LStack_t));
	if (NULL == Top)
	{
		perror("Calloc memory for Top is Failed");
		exit(-1);
	}
	// 2.对头结点进行初始化,不存储有效内容,因此数据域初始化为0
	Top->next = NULL;
	Top->data = 0;
	// 3.把头结点的地址返回即可
	return Top;
}


//创建新的结点
LStack_t *LStack_NewNode(DataType_t data)
{
	// 1.创建一个新结点并对新结点申请内存
	LStack_t *New = (LStack_t *)calloc(1, sizeof(LStack_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}
	// 2.对新结点的数据域和指针域进行初始化
	New->data = data;
	New->next = NULL;
	return New;
}

//入栈
bool LStack_Push(LStack_t *Top, DataType_t data)
{
	// 1.创建新的结点，并对新结点进行初始化
	LStack_t *New = LStack_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node\n");
		return false;
	}
	/* 此处考虑两种情况，如果链表为空或者非空：
	1.如果为空，即满足Top->next==NULL；
	2.如果为非空，Top->next！=NULL,用下述代码也能满足；
	综上，可以不用if语句判断是否为空链表。
	*/
	New->next = Top->next;
	Top->next = New;
	return true;
}

//出栈
bool LStack_Pop(LStack_t *Top)
{
	// 对首节点的地址进行备份
	LStack_t *PTop = Top->next;
	if (NULL == PTop) // 判断是否为空表 judge is this a empty list.
	{
		printf("This is a empty list.\n");
		return false;
	}
	/* 此处考虑两种情况，如果链表仅有一个元素或一个以上的元素：
	1.如果仅有一个元素，即满足PTop->next==NULL；
	2.如果为非空,PTop->next!=NULL,用下述代码也能满足；
	综上，可以不用if语句判断是否为仅有一个元素。
	*/
	Top->next = PTop->next;
	PTop->next = NULL;
	free(PTop);
	return true;
}

//链表整体释放
bool LStack_Free(LStack_t *Top) // 实现链式栈的整体释放
{
	// 对首节点的地址进行备份
	if (Top == NULL)
	{
		printf("The list doesn't exist.\n");
		return false;
	}
	LStack_t *PTop;
	while (Top)
	{
		PTop = Top;
		Top = Top->next;
		free(PTop);
	}
	return true;
}

//链式栈元素展示
void LStack_Print(LStack_t *Top)
{
	LStack_t *PTop = Top; // 对链表的头文件的地址进行备份
	if (Top == NULL)
	{
		printf("The list doesn't exist.\n");
		return;
	}
	printf("4\n");
	while (PTop->next) // 判断是否为空链表
	{
		// 把头的直接后继作为新的头结点
		PTop = PTop->next;
 
		// 输出头结点的直接后继的数据域
		printf("data = %d  ", PTop->data);
	}
}


//验证
int main(int argc, char const *argv[])
{
	LStack_t *H = (LStack_t *)calloc(1, sizeof(LStack_t));
	LStack_Push(H, 10);
	LStack_Push(H, 20);
	LStack_Push(H, 30);
	LStack_Print(H);
	LStack_Pop(H);
	LStack_Print(H);
	LStack_Free(H);
	return 0;
}