冰冰学习笔记：这些栈与队列的练习题，你会吗？
欢迎各位大佬光临本文章！！！
还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。
本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。
我的博客地址：bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=blog
https://blog.csdn.net/bingbing_bang?type=blog
我的gitee：冰冰棒 (bingbingsupercool) - Gitee.
系列文章推荐
冰冰学习笔记：这些链表练习题，你会吗？（上）
冰冰学习笔记：这些链表练习题，你会吗？（中）
冰冰学习笔记：这些链表练习题，你会吗？（下）
目录
系列文章推荐
前言
1.有效的括号
使用栈来实现
2.用栈实现队列
3.用队列实现栈
总结
前言
学习完栈与队列后，我们要将知识融会贯通，充分发挥这两种数据结构的优点，下面是几道使用栈和队列来完成的练习题。学会这些练习题会对栈与队列的认识更加深刻，使用也会逐渐变得得心应手。
1.有效的括号
题目链接：20. 有效的括号 - 力扣（LeetCode）
题目描述：给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。
使用栈来实现
什么意思呢？该题目就是给你一串只包含上述三种括号类型的字符串，判断字符串中的所有括号是否都一一对应，即所有的左括号 '(' 是否正好匹配所有的右括号 ')' 。
但是我们要知道，就算数目对的上也不一定就是匹配的。例如出现下面两种情况：
此种情况下虽然数目是对的，但是方向并不对，也就是说当遇到 左括号 '(' 时，下一个右括号必须为 ')' 否则就不能匹配成功。
那该如何解答呢？这里我们就要使用栈的特点了，栈的数据存储特点是先进后出。因此我们可以这样解答：在遇到左括号的时候进行入栈操作，在遇到右括号的时候进行出栈操作，然后判断此时字符串中的括号与出栈的括号是否匹配，如果匹配就继续向后移动，不匹配直接返回false，直到遍历完整个字符串。
基于上面的分析，我们的代码实现就比较简单了。首先我们将自己写好的栈复制到代码中，然后开始构建逻辑代码。代码分析如下图所示：
两个蓝色框圈起来的为特殊情况处理，如果一开始就遇到右括号，此时如果直接对其进行出栈操作，由于栈内部并没有数据，因此必然会导致程序错误，所以在出栈之前对其栈进行判空操作，如果为空则返回false，证明直接遇到了右括号，为错误形式。不为空在取出进行对比。
当循环遍历结束，我们并不能直接证明是否为正确形式，此时还需要对栈进行判空处理，栈为空，说明所有的括号匹配完毕，如果不为空，则说明有多余的左括号，所以也是错误形式。我们保存ret为判空的结果，栈为空ret中为true，返回的也是true，栈不为空，ret为false，返回的也是false。
实现代码：
//判断括号匹配问题bool isValid(char* s){ ST st; StackInit(&st); while ( *s ) { if ( *s == '(' || *s == '[' || *s == '{' ) { StackPush(&st, *s); s++; } else { if ( StackEmpty(&st) ) { StackDestroy(&st); return false; } else { char top = StackTop(&st); StackPop(&st); if ( (top == '(' && *s == ')') || (top == '{' && *s == '}') || (top == '[' && *s == ']') ) s++; else { StackDestroy(&st); return false; } } } } bool ret = StackEmpty(&st); StackDestroy(&st); return ret;}2.用栈实现队列
题目链接：232. 用栈实现队列 - 力扣（LeetCode）
题目描述：使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
push、pop、peek、empty)
该题目的意思是让我们使用两个栈来模拟实现一个队列，栈的性质是后进先出，而队列的性质是先进后出。因此，我们可以采用两个栈进行数据轮转来进出。
设计两个栈push和pop，一个栈负责存储数据，一个栈负责弹出数据。由于栈具有先进后出的性质，因此我们将数据存入到push栈中，例如存入数据1，2，3。如果直接出栈，出栈顺序为3，2，1。并不符合队列的出栈顺序1，2，3。那如果我们在调用出队函数时，将push栈的数据先弹出导入到pop栈中，数据从pop栈中弹出，此时栈push以3，2，1的顺序将数据放入到pop栈中，pop栈的进栈顺序为3，2，1。然后进行出栈操作，此时的出栈顺序为1，2，3。符合了队列先进先出的原则。
出队的时候我们要先判断pop栈是否为空，不为空则直接将数据从pop栈中弹出，如果为空，我们需要将push栈中的数据先导入pop栈，然后在完成出队操作。返回队顶元素，则直接返回pop栈不为空时的栈顶元素即可。队列为空则表明栈push与栈pop都为空。销毁队列，则需要先销毁两个栈的空间在销毁队列的空间。具体代码如下所示：
typedef struct{ ST pushst; ST popst;} MyQueue;MyQueue* myQueueCreate(){ MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->pushst); StackInit(&obj->popst); return obj;}void myQueuePush(MyQueue* obj, int x){ StackPush(&obj->pushst, x);}int myQueuePop(MyQueue* obj){ if ( StackEmpty(&obj->popst) ) { while ( !StackEmpty(&obj->pushst) ) { StackPush(&obj->popst, StackTop(&obj->pushst)); StackPop(&obj->pushst); } } int top = StackTop(&obj->popst); StackPop(&obj->popst); return top;}int myQueuePeek(MyQueue* obj){ if ( StackEmpty(&obj->popst) ) { while ( !StackEmpty(&obj->pushst) ) { StackPush(&obj->popst, StackTop(&obj->pushst)); StackPop(&obj->pushst); } } return StackTop(&obj->popst);}bool myQueueEmpty(MyQueue* obj){ return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);}void myQueueFree(MyQueue* obj){ StackDestroy(&obj->pushst); StackDestroy(&obj->popst); free(obj);}3.用队列实现栈
题目链接：225. 用队列实现栈 - 力扣（LeetCode）
题目描述：使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。
该题目与上一个题目相似，只不过需要使用队列先进先出的性质去实现栈后进先出的性质。有了上一题的铺垫，我们很容易想到使用两个队列相互倒换数据来完成。
首先创建两个队列q1，q2，使其组成栈的基本结构，然后进行初始化操作。在执行数据进栈功能时，先判断两个队列q1,q2是否为空，找到空的队列进行数据存放。在执行出队列操作时，我们需要先找到数据不为空的队列nonempty，然后将里面的n-1个数据倒换到另一个队列中，然后将队列nonempty的最后一个队列数据进行弹出操作。此时得到的就是最后进入队列的数据，从而满足了栈后进先出的操作。入栈出栈过程如下所示。
此时再次操作入栈函数，函数又会重新在q1，q2中寻找空队列进行数据插入。对于栈顶元素获取，无非是数据入队后返回不为空的队尾的数据，判断栈为空则为两个队列都为空。栈空间销毁则为先销毁队列的空间，然后释放掉栈的空间，具体代码如下所示。
代码实现：
typedef struct { Queue q1; Queue q2;} MyStack;MyStack* myStackCreate() { MyStack*ps=(MyStack*)malloc(sizeof(MyStack)); if(ps==NULL) { perror("malloc"); exit(-1); } QueueInit(&ps->q1); QueueInit(&ps->q2); return ps;}void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); }}int myStackPop(MyStack* obj) { Queue*emptyQ=&obj->q1; Queue*nonemptyQ=&obj->q2; if(!QueueEmpty(&obj->q1)) { emptyQ=&obj->q2; nonemptyQ=&obj->q1; } while(QueueSize(nonemptyQ)>1) { QueuePush(emptyQ,QueueFront(nonemptyQ)); QueuePop(nonemptyQ); } QueueDataType top=QueueFront(nonemptyQ); QueuePop(nonemptyQ); return top;}int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) {return QueueBack(&obj->q1); } else {return QueueBack(&obj->q2); }}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj);}总结
栈与队列的练习题总体来说并不难，只要深刻理解了栈与队列的性质就能将这些练习题完全搞懂，对于练习题来说，还有一种循环队列的实现，作者使用链表与数组两种方式进行了搭建，这里就不多做介绍，有兴趣的可以自行去仓库下载观看。
循环队列练习题代码：循环队列两种形式实现，链表与数组 · a1d212e · 冰冰棒/数据结构仓库 - Gitee.com
