Data Structure--栈和队列相关例题--括号匹配问题--用队列实现栈--用栈实现队列 矫情吗;* 2022-10-30 15:21 131阅读 0赞 ## 1.括号匹配问题 ## 给定一个只包括 ‘(’,’)’,’\{’,’\}’,’\[’,’\]’ 的字符串 s ,判断字符串是否有效。 条件: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 //找到了左边的括号,就将其入栈,当找到了右边匹配的,则将左边的出栈,这样栈就为空,就成功匹配 bool isValid(char * s){ stack st; stackInit(&st); //初始化 static char map[][2] = { { '(', ')' }, { '[', ']' }, { '{', '}' } }; //检测括号 while (*s){ //存在字符时 int i = 0; for (; i<3; ++i){ //利用循环找到左边对应的括号 if (*s == map[i][0]){ stackPush(&st, *s); //找到就入栈 ++s; break; //结束循环 } } if (i == 3){ //如果没有找到,为3则没找到 if (stackEmpty(&st)) //判断如果为空,则直接返回 return false; char topchar = stackTop(&st); //定义一个字符指向栈顶 for (int j = 0; j<3; ++j){ //寻找有后面括号的字符 if (*s == map[j][1]){ //存在字符于后面的时候 if (topchar == map[j][0]){ //如果找到 stackPop(&st); //让其出栈 ++s; break; } else return false; //没找到则返回错误 } } } } if (stackEmpty(&st)) //字符寻找完后,如果为空 return true; //则证明成功匹配了,为真 return false; } ## 2.用队列实现栈 ## 对于这段代码利用了队列的接口,具体看这里的链接: [点击这里][Link 1] typedef struct{ Queue q; //初始开辟 } MyStack; //创建元素 MyStack* myStackCreate() { MyStack* ms = (MyStack*)malloc(sizeof(MyStack)); //动态开辟 queueInit(&ms->q); //调用栈的初始化接口 return ms; } //实现入栈 void myStackPush(MyStack* obj, int x) { queuePush(&obj->q, x); //直接调用队列的入队就可以实现了 } //实现出栈 int myStackPop(MyStack* obj) { int ret; //定义整型变量 int size = queueSize(&obj->q); //调用队列的接口计算出大小 while (size>1){ //当存在很多的时候 int front = queueFront(&obj->q); //队列队首元素 queuePop(&obj->q); //出队 queuePush(&obj->q, front); //front进行入队 --size; //循环 } ret = queueFront(&obj->q); //进行入队 queuePop(&obj->q); //出队 return ret; } //求栈顶 int myStackTop(MyStack* obj) { return queueBack(&obj->q); //队尾的元素 } //判空 bool myStackEmpty(MyStack* obj) { return queueEmpty(&obj->q); //直接调用队列实现的操作 } void myStackFree(MyStack* obj) { queueDestory(&obj->q); //队列式销毁 free(obj); //释放节点 } ## 3.用栈实现队列 ## ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70] 对于这段代码利用了栈的接口,具体看这里的链接: [点击这里][Link 2] typedef struct { stack pushST; //定义两个栈 stack popST; } MyQueue; //创建 MyQueue* myQueueCreate() { MyQueue* mq = (MyQueue*)malloc(sizeof(MyQueue)); //动态开辟 stackInit(&mq->pushST, 10); stackInit(&mq->popST, 10); //对两个进行分别初始化 return mq; } //入队 void myQueuePush(MyQueue* obj, int x) { stackPush(&mq->pushST, x); //直接调用入栈操作 } //出队 int myQueuePop(MyQueue* obj) { int ret; //定义整形数组 if (stackEmpty(&obj->popST)){ //判空 while (stackEmpty(&obj->pushST) != 1){ //判空并循环 int top = stackTop(&obj->pushST); //找出栈顶 stackPop(&obj->pushST); //出栈 stackPush(&obj->popST, top); //进入到第二个栈内 } } ret = stackTop(&obj->popST); //表示第二个栈的栈顶 stackPop(&obj->popST); //出栈 return ret; //返回值 } //最前的元素(和上面的代码一致) int myQueuePeek(MyQueue* obj) { if (stackEmpty(&obj->popST)){ //判空 while (stackEmpty(&obj->pushST) != 1){ //循环并判空 int top = stackTop(&obj->pushST); //找出栈顶 stackPop(&obj->pushST); //出栈 stackPush(&obj->popST, top); //进入第二个栈 } } return ret = stackTop(&obj->popST); //表示第二个栈的栈顶 } //判空 bool myQueueEmpty(MyQueue* obj) { return stackEmpty(&obj->pushST) && stackEmpty(&obj->popST);//调用接口,两个栈之间是与操作 } //释放 void myQueueFree(MyQueue* obj) { stackDestory(&obj->pushST); //对两个栈进行分别销毁 stackDestory(&obj->popST); free(obj); //释放节点 } 今天讲的有点难度,大家多注意细节,注意对于队列和栈互相转换的理解,已结对前面代码的理解,代价多看看多敲敲,一起加油!!! [Link 1]: https://blog.csdn.net/weixin_46554582/article/details/113874587 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/8af80211b3c34b358a3bea46787a13d2.png [Link 2]: https://blog.csdn.net/weixin_46554582/article/details/113874048
还没有评论,来说两句吧...