✨✨所属专栏：LeetCode刷题专栏✨✨
✨✨作者主页：嶔某✨✨
上一篇：数据结构_栈和队列(Stack & Queue)-CSDN博客
有效的括号
解析:
这里我们用数组实现的栈来解决这个问题，在有了栈的几个基础接口之后，我们运用这几个接口解决问题。
首先新建一个栈并初始化，进入循环如果当前指针指向的字符元素为左括号 {([ 就入栈，反之就出栈，之后判断指针指向的字符是否和出栈的字符左右括号相匹配。
( (top == '{'&& *s != '}') || (top == '['&& *s != ']') || (top == '('&& *s !=')') )
每次循环后s++，如果 *s != '\0' 就进行下一次循环。
写完后提交会发现当只有一个元素的时候这种写法是不能过的
这里我们在else里面做一个判空，因为如果进了else里面，就说明这是个右括号，那么栈里面一定有其所对应的左括号，如果这时后栈为空，那么显然括号之间是不匹配的。这样就很好的解决了诸如此类的问题。
if(STEmpty(&S))
{
STDestroy(&S);
return false;}
最后s遇到了 '\0' 循环结束，我们判断栈是否为空，如果为空返回true，否则栈中还有元素括号之间也是不匹配的。
return STEmpty(&S);
可以这么理解这两段代码：一个判断了左括号是否多了，一个判断了右括号是否多了。
示例代码：
function/数据结构_栈 · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)
https://gitee.com/wang-qin928/c-language-learning/tree/master/function/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%A0%88
bool isValid(char* s)
{
ST S;
STInit(&S);
while(*s)
{
if(*s == '{' || *s == '[' || *s == '(')
{
STPush(&S,*s);
}
else
{
if(STEmpty(&S))
{
STDestroy(&S);
return false;
}
char top = STTop(&S);
STPop(&S);
if((top == '{'&& *s != '}')||
(top == '['&& *s != ']') ||
(top == '('&& *s !=')'))
{
STDestroy(&S);
return false;
}
}
s++;
}
return STEmpty(&S);
}用队列实现栈
解析：
这里我们使用数组实现的队列，只需要创建两个队列，把数据在两个队列之间互相导就行了。
定义结构体MyStack：
将mystack结构体里面创建两个队列q1、q2。
myStackCreate函数：
malloc出结构体pst的内存空间 ，并将q1、q2交给 QueueInit函数，返回这个结构体。
myStackPush函数：
将数据方放进 QueuePush，入队列q1就行。
myStackPop函数：
将q1队列的数据转到q2里面，最后剩一个数据不转，直接删除，之后再将数据从q2转到q1里面。返回删除的那个数据。
myStackTop函数：
和上一个函数一样，只不过myStackTop不删除数据，直接返回就好了。
myStackEmpty函数：
return !QueueSize(&(obj->q1));
myStackFree函数：
这里一定要先释放q1、q2的空间之后再释放pst。
示例代码：
function/队列 · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)https://gitee.com/wang-qin928/c-language-learning/tree/master/function/%E9%98%9F%E5%88%97
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&(pst->q1));
QueueInit(&(pst->q2));
return pst;
}
void myStackPush(MyStack* obj, int x) {
QueuePush(&(obj->q1),x);
}
int myStackPop(MyStack* obj) {
while(QueueSize(&(obj->q1)) != 1)
{
QueuePush(&(obj->q2),QueueFront(&(obj->q1)));
QueuePop(&(obj->q1));
}
int tmp = QueueFront(&(obj->q1));
QueuePop(&(obj->q1));
while(QueueSize(&(obj->q2)))
{
QueuePush(&(obj->q1),QueueFront(&(obj->q2)));
QueuePop(&(obj->q2));
}
return tmp;
}
int myStackTop(MyStack* obj) {
return QueueBack(&(obj->q1));
}
bool myStackEmpty(MyStack* obj) {
return !QueueSize(&(obj->q1));
}
void myStackFree(MyStack* obj) {
Destory(&(obj->q1));
Destory(&(obj->q2));
free(obj);
}用栈实现队列
解析：
此题与上题思路差不多，有一些细节上的改变，我们在代码里面细说。
定义结构体MyQueue：
创建两个栈st1、st2
myQueueCreate函数：
为MyQueue结构体malloc一块空间，将里面的st1、st2交给 STInit函数。
myQueuePush函数：
直接利用STPush函数插入就行。
myQueuePeek函数：
这里判断一下，如果st2为空的话，就将st1的数据转到st2来，取栈顶元素返回（转过来的时候数据会反过来）如果st2不为空，就直接返回st2栈顶元素。
myQueuePop函数：
这里本来也是要进行判断、转数据的，但是我们可以简化一下代码，直接调用myQueuePeek返回值存起来，这样st2必然就有数据，我们就可以直接pop掉st2里面的数据。
myQueueEmpty函数：
只有st1、st2同时为空，这个队列才为空。
myQueueFree函数：
先用 STDestroy释放掉st1、st2的空间，之后再free掉obj。
总结：此题目不用将st2的数据再转回到st1里，相当于st2是专门用来出数据的，st1专门用来入数据的。
示例代码：
function/数据结构_栈 · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)https://gitee.com/wang-qin928/c-language-learning/tree/master/function/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%A0%88
typedef struct {
ST st1;
ST st2;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* Q = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&(Q->st1));
STInit(&(Q->st2));
return Q;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&(obj->st1),x);
}
int myQueuePop(MyQueue* obj) {
int tmp = myQueuePeek(obj);
STPop(&(obj->st2));
return tmp;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&(obj->st2)))
{
while(!STEmpty(&(obj->st1)))
{
STPush(&(obj->st2),STTop(&(obj->st1)));
STPop(&(obj->st1));
}
return STTop(&(obj->st2));
}
else
{
return STTop(&(obj->st2));
}
}
bool myQueueEmpty(MyQueue* obj) {
return (STEmpty(&(obj->st1)) && STEmpty(&(obj->st2)));
}
void myQueueFree(MyQueue* obj) {
STDestroy(&(obj->st1));
STDestroy(&(obj->st2));
free(obj);
}本期博客到这里就结束了，如果有什么错误，欢迎指出，如果对你有帮助，请点个赞，谢谢！
