数据结构之栈

发布于:2025-07-07 ⋅ 阅读:(23) ⋅ 点赞:(0)

欢迎拜访雾里看山-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) 所有操作O(1)
扩容能力 有限(需重新分配) 无限(除非内存耗尽)
缓存友好 高(连续内存) 低(非连续内存)
实现难度 简单 中等
适用场景 元素数量可预测/固定大小 元素数量变化大/内存受限

总结与选择建议

栈的核心价值

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

实现选择建议

场景 推荐实现 理由
元素数量固定/可预测 顺序栈(数组) 内存紧凑,无额外开销
元素数量变化大/不可预测 链栈(链表) 动态扩展,无容量限制
高频访问/内存敏感 顺序栈 缓存友好,访问速度快
需要多栈共享内存 顺序栈 可在同一数组实现多个栈
需要实现复杂功能 链栈 灵活性高,无扩容问题

应用领域总结

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

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