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

前言

栈作为一种基础且强大的线性数据结构，在计算机科学领域扮演着至关重要的角色。其"后进先出"（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=3STPop(&stack);  // 弹出30
// 栈: [10, 20], top=2STPop(&stack);  // 弹出20  
// 栈: [10], top=1STPop(&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=3STDataType 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));  // 输出: 0STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);printf("当前栈大小: %d\n", STSize(&stack));  // 输出: 3STPop(&stack);
printf("弹出后栈大小: %d\n", STSize(&stack));  // 输出: 2