【数据结构】手写链栈【纯c语言版】

摘要：本章主要讲述链栈的实现

• • • 1. 链栈的存储结构
    • 2. 链栈的入栈出栈图解
    • 3. 链栈的代码实现
    • • 3.1 定义链栈的结构
      • 3.2 栈的初始化
      • 3.3 创建新结点
      • 3.4 判断栈是否为空
      • 3.5 入栈操作
      • 3.6 出栈操作
      • 3.7 读栈顶操作
      • 3.8 清空栈
      • 3.9 销毁栈
      • 3.10 感悟
    • 源码链接(含测试代码)
    • 文章索引
    • 后记

• 链栈的结构与链表相似
• 插入与删除等操作都在链表的头部
• 即:链栈是一个以top为头结点、从栈顶指向栈底的单链表

typedef struct STDataType
{
	int id;
	char* name;
} STDataType;


typedef struct StackNode
{
	STDataType data;	// 链栈中结点的数据域
	struct StackNode* next; // 链栈中结点的指针域
} StackNode;


typedef struct Stack
{
	StackNode* top;	// 栈顶指针
	int size;		// 栈中元素个数
} Stack;

void StackInit(Stack* ps)
{
	assert(ps);
	ps->size = 0;
	ps->top = NULL;
}

StackNode* BuyStackNode(STDataType* elem)
{
	// 结点中的数据域不能为空
	assert(elem);
	// 开辟一个 StackNode 大小的内存空间
	StackNode* ps = (StackNode*)malloc(sizeof(StackNode));
	if (!ps)
	{
		perror("创建新结点失败!");
		exit(-1);
	}

	ps->data = *elem;
	ps->next = NULL;

	return ps;
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->size == 0;
}

Status StackPush(Stack* ps, STDataType* elem)
{
	assert(ps);
	// 创建新结点
	StackNode* newNode = BuyStackNode(elem);

	// 新结点指向原栈顶指针的指向
	newNode->next = ps->top;
	// 新栈顶指针指向新结点
	ps->top = newNode;
	// 长度+1
	(ps->size) ++;
	// 入栈成功
	return TRUE;
}

Status StackPop(Stack* ps, STDataType* target)
{
	assert(ps);
	if ( StackEmpty(ps) )
	{
		printf("空栈，出栈失败!n");
		target = NULL;
		return FALSE;
	}
	// 返回栈顶元素
	*target = ps->top->data;
	// 保存出栈前的栈顶元素
	StackNode* top = ps->top;
	// 栈顶指针指向原栈顶的下一结点
	ps->top = ps->top->next;
	// 释放原栈顶
	free(top);
	// 总长度-1
	(ps->size)--; 
	return TRUE;
}

Status StackTop(Stack* ps, STDataType* target)
{
	assert(ps);
	if (StackEmpty(ps))
	{
		target = NULL;
		printf("空栈，读取栈顶失败n");
		return FALSE;
	}

	*target = ps->top->data;
	return TRUE;
}

void StackClear(Stack* ps)
{
	assert(ps);
	// 临时记录原栈顶
	StackNode* temp = NULL;
	while (ps->top)
	{
		// 记录原栈顶
		temp = ps->top;
		// 栈顶指针指向原栈顶的下一结点
		ps->top = ps->top->next;
		// 长度-1
		(ps->size) --;
		// 释放原栈顶
		free(temp);
	}
}

void StackDestory(Stack** ps)
{
	StackClear(*ps);
	free(*ps);
	*ps = NULL;
}

其实大家可以发现，链栈的操作和单链表的操作简直是大同小异，只不过我这里的链栈弄了一个头结点而已。

点击跳转到单链表内容

点击跳转
【文件说明】

顺序栈
单链表
循环队列

我水平有限，错误难免，还望各位加以指正。

关于链栈的内容到此结束，感谢您的阅读！！！如果内容对你有帮助的话，记得给我三连丫（点赞、收藏、关注）

本人博客所有文章，均为原创。部分文章中或引用相关资料，但均已著明来源出处。可随意转载、分享，但需加本文链接，以及版权说明。