数据结构：栈（C语言版）

前言

学习过了顺序表和链表，接下来我们学习一种新的数据结构，它就是 ‘栈’。那么，让我们来领略一下栈魅力吧。

一、概念和结构

（1）栈的概念：栈是一种特殊的线性表，它只允许固定的一端进行插入和删除元素的操作。进行操作的一端称为栈顶，另一端称为栈底。

（2）特点：栈的数据元素遵循后进先出（LIFO）原则。

（3）压栈：栈的插入操作称为压栈 / 入栈 / 进栈，入数据在栈顶。

（4）出栈：栈的删除操作叫出栈，出数据也在栈顶。

一个简单的示意图如下：

二、栈的实现

1.栈的结构定义

typedef int STDataType; typedef struct Stack{ STDataType* arr; int top;//当前元素个数，即下一个入栈位置的下标 int capacity;//已分配的空间大小 }ST;

2.栈的初始化

void STInit(ST* ps){ ps->arr = NULL; ps->top = ps->capacity = 0; }

3.入栈

void StackPush(ST* ps, STDataType x){ assert(ps); if(ps->capacity == ps->top){ 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; }

与前面不同的是，申请空间的代码，不需要将其弄成函数分离在外面，因为栈只有这一个插入操作。

4.判空

bool StackEmpty(ST* ps){ assert(ps); return ps->top == 0; }

因为出栈前要判断栈是否为空，所以要先实现栈的判空。

5.出栈

void StackPop(ST* ps){ assert(ps); assert(!StackEmpty(ps)); --ps->top; // 缩容：使用量 < 1/4 且容量 > 4 时，缩减为一半 if (ps->top > 0 && ps->top <= ps->capacity / 4 && ps->capacity > 4) { int newcapacity = ps->capacity / 2; STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType)); if (tmp == NULL) { // 避免缩容失败，数据丢失； perror("realloc fail!"); exit(2); } ps->arr = tmp; ps->capacity = newcapacity; } }

在这里实现的栈的缩容，避免大量入栈后又是大量出栈，导致的空间浪费。

6.取栈顶数据

STDataType StackTop(ST* ps){ assert(ps); assert(!StackEmpty(ps)); return ps->arr[ps->top-1]; }

7.取栈的数据个数

int StackSize(ST* ps){ assert(ps); return ps->top; }

8.栈的销毁

void StackDestroy(ST* ps){ assert(ps); if(ps->arr) free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0; }

三、总结

这篇文章围绕栈（Stack）这一数据结构，从概念出发，逐步讲解了其底层实现。核心观点是：栈是一种"后进先出"（LIFO）的受限线性结构，选用动态数组而不是链表来实现，原因在于数组的尾部插入/删除代价小、缓存局部性好。

本期文章到此为止，感谢各位阅读，有问题还请指出，感谢🙏。