文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >数据结构（C语言篇）：（八）栈

数据结构（C语言篇）：（八）栈

作者头像
_OP_CHEN
发布于 2026-01-14 09:33:28
发布于 2026-01-14 09:33:28
220
举报
文章被收录于专栏：C++C++

前言

栈作为一种基础且强大的线性数据结构，在计算机科学领域扮演着至关重要的角色。其"后进先出"（LIFO）的核心特性，使其成为处理函数调用、表达式求值、括号匹配等场景的理想选择。从程序执行时系统栈的管理，到日常开发中撤销操作、浏览历史等功能的实现，栈的应用无处不在。本文将深入探讨栈的工作原理、实现方式以及典型应用场景，帮助读者全面理解这一数据结构的精髓及其在实际工程中的价值。下面就让我们正式开始吧！

一、概念与结构

栈：是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素等操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

压栈和出栈的示意图如下：

栈的底层结构选型：

栈的实现我们一般可以使用数组或者链表来实现，相对而言数组的结构更优一些。因为数组在尾上插入数据的代价是比较小的。

如果使用数组来实现：

此时入栈和出栈的时间复杂度都是

O(1)
O(1)

。

如果使用链表来实现：

此时出栈和入栈的时间复杂度也同样都是

O(1)
O(1)

。

二、栈的实现

2.1 头文件的准备

我们将栈的结构和一系列栈相关的函数在头文件Stack.h中声明如下：

代码语言：javascript
复制
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

//定义栈的结构
typedef int STDataType;
typedef struct Stack {
	STDataType* arr;
	int top; //指向栈顶的位置---刚好就是栈中有效数据个数
	int capacity;//栈的空间大小
}ST;

//初始化
void STInit(ST* ps);
//销毁
void STDesTroy(ST* ps);

//入栈——栈顶
void STPush(ST* ps, STDataType x);
//出栈———栈顶
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);


//栈是否为空
bool STEmpty(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);

2.2 函数的实现

2.2.1 STInit( )函数（初始化）

函数的实现逻辑如下：

1. 初始化数组指针：先将栈的数组指针arr置为NULL，此时表示栈没有分配任何内存空间。

代码语言：javascript
复制
ps->arr = NULL;

2. 初始化栈顶指针和容量：

  • ps->top = 0：将栈顶指针设置为0，表示空栈
  • ps->capacity = 0：将栈的容量设置为0，表示当前没有分配空间
代码语言：javascript
复制
ps->top = ps->capacity = 0;

完整代码如下：

代码语言：javascript
复制
//初始化
void STInit(ST* ps)
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;

}
2.2.2 STDestroy( )函数（销毁）

函数实现逻辑如下：

1. 释放动态数组内存：

  • 检查 ps->arr 是否为 NULL（是否分配了内存）
  • 如果分配了内存，使用 free() 释放数组内存
  • 避免对 NULL 指针调用 free()
代码语言：javascript
复制
if(ps->arr)
    free(ps->arr);

2. 重置指针和状态：

  • ps->arr = NULL：将数组指针设置为 NULL，避免野指针
  • ps->top = 0：将栈顶指针重置为0，表示空栈
  • ps->capacity = 0：将容量重置为0，表示没有分配空间
代码语言：javascript
复制
ps->arr = NULL;
ps->top = ps->capacity = 0;

完整代码如下：

代码语言：javascript
复制
//销毁
void STDesTroy(ST* ps)
{
	if(ps->arr)
		free(ps->arr);

	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

使用示例如下：

代码语言：javascript
复制
ST stack;
STInit(&stack);      // 初始化栈

// 使用栈进行各种操作
STPush(&stack, 10);
STPush(&stack, 20);
// ...

STDesTroy(&stack);   // 销毁栈，释放资源
// 现在stack可以被重新初始化或丢弃
2.2.3 STPush( )函数（入栈）

首先画图分析：

函数实现逻辑如下：

1. 参数验证：确保栈指针 ps 不为 NULL。

代码语言：javascript
复制
assert(ps);

2. 检查空间是否足够：如果栈顶指针等于容量，说明栈已满，需要扩容。

代码语言：javascript
复制
if (ps->top == ps->capacity)

3. 动态扩容机制：首次分配时，如果容量为0（初始状态），先分配四个元素的空间；后续扩容时，如果已有容量，就将容量扩大为原来的2倍。（使用 realloc 重新分配内存，可以保留原有数据）

代码语言：javascript
复制
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));

4. 错误处理：检查内存分配是否成功，如果失败就输出错误信息，并退出程序。

代码语言：javascript
复制
if (tmp == NULL)
{
    perror("realloc fail！");
    exit(1);
}

5. 更新指针和容量：首先更新数组指针指向新分配的内存，然后更新容量为新分配的大小。

代码语言：javascript
复制
ps->arr = tmp;
ps->capacity = newCapacity;

6. 压入元素：将元素 x 放入栈顶位置 ps->arr[ps->top]，然后栈顶指针 ps->top 自增1。

代码语言：javascript
复制
ps->arr[ps->top++] = x;

完整代码如下所示：

代码语言：javascript
复制
//入栈——栈顶
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//判断空间是否足够
	if (ps->top == ps->capacity)
	{
		//增容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail！");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

使用示例如下：

代码语言：javascript
复制
ST stack;
STInit(&stack);

STPush(&stack, 10);  // 分配4个空间，压入10
STPush(&stack, 20);  // 压入20
STPush(&stack, 30);  // 压入30  
STPush(&stack, 40);  // 压入40，栈满
STPush(&stack, 50);  // 扩容到8个空间，压入50
2.2.4 STPop( )函数（出栈）

要想实现出栈函数，我们需要先实现一个STEmpty （判空）函数，如下所示：

代码语言：javascript
复制
//栈是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

画图分析如下：

STPop的实现逻辑如下：

1. 前置条件检查：首先使用用 STEmpty 函数检查栈是否为空，如果栈为空，则断言失败，不能执行弹出操作。同时需要确保栈中至少有一个元素可弹出。

2. 执行弹出操作：首先将栈顶指针 top 减1，这样原来的栈顶元素就不再属于栈的有效范围，但实际上并没有删除数据，只是改变了栈的边界。

代码语言：javascript
复制
ps->top--;

完整代码如下所示：

代码语言：javascript
复制
//出栈———栈顶
void STPop(ST* ps)
{
	assert(!STEmpty(ps));
	ps->top--;
}

使用示例如下：

代码语言：javascript
复制
ST stack;
STInit(&stack);

STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);
// 栈: [10, 20, 30], top=3

STPop(&stack);  // 弹出30
// 栈: [10, 20], top=2

STPop(&stack);  // 弹出20  
// 栈: [10], top=1

STPop(&stack);  // 弹出10
// 栈: 空, top=0
2.2.5 STTop( )函数（取栈顶元素）

画图分析如下：

函数的实现逻辑如下：

1. 前置条件检查：首先使用 STEmpty 函数检查栈是否为空，如果栈为空，则断言失败，不能获取栈顶元素。需要确保栈中至少有一个元素。

代码语言：javascript
复制
assert(!STEmpty(ps));

2. 返回栈顶元素：

  • ps->top 指向下一个空位置（栈顶的下一个位置）
  • ps->top - 1 就是当前栈顶元素的位置
  • 返回该位置的元素值
代码语言：javascript
复制
return ps->arr[ps->top - 1];

完整代码如下：

代码语言：javascript
复制
//取栈顶元素
STDataType STTop(ST* ps)
{
	assert(!STEmpty(ps));
	return ps->arr[ps->top - 1];
}

使用示例：

代码语言：javascript
复制
ST stack;
STInit(&stack);

STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);
// 栈: [10, 20, 30], top=3

STDataType topValue = STTop(&stack);  // 获取栈顶值30
printf("栈顶元素: %d\n", topValue);   // 输出: 栈顶元素: 30

// 栈仍然保持: [10, 20, 30], top=3
2.2.6 STSize( )函数（获取栈中元素个数）

函数实现逻辑如下：

1. 参数验证：确保栈指针 ps 不为 NULL。

代码语言：javascript
复制
assert(ps);

2. 返回元素数量：直接返回栈顶指针 top 的值。因为 top 既指向下一个空位置，又表示当前元素数量。

代码语言：javascript
复制
return ps->top;

完整代码如下：

代码语言：javascript
复制
//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

使用示例如下：

代码语言：javascript
复制
ST stack;
STInit(&stack);

printf("初始栈大小: %d\n", STSize(&stack));  // 输出: 0

STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);

printf("当前栈大小: %d\n", STSize(&stack));  // 输出: 3

STPop(&stack);
printf("弹出后栈大小: %d\n", STSize(&stack));  // 输出: 2

总结

本期我为大家介绍了数据结构中，栈的结构和其相关函数的实现逻辑，下期我将继续为大家带来队列的相关内容，请大家多多关注和支持~~~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2026-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除
ps
函数
数组
指针
数据结构

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

ps
函数
数组
指针
数据结构
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 前言
  • 一、概念与结构
  • 二、栈的实现
    • 2.1 头文件的准备
    • 2.2 函数的实现
      • 2.2.1 STInit( )函数（初始化）
      • 2.2.2 STDestroy( )函数（销毁）
      • 2.2.3 STPush( )函数（入栈）
      • 2.2.4 STPop( )函数（出栈）
      • 2.2.5 STTop( )函数（取栈顶元素）
      • 2.2.6 STSize( )函数（获取栈中元素个数）
  • 总结
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论