栈和队列的习题详解（1）：有效的括号
前言：
在差不多二十天前小编写过栈和队列的详解，本来我想当时写完那两个结构之后就继续写它们的习题，但是写完那几篇博客以后，我就开始狂玩了十几天，我在上篇博客也说过，导致我在刚开学的时候就忘记了这个习题的写法了，再次听完习题讲解后，我痛定思痛，决定现在立马写篇博客来对于习题的讲解，下面废话不多说，开始今天的习题之旅~
目录
1.有效的括号
1.1.题目的展示
1.2.题目的大致解释
1.3.习题的文字讲解
1.4.习题代码以及提交结果展示
2.总结
正文：
1.有效的括号
1.1.题目的展示
老规矩，再讲借题目之前，小编先把题目地址给出来：20. 有效的括号 - 力扣（LeetCode）
1.2.题目的大致解释
这个题目乍一看，似乎是一个比较难以理解的题目，小编当初也是认为这个题目理解起来算是比较有难度的，此时这个题目是括号配对问题，可能很多读者朋友会问：括号是如何进行配对？我先来稍微解释一下这个题目：
括号配对其实就是我们所认识的小括号，中括号，大括号，它们想要实现括起来这个功能，那就必须要左右括号是一起的，类似下图这样：
当然，括号和括号之间也是可以进行复合的，但是左括号和右边=括号是必须配对在一起的，就类似下图这样：
当然，也有不配对的情况，就比如左括号或者右括号是单独出现的，后者是左右括号不匹配的情况，如下图所示：
以上便是这个题目让我们解决的大致问题，当时我还是有点没有思路的，但是小编当初是学习完栈和队列以后在看的这些算法题，我自然而然的认为这个题必然和栈和队列有关，但我不知道到底是哪个数据结构，于是乎小编在听完老师的讲解以后，便知道了这个题的做题方法，这个题是用栈来实现的，实现的方法也是很巧妙，下面小编就开始对这个题目进行讲解。
1.3.习题的文字讲解
这个解题方法是通过栈的结构来实现的，小编在之前的博客说过，栈的结构特点是后进先出，由栈顶入，从栈顶出，类似一个瓶子一样，所以小编的做题方法便是我们可以把左括号放入栈中，然后如果我们碰到了右括号，那么我们便可以通过比较栈顶元素和右括号是否配对来看看这个括号是否有效，因为小编刚刚也说过，栈有着后进先出的特点，所以最后一个进的左括号和第一个右括号自然就是配对的，所以我们比较完成以后，就可以出栈，然后继续和之后进行入栈或者配对，所以才此时我们肯定是用到了循环的，并且此时我们可以通过使用指针的方法来对于字符串的每一个字符进行读取，所以此时循环的条件自然就是这个指针不能够是‘\0’，我们的目的就是遍历整个字符串，来看看括号是否配对，如果成功配对了的话，此时我们的栈中的元素肯定就是空的，如果栈不为空，证明此时括号并不匹配，可能出现了左括号多于右括号的情况，所以循环结束以后，我们还得再写一个if语句来判断栈是否为空，如果不为空直接返回false，如果为空就返回true，此时这个题目算是写完了，可能很多读者朋友看到这么长的文字，可能会不想去读，所以小编就拿一个例子来通过图文的方式来带领各位去知道这个题目的做题方法：
1.4.习题的图文搭配代码讲解
首先，我们需要先把栈这个数据结构写出来（我的建议就是直接把自己以前写过的复制粘贴过来，毕竟我们都是CV程序员（狗头保命）），然后我们便可以设置好一个栈，然后设置好一个指针去指向字符串，我们通过这个指针来对字符串每一个字符进行读取，然后我们便可以进入到循环，首先我们需要先确保此时指针的指向是否为左括号，如果就是左括号，那么便可以入栈，很明显，此时就是做括号，所以我们选择入栈，下面是相应的代码和图：
char* arr = s;ST s1;STInit(&s1);while (*arr != '\0') {if (*arr == '(' || *arr == '[' || *arr == '{') {STPush(&s1, *arr);}
之后，我们让指针往后走一步，再去判断此时是否为左括号，很明显此时为右小括号，所以此时我们就需要和栈顶元素进行配对，。但是这里有一个需要注意的点，我们不能直接将栈顶数据和右括号进行配对，因为此时我们无法确保真的有栈顶元素，就比如上面小编举例的只有右括号的情况，所以此时我们需要去判断这个栈是否为空，如果为空的话我们直接返回false，如果不为空的话我们在进行配对操作，配对成功我们出栈，然后让字符串继续往后找，如果不匹配直接返回false，很显然，此时可以配对，所以我们直接进行出栈就好了，代码和解释图如下图所示：
} else {if (panduan(&s1))return false;char ch = STTop(&s1);if (ch == '(' && *arr == ')' || ch == '[' && *arr == ']' ||ch == '{' && *arr == '}') {STPop(&s1);} else {STDestroy(&s1);return false;}}arr++;
之后我们在通过循环继续往后找左括号，并且搭配右括号进行配对，经过不断的重复我们便可以结束循环，当然我们在结束循环的时候，并不代表着此时括号是一定匹配的，所以此时我们仍需判断栈是否为空，只有栈为空，才可以说明此时括号是有效的，否则直接返回false，此时不难发现这个例子是正确的，最后会呈现下面的效果：
此时我们就实现了有效括号的配对，也代表着这个题目正式的写完了，可能点开这篇文章的读者朋友只想知道代码如何写，或者听完了想看看完整代码是什么样子的，不要着急，下面就进行代码展示环节！
1.4.习题代码以及提交结果展示
typedef char STDataType;
typedef struct stack {STDataType* arr; // 数组，类型可能不是一定的所以用typedef替换一下int capacity; // 总空间大小int top; // 栈顶表示
} ST;
void STInit(ST* ps) {ps->arr = NULL;ps->capacity = ps->top = 0; // 总空间个数和有用空间个数都初始化为0
}
void STDestroy(ST* ps) {if (ps->arr) // 先判断是否进行动态内存开辟了{free(ps->arr);}ps->capacity = ps->top = 0;
}
void STPush(ST* ps, STDataType x) // 类似顺序表的尾插
{if (ps->capacity == ps->top) {int newcaopacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* arr1 =(STDataType*)realloc(ps->arr, newcaopacity * sizeof(STDataType));assert(arr1);ps->arr = arr1;ps->capacity = newcaopacity;} // 扩容完成ps->arr[ps->top++] = x;
}
bool panduan(ST* ps) {assert(ps);return ps->top == 0; // 这个是来判断栈是不是空了
}
void STPop(ST* ps) {assert(ps);assert(!panduan(ps));ps->top--;
}
STDataType STTop(ST* ps) {assert(ps);assert(!panduan(ps));return ps->arr[ps->top - 1];
}
int STSize(ST* ps) { return ps->top; }
bool isValid(char* s) {char* arr = s;ST s1;STInit(&s1);while (*arr != '\0') {if (*arr == '(' || *arr == '[' || *arr == '{') {STPush(&s1, *arr);} else {if (panduan(&s1))return false;char ch = STTop(&s1);if (ch == '(' && *arr == ')' || ch == '[' && *arr == ']' ||ch == '{' && *arr == '}') {STPop(&s1);} else {STDestroy(&s1);return false;}}arr++;}if (!panduan(&s1))return false;STDestroy(&s1);return true;
}
2.总结
本来小编是都想着直接把栈和队列四个习题在一个文章进行呈现的，但在我写完有效的括号这个习题后，发现字数已经是很多了，其它三个题都涉及着我们需要写一些函数的实现，如果一起写就不好体现每个题的价值，于是这次我就大胆尝试把这些小题都分出来写，由于这是第一次尝试，小编肯定有写的不足的情况，若有错误或者写的不好，恳请各位大佬在评论区指出，我一定会及时汲取自己的不足来对之后的文章进行改善，今天这个题目是很重要的，各位读者朋友一定要好好去理解，那么，我们下一篇文章见啦！