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

【数据结构】栈与【LeetCode】20.有效的括号详解

article 2026/2/18 21:14:15

一、栈
- 1、栈的概念及结构
- 2、栈的实现
- 3、初始化栈和销毁栈
- 4、打印栈的数据
- 5、入栈操作---栈顶
- 6、出栈---栈顶
- - 6.1栈是否为空
  - 6.2出栈---栈顶
- 7、取栈顶元素
- 8、获取栈中有效的元素个数
二、栈的相关练习
- 1、练习
- 2、AC代码

个人主页，点这里~
数据结构专栏，点这里~

在这里插入图片描述

一、栈

1、栈的概念及结构

栈：⼀种特殊的线性表，其只允许在固定的⼀端进行元素的插入和删除元素操作。进行数据插入和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
在这里插入图片描述
以上这张图片很好的反映了栈的结构，及出入栈的顺序。

2、栈的实现

栈的实现⼀般可以使用数组或者链表实现，相对而言数组的结构实现更优⼀些。因为数组在尾上插入，数据的代价比较小。数组在尾上插入整型数据只需要增加4个字节，但链表增加的字节就大的多了。

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;     //指向栈顶位置int capacity;//数据容量
}ST;

3、初始化栈和销毁栈

我们已经知道用什么方法实现栈，并且已经将栈的结构写出来了，接下来就该初始化了。
初始化：

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

初始化栈十分简单，只需把arr数组置为空，栈顶top和容量capacity置为0即可。

销毁：

void StackDestroy(ST* ps)
{if (ps->arr)//如果不为NULL{ps->arr = NULL;}ps->top = ps->capacity = 0;
}

以上就是栈的初始化以及销毁的代码了，和我们讲顺序表的时候差不多。

4、打印栈的数据

void SPrint(ST* ps)
{assert(ps);for (int i = 0;i < ps->top;i++){printf("%d", ps->arr[i]);if (i < ps->top - 1){printf("->");}}
}

5、入栈操作—栈顶

我们知道栈只能从栈顶入数据和出数据，所以我们就大概知道如何入栈了。

//入栈---栈顶
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity)//如果栈空间满了就增容{int newcapacity = ps->capacity == 0 ? 4 : 2 * ps -> capacity;STDataType* set = (STDataType*)realloc(ps->arr,sizeof(STDataType) * newcapacity);if (set == NULL){perror("realloc fail!");return 1;}ps->arr = set;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}

以上是入栈的代码，但在入栈之前呢，我们要考虑栈空间是不是满了，也就是栈顶是不是和容量一样大，如果满了，我们需要增容，在进行增容之前，我们还要考虑top和capacity是不是都为0，如果为0的话，我们要把容量大小置为4，否则的话容量扩大为二倍。

测试代码：

#include "Stack.h"void test()
{ST plist;StackInit(&plist);StackPush(&plist, 1);StackPush(&plist, 2);StackPush(&plist, 3);SPrint(&plist);
}int main()
{test();return 0;
}

测试结果：
在这里插入图片描述

6、出栈—栈顶

在实现出栈之前我们要考虑栈里面的元素是否为空，如果为空就终止操作，所以我们先写一个判空函数，这样我们就可以在出栈之前知道栈是否为空了。

6.1栈是否为空

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

这里用到了bool类型记得要加上#include<stdbool.h>头文件。

6.2出栈—栈顶

void StackPop(ST* ps)
{assert(!StackEmpty(ps));ps->top--;
}

这里实现出栈是只需要实现top减一即可，因为我们不会访问top之后的元素。

7、取栈顶元素

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

这里取栈顶元素时，我们只需要判断一下栈是否为空，再将栈顶元素返回即可。

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

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

以上就是栈的常见操作，接下来让我们做一道练习题试一下吧！

二、栈的相关练习

1、练习

题目描述：
在这里插入图片描述
题目链接，点击这里~

没有做过的，可以先看题目思考一下，下面会给出题解。

我们根据题目描述可以知道题目让我们判断括号匹配是否正确，如果正确返回true，如果错误返回false。
我们在利用栈思想(先进后出)进行求解的时候，可以当遇到左括号让它入栈，然后再遇到右括号的时候让栈顶的和它匹配(在括号匹配的情况下，最后出现的左括号总与最先出现的右括号匹配)，如果不匹配就一定是非法的，返回false，如果都匹配的话就是合法的，返回true。这里可以用数组模拟栈。我们在遇到左括号例如'('时我们可以在栈中保存')'，这样在比较的时候容易比较。

特殊情况一：
字符数目是奇数，只要是奇数就一定不匹配，直接返回false。

    int len=strlen(s);if(len%2==1){return false;}

特殊情况二：
如果全是左括号，那么最后栈顶top一定大于0，而如果是正确匹配的情况下，到最后top肯定是0。因为我们初始化top为0。所以遇到top大于0的情况直接返回false。

    //到最后top大于0的情况if(top>0){return false;}

如果全是右括号，那么在比较的时候，top一定为0，此时栈中没有元素，也就无法比较，所以遇到比较时top为0的情况也直接返回false。

            if(top==0||s[i]!=stack[--top]){return false;}

2、AC代码

AC代码：

bool isValid(char* s) 
{int len=strlen(s);if(len%2==1){return false;}char stack[10005];int top=0;int i;for(i=0;i<len;i++){if(s[i]=='('){stack[top++]=')';}else if(s[i]=='['){stack[top++]=']';}else if(s[i]=='{'){stack[top++]='}';}else{if(top==0||s[i]!=stack[--top]){return false;}}}if(top>0){return false;}return true;
}

总结：
以上就是本期博客分享的全部内容啦！如果觉得文章还不错的话可以三连支持一下，你的支持就是我前进最大的动力！
技术的探索永无止境! 道阻且长，行则将至！后续我会给大家带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～

目录

一、栈