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

发布于：2025-09-02 ⋅ 阅读:(19) ⋅ 点赞:(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( )函数（获取栈中元素个数）

总结

前言

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

一、概念与结构

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

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

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

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

        栈的底层结构选型：

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

        如果使用数组来实现：

        此时入栈和出栈的时间复杂度都是O(1)。

        如果使用链表来实现：

        此时出栈和入栈的时间复杂度也同样都是O(1)。

二、栈的实现

2.1  头文件的准备

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

#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，此时表示栈没有分配任何内存空间。

ps->arr = NULL;

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

  • ps->top = 0：将栈顶指针设置为0，表示空栈

  • ps->capacity = 0：将栈的容量设置为0，表示当前没有分配空间

ps->top = ps->capacity = 0;

        完整代码如下：

//初始化
void STInit(ST* ps)
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;

}

2.2.2  STDestroy( )函数（销毁）

        函数实现逻辑如下：

        1.  释放动态数组内存：

  • 检查 ps->arr 是否为 NULL（是否分配了内存）

  • 如果分配了内存，使用 free() 释放数组内存

  • 避免对 NULL 指针调用 free()

if(ps->arr)
    free(ps->arr);

        2.  重置指针和状态：

  • ps->arr = NULL：将数组指针设置为 NULL，避免野指针

  • ps->top = 0：将栈顶指针重置为0，表示空栈

  • ps->capacity = 0：将容量重置为0，表示没有分配空间

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

        完整代码如下：

//销毁
void STDesTroy(ST* ps)
{
	if(ps->arr)
		free(ps->arr);

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

        使用示例如下：

ST stack;
STInit(&stack);      // 初始化栈

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

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

2.2.3  STPush( )函数（入栈）

        首先画图分析：

        函数实现逻辑如下：

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

assert(ps);

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

if (ps->top == ps->capacity)

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

int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));

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

if (tmp == NULL)
{
    perror("realloc fail！");
    exit(1);
}

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

ps->arr = tmp;
ps->capacity = newCapacity;

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

ps->arr[ps->top++] = x;

        完整代码如下所示：

//入栈——栈顶
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;
}

        使用示例如下：

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 （判空）函数，如下所示：

//栈是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

       画图分析如下：

        STPop的实现逻辑如下：

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

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

ps->top--;

        完整代码如下所示：

//出栈———栈顶
void STPop(ST* ps)
{
	assert(!STEmpty(ps));
	ps->top--;
}

        使用示例如下：

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 函数检查栈是否为空，如果栈为空，则断言失败，不能获取栈顶元素。需要确保栈中至少有一个元素。

assert(!STEmpty(ps));

        2.  返回栈顶元素：

  • ps->top 指向下一个空位置（栈顶的下一个位置）

  • ps->top - 1 就是当前栈顶元素的位置

  • 返回该位置的元素值

return ps->arr[ps->top - 1];

        完整代码如下：

//取栈顶元素
STDataType STTop(ST* ps)
{
	assert(!STEmpty(ps));
	return ps->arr[ps->top - 1];
}

        使用示例：

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。

assert(ps);

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

return ps->top;

        完整代码如下：

//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

        使用示例如下：

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

总结

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

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布