✨✨所属专栏: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);
}
本期博客到这里就结束了,如果有什么错误,欢迎指出,如果对你有帮助,请点个赞,谢谢!