首页云计算栈的详解和例题（力扣有效括号）

栈的详解和例题（力扣有效括号）

时间2024-07-26 00:00:24发布ongwu分类云计算浏览55

感谢各位大佬的光临，希望和大家一起进步，望得到你的三连，互三支持，一起进步

个人主页：LaNzikinh-CSDN博客

收入专栏:初阶数据结构_LaNzikinh篮子的博客-CSDN博客

文章目录 前言一.什么是栈二.栈的实现三.例题（力扣）总代码

前言

之前讲了，很多关于栈的习题，还有栈与队列的互相转换，还是补一篇栈的详解

一.什么是栈

栈（stack）是一种只允许在一端进行插入和删除操作的线性表。这一端称为栈顶，另一端称为栈底。栈的特点是后进先出（LIFO），即最后进入的元素最先出来。栈可以用来存储局部变量和一些数据，当函数或线程执行完毕，栈就会释放空间。

二.栈的实现

这样的实现它分为两种，一种是用数组去实现栈，另一种就是用链表去实现栈，我们这里主要讲的是用数组去实现栈，用链表实现栈又叫做链式栈，如果用尾做为栈顶那么尾插尾删就要设计成双向链表，否则删除数据效率会很低。

2.1结构

注意：初始化时把top=0的话，top可以看成有栈中的元素总数，不是栈顶的元素下标！！

typedef int STDataType;
typedef struct stack
{
STDataType* a;
int top;
int capacity
}ST;

其实就可以把它看成一个顺序表，top就是size的意思，它用来控制栈顶的元素的

2.2初始化

初始化时，top给的是0的话，意味着top栈顶数据的指向下一个，top给-1的话，意味着top就是栈顶数据

void stackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;//ps->top=-1;
ps->capacity = 0;
}

2.3放入数据

这里和顺序表的扩容和插入一模一样

void stackPush(ST* ps, STDataType x)
{
assert(ps);
//检查扩容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);
assert(tmp);
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}

 2.4删数据和取栈顶元素

我初始化的top为0，所以取栈顶元素的下标是top-1

void stackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
STDataType stackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
//我初始化的top为0，所以取栈顶元素的下标是top-1
return ps->a[ps->top -1 ];
}

2.5检查栈中还要元素和释放

bool stackEmpty(ST* ps)
{
assert(ps);
//说明栈里没有元素了
if (ps->top == 0)
return true;
else
return false;
}
void stackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}

然后我们来看一道例题

三.例题（力扣）

给定一个只包括 (，)，{，}，[，] 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()" 输出：true 输入：s = "(]" 输出：false

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

思路:利用栈算法先搭建一个栈，然后我们先让左括号入栈，在让左括号出栈和右括号匹配

注意:因为如果用C语言去写，c语言中的库没有栈的，所以必须自己搭建一个栈，就是我们上面写的

3.1

我们先断言一下传来的不能是空指针，然后对栈进行初始化，然后设置一个循环，意思是说等这个字符串走完了之后这个循环就出了，第一步判断我们先得让左括号入栈，如果是左括号的就入栈，然后字符串加加

assert(s);
ST st;
stackInit(&st);
while (*s)
{
if (*s == ( || *s == { || *s == [)
{
stackPush(&st, *s);
s++;
}

3.2

然后如果不是左括号我们就可以进行第一次判断了，如果遇到了右括号，但是栈里没有数据，说明前面没有右括号不匹配，我们直接退出，如果不是这个错误的话，我们就可以取栈顶元素，把这个括号取出来删掉，然后进行左括号匹配，如果不是就直接退出，注意:stackDestroy(&st);为什么我要提前放不在后面放，因为我在这里就退出了存在开屏内存没有释放会造成内存泄露。

else
{
if (stackEmpty(&st))
{
return false;
}
STDataType top = stackTop(&st);
stackPop(&st);
if ((*s == ) && top != () || (*s == } && top != {) || (*s == ] && top != [))
{
stackDestroy(&st);
return false;
}
else {
s++;
}
}

3.3

如果只有左括号没有右括号呢，所以我的结尾判断还需要特殊一点，如果栈里还有元素的话就说明还存在左括号没有出去没有匹配，所以我也不能返回正确

bool ret = stackEmpty(&st);
stackDestroy(&st);
return ret;

总代码

注意这个题目是符号判断，所以我的STDataType是char类型的

typedef char STDataType;
typedef struct stack
{
STDataType* a;
int top;
int capacity;
}ST;
void stackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void stackPush(ST* ps, STDataType x)
{
assert(ps);
//检查扩容
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
assert(tmp);
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void stackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void stackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
STDataType stackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
bool stackEmpty(ST* ps)
{
assert(ps);
if (ps->top == 0)
return true;
else
return false;
}
bool isValid(char* s)
{
assert(s);
ST st;
stackInit(&st);
while (*s)
{
if (*s == ( || *s == { || *s == [)
{
stackPush(&st, *s);
s++;
}
else
{
if (stackEmpty(&st))
{
return false;
}
STDataType top = stackTop(&st);
stackPop(&st);
if ((*s == ) && top != () || (*s == } && top != {) || (*s == ] && top != [))
{
stackDestroy(&st);
return false;
}
else {
s++;
}
}
}
bool ret = stackEmpty(&st);
stackDestroy(&st);
return ret;
}

Ongwu博客 版权声明：以上内容未经允许不得转载！授权事宜或对内容有异议或投诉，请联系站长，将尽快回复您，谢谢合作！

展开全文READ MORE
Avira System Speedup(Avira系统加速专业版) Pro v7.3.0.501 中国移动召开京津冀协同发展工作推进会

游客 回复需填写必要信息
↑