当前位置：首页 > backend >正文

C语言：栈的实现和剖析

backend 2025/8/11 17:07:56

引言

一、栈的基本概念

1.1、栈的定义

1.2、相关概念

二、栈的实现

2.1、栈的基本结构

2.2、初始化栈

2.3、入栈

2.4、判断栈是否为空

2.5、出栈

2.6、取栈顶元素

2.7、获取栈中有效元素的个数

2.8、栈的销毁

三、练习：括号匹配问题

结语

引言

在数据结构的世界里，栈（Stack）以其独特的“后进先出”（LIFO）特性，成为一个实用且重要的线性结构。它无处不在，从函数调用的内部机制到表达式求值，再到浏览器的前进/后退功能，栈的身影随处可见。

本篇博客，我们将深入C语言的底层，亲手构建并剖析栈的实现。我们将探讨如何在C语言中灵活运用数组或链表来抽象出栈的本质操作——压栈（Push）和弹栈（Pop），并理解其背后的原理与细节。无论你是数据结构初学者，还是希望巩固C语言编程技能，相信本篇都能为你呈现一个清晰、生动的栈实现之旅。

一、栈的基本概念

1.1、栈的定义

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作。

栈就是先进后出，后进先出

1.2、相关概念

栈顶：进行数据插入或删除操作的一端

栈底：不进行数据插入或删除操作的一端

压栈：栈的插入操作，也叫入栈，进栈

出栈：栈的删除操作

二、栈的实现

2.1、栈的基本结构

前面说了，栈是一种线性表，而目前我们所学的线性表只有顺序表和链表，我们应该用那种数据结构去实现栈呢？其实两者都可以，但是大部分的栈还是由顺序表实现的

下面就是用顺序表定义栈结构：

//定义栈的结构
typedef int StackDataType;
typedef struct Stack
{StackDataType* arr;    //顺序表int top;               //栈顶（元素个数）int capacity;          //容量
}Stack;

这里的成员 top 是指栈的栈顶元素的下标+1 ，同时也是栈的元素个数的含义。

2.2、初始化栈

栈的初始化很简单，就是给栈的结构成员赋一个初始值，当然，top 和 capacity就赋0了，arr指针是赋NULL了

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

2.3、入栈

这里放一个设定，入栈和出栈都是在顺序表的末尾进行。（当然也可以设置成顺序表的头部，只要你不嫌麻烦）

入栈需要先判断空间容量是否足够？不够，扩容，然后在入栈

void StackPush(Stack* ps, StackDataType x)
{assert(ps);//判断容量是否足够？if (ps->top == ps->capacity){//扩容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;StackDataType* tmd = (StackDataType*)realloc(ps->arr ,sizeof(StackDataType) * newCapacity);if (tmd == NULL){perror("malloc fail!");exit(1);}ps->arr = tmd;ps->capacity = newCapacity;}//入队ps->arr[ps->top++] = x;
}

注意扩容还要保留原数据，所以用realloc！

2.4、判断栈是否为空

判断栈是否为空非常简单，就看栈中的个数为不为0就好了

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

2.5、出栈

出栈和顺序表一样，只用 size--就可以了，后面插入数据会自己覆盖的。别忘了要判断栈是否为空

//出栈
void StackPop(Stack* ps)
{assert(!StackEmpty(ps));ps->top--;
}

2.6、取栈顶元素

刚才说的是出栈，而现在是取栈顶元素，二者是不一样的，但经常搭配使用。

和出栈一样，栈里面有东西才能返回，因此要判断栈是否为空

StackDataType StackTop(Stack* ps)
{assert(!StackEMpty(ps));return ps->arr[ps->top - 1];
}

2.7、获取栈中有效元素的个数

这个直接把个数返回就好了

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

2.8、栈的销毁

需要注意的是，栈中的数组是通过malloc开辟空间，最后应该用 free 释放，但是，为了防止为初始化的栈销毁，所以应该先判断一下

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

三、练习：括号匹配问题

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

这道题就需要用到栈，遍历该数组，遇见左符号就入栈，遇见右符号就出栈，并一直匹配，直到栈为空，如果遍历完，栈不为空，那就返回不匹配。

像上述动图那样，遍历完数组后栈内还有剩余，那么就返回 false ，同样，如果中途符号不匹配，那么也是返回 false ，其余情况返回 ture

具体代码如下：

bool isValid(char* s) 
{int length = strlen(s);if(length % 2 != 0){return false;}//创建一个栈Stack ps;StackInit(&ps);//遍历字符串，将每个字符串压入栈中char* s2 = s;while(*s2 != '\0' ){//是左边字符就入栈，否则就出栈比较if(*s2 == '(' || *s2 == '{' || *s2 == '['){StackPush(&ps , *s2);}else{if(ps.top == 0){return false;}SDataType ch = StackTop(&ps);StackPop(&ps);//如果if(*s2 ==')' && ch != '(' ||*s2 == '}' && ch != '{' ||*s2 == ']' &&ch != '['){return false;}}//判断完成后s2++;}//循环完后，还要检查栈是否为空，如果不为空，返回fasleif(ps.top != 0){StackDestory(&ps);return false;}StackDestory(&ps);return true;
}