【数据结构】C 语言实现栈（Stack）超详细入门 + LeetCode 实战-171主机测评

前情回顾：上一篇主要讲解了双向链表，大家感兴趣的可以再去学习观看：

数据结构–双向链表-CSDN博客

前言：

一.栈的概念

注意：

栈的核心操作：

二.栈的实现

1.栈的初始化（动态数组实现）

2.入栈

3.出栈

4.获取栈顶元素

5.获取栈中有效元素个数

6.判空（如果为空返回非0结果）

7.销毁栈

三.栈的经典应用

思路：

注意：

详细代码（C语言实现）：

四.总结

前言：

栈是数据结构中最基础、最重要的一种线性结构。不管是考试、面试、还是写算法，栈都是必学内容。本篇文章用最通俗的语言 + 完整可运行的 C 代码带你从零实现栈，并完成一道经典 LeetCode 栈题目，新手也能轻松看懂。

适合人群：C 语言初学者、数据结构入门、准备面试刷题的同学。

———————————————————————————————————————————

一.栈的概念

栈（Stack）是一种先进后出（LIFO：Last In First Out）的数据结构。

如图所示：先进去的子弹最后出来，形象的解释了栈的概念

注意：

栈只有一端可以操作，叫做栈顶；另一端固定不动，叫做栈底。一般用数组来实现，不过链表，双向链表也都能实现。

栈的核心操作：

二.栈的实现

1.栈的初始化（动态数组实现）

//栈的初始化
void STInit(ST* sl)
{
assert(sl);
sl->arr = (data*)malloc(sizeof(data));
sl->count = 0;
sl->capacity = 1;
}

2.入栈

//入栈
void STPush(ST* sl, data x)
{
assert(sl);
//判断栈的空间
if (sl->count == sl->capacity)
{
//扩容
data* temp = (data*)realloc(sl->arr, sizeof(data) * 2 * sl->capacity);
//判断扩容是否成功
if (temp == NULL)
{
perror("空间为空");
exit(1);
}
else
{
sl->arr = temp;
//重新给定栈的空间
sl->capacity *= 2;
}
}
sl->arr[sl->count] = x;
sl->count++;
}

3.出栈

//出栈
void STPop(ST* sl)
{
assert(sl);
sl->count–;
}

4.获取栈顶元素

//取栈顶数据
data STTop(ST* sl)
{
assert(sl);
return sl->arr[sl->count – 1];
}

5.获取栈中有效元素个数

//获取栈中数据个数
int STSize(ST* sl)
{
assert(sl);
//栈中的数据个数即为count的数
return sl->count;
}

6.判空（如果为空返回非0结果）

//判空（是空返回1，不是空返回0）
bool STEmpty(ST* sl)
{
assert(sl);
return sl->count==0;
}

7.销毁栈

//栈的销毁
void STDestory(ST* sl)
{
assert(sl);
free(sl->arr);
sl->arr = NULL;
sl->capacity = 0;
sl->count = 0;
}

三.栈的经典应用

20. 有效的括号 – 力扣（LeetCode）

思路：

遍历字符串，将左括号入栈，遇到最近的右括号，将最后入栈的左括号取出与其对比，直到字符串遍历完毕

———————————————————————————————————————————

注意：

1.若要是栈中的数据没有全部匹配，说明左括号多，右括号少，要返回false

2.先要判断栈是否为空，若为空则不能取出说明右括号提前出现，没有左括号与之匹配，要返回false

3.由于从头遍历看是否都匹配，不如直接看两个括号若是不匹配，直接就返回false，后面就不再匹配

———————————————————————————————————————————

详细代码（C语言实现）：

typedef char data;
typedef struct Stack
{
data* arr;
int count;
int capacity;
}ST;
//栈的初始化
void STInit(ST* sl)
{
assert(sl);
sl->arr = (data*)malloc(sizeof(data));
sl->count = 0;
sl->capacity = 1;
}
//栈的销毁
void STDestory(ST* sl)
{
assert(sl);
free(sl->arr);
sl->arr = NULL;
sl->capacity = 0;
sl->count = 0;
}
//入栈
void STPush(ST* sl, data x)
{
assert(sl);
//判断栈的空间
if (sl->count == sl->capacity)
{
//扩容
data* temp = (data*)realloc(sl->arr, sizeof(data) * 2 * sl->capacity);
//判断扩容是否成功
if (temp == NULL)
{
perror("空间为空");
exit(1);
}
else
{
sl->arr = temp;
//重新给定栈的空间
sl->capacity *= 2;
}
}
sl->arr[sl->count] = x;
sl->count++;
}
//出栈
void STPop(ST* sl)
{
assert(sl);
sl->count–;
}
//取栈顶数据
data STTop(ST* sl)
{
assert(sl);
return sl->arr[sl->count – 1];
}
//判空（是空返回1，不是空返回0）
bool STEmpty(ST* sl)
{
assert(sl);
return sl->count==0;
}
//获取栈中数据个数
int STSize(ST* sl)
{
assert(sl);
//栈中的数据个数即为count的数
return sl->count;
}
bool isValid(char* s) {
//将左括号放在栈里面，当遇到最近的右括号，判断是否与其相匹配
ST sl;
STInit(&sl);
while(*s)
{
if(*s=='('||*s=='{'||*s=='[')
{
STPush(&sl,*s);
}
else
{
if(STEmpty(&sl))
{
STDestory(&sl);
return false;
}
//若栈里没有左括号，会非法访问
char ch = STTop(&sl);
//取出数据后就要出栈
STPop(&sl);
//距离最近的两个括号若是不匹配直接返回false
if((ch=='('&&*s!=')')
|| (ch=='{'&&*s!='}')
|| (ch=='['&&*s!=']'))
{
STDestory(&sl);
return false;
}
}
++s;
}
//若栈不为空说明不匹配
bool ret=STEmpty(&sl);
STDestory(&sl);
return ret;
}

四.总结

1. 栈是先进后出结构

2. 核心操作：push / pop / top / isEmpty

3. 数组实现栈最简单高效

4. LeetCode 20 是栈最经典的面试题

5. 栈常用于：括号匹配、函数调用、表达式求值、浏览器后退

——————————————————————————————————————————–

本文从栈的原理到 C 语言实现，再到 LeetCode 实战，一步步带你入门栈。如果对你有帮助，欢迎点赞、收藏、关注，后续持续更新数据结构与算法！

下篇文章主要讲解队列的实现

【数据结构】C 语言实现栈（Stack）超详细入门 + LeetCode 实战

前言：

一.栈的概念