数据结构之栈

欢迎拜访：雾里看山-CSDN博客
本篇主题：数据结构之栈
发布时间：2025.7.5
隶属专栏：数据结构

栈的概念与结构

基本概念

栈是一种后进先出（LIFO: Last In First Out）的线性数据结构，只允许在固定的一端进行插入和删除操作。

• 压栈/入栈 (Push)：将元素放入栈顶
• 出栈 (Pop)：从栈顶移除元素
• 栈顶 (Top)：唯一允许操作的元素位置
• 栈底 (Bottom)：不允许操作的一端

核心特性

• LIFO原则：最后入栈的元素最先出栈
• 受限访问：只能访问栈顶元素
• 动态大小：大小随操作变化（除固定大小栈）
• 操作高效：所有操作时间复杂度为O(1)

栈的实现

栈有两种主要实现方式：顺序栈（基于数组）和链栈（基于链表）。

顺序栈

栈结构的定义：

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;// 数组的指针
	int top;      // 存储数据的数量
	int capacity; // 栈的总容量
}ST;

基本操作的实现

// 栈的初始化
void STInit(ST* ps)
{
	assert(ps);

	STDataType* tmp= (STDataType*)malloc(sizeof(STDataType) * 4);
	if (tmp == NULL)
	{
		perror("Init malloc fail");
		exit(-1);
	}

	ps->a = tmp;
	ps->capacity = 4;
	ps->top = 0;
}

// 栈的销毁
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a == NULL;
	ps->top = ps->capacity = 0;
}

// 入栈
void STPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		STDataType* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("Push realloc fail");
			exit(-2);
		}
		ps->a = tmp;
		ps->capacity *= 2;

	}

	ps->a[ps->top] = x;
	ps->top++;
}

// 出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	ps->top--;
}

// 取栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

// 栈存储的数量
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

//栈是否为空
bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

链栈

栈结构的定义

typedef int STDataType;

typedef struct StackNode
{
	STDataType data;       // 存放数据
	struct StackNode* next;// 指向下一个节点
}STNode;

typedef struct Stack
{
	STNode* top;       // 栈顶元素
	int size;          // 栈内元素的数量
}Stack;

基本操作的实现

// 初始化栈
void StackInit(Stack* ps)
{
	ps->top = NULL;
	ps->size = 0;
}
// 创建节点
STNode* BuyNode(STDataType x)
{
	STNode* tmp = (STNode *)malloc(sizeof(STNode));
	if (tmp == NULL)
	{
		perror("malloc node fail\n");
		exit(-1);
	}
	tmp->data = x;
	tmp->next = NULL;
	return tmp;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	STNode* node = BuyNode(data);

	node->next = ps->top;
	ps->size++;
	ps->top = node;
}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->size > 0);

	STNode* top = ps->top;
	ps->top = ps->top->next;
	ps->size--;
	free(top);
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	return ps->top->data;
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->size;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->size == 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);

	while (ps->top)
	{
		STNode* tmp = ps->top;
		ps->top = ps->top->next;
		free(tmp);
	}
	ps->size = 0;
}

两种实现的比较

总结与选择建议

栈的核心价值

• 简单高效：所有操作时间复杂度O(1)
• 逻辑清晰：LIFO原则简化问题处理
• 功能强大：适用于多种算法和系统功能
• 内存友好：最小化临时存储需求

实现选择建议

应用领域总结

• 系统级开发：函数调用栈、中断处理
• 算法实现：DFS、回溯、表达式求值
• 应用软件：撤销/重做、浏览历史
• 编译器：语法分析、中间代码生成
• 嵌入式系统：有限状态机、任务调度

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！