引言
本篇文章将介绍关于栈和队列的一些基础OJ题目，掌握后一定能让你对栈和队列的理解更上一层楼！
如果你对栈和队列的基础实现有问题的话，可以观看这篇博客哦：栈和队列的基本实现 – 小园得志
1.用队列实现栈
题目链接：225. 用队列实现栈 – 力扣（LeetCode）
具体思路：
首先我们要明确的清楚队列和栈最大的区别是什么，回顾栈和队列的知识，队列的特点是先进先出，而栈的特点却是后进先出，所以我们只要实现了能用队列实现后进先出，就可以实现栈了
如果我们只有一个队列的话，要实现后进先出显然是不太可能的，所以这里我们给出两个队列p1和p2
那么我们创建两个队列的意义是什么呢，就不卖关子了，这里的一个队列会用来存数据，而另一个空队列则会用来在删除数据的时候，充当传数据的作用，那这是为什么呢，这里给出一个例子：
假如我们已经在p1中存了{1， 2， 3， 4}四个数据，我们想删除数据，就要删掉4这个数据，但是我们只能从头开始删数据，那该怎么办呢？
这里我们可以先将1,2,3这三个数据传到p2中存好，再将p1中的数据删除，这样便实现了栈的删除了！
了解了最重要的步骤后，我们现在就来依次实现其他的函数吧
- 结构体的创建
因为我们要使用两个队列，所以我们的结构体包含两个结构体就可以了
具体实现如下：
- 初始化
先创建一个指针，又因为包含两个队列，所以直接调用队列的初始化，然后将这个指针直接返回就可以了
ps：记得传地址哦（->的优先级是高于&的，所以不打括号也没有关系）
具体实现如下：
- 插入数据
因为我们有一个队列是空的，一个队列是存有数据的（假设），队列和栈的插入都是插入队尾，所以可以看作相同，所以我们只要找出那个不是空的队列，然后将数据插在队尾就可以了，为了实现这一点，我们利用了队列的size元素进行判断
具体实现如下：
- 删除数据
这是利用队列实现栈最大的难点，但是具体思路已经在前面详细说过了，这里不再过多赘述，与插入数据相同，我们利用一样的方式先找到空的队列（p2），然后调用另一个队列（p1）依次往空的队列（p2）里插入数据，要注意的是每插入一个数据，我们也要删除‘ ’p1 ‘’的一个数据，直到‘ p1 ’中只有一个数据的时候就停下来，然后返回这个数据，但在返回前记得将‘ p1 ’队列清空
具体实现如下：
- 返回栈顶元素
要先找到存数据的那个队列，然后根对之前知识点的了解，栈顶其实就是队列的队尾，直接调用返回队尾元素的函数就可以实现了
具体实现如下：
- 判断栈是否为空
因为只有一个队列中是存有元素的，所以我们只用判断这个队列是否为空就可以了，那么我们还要去专门去寻找这个队列吗，答案当然是否定的，我们直接判断两个队列是否都为空，如果都为空就返回true，反之就会返回false
具体实现如下：
- 销毁栈
其实就是将两个队列销毁就可以了，直接调用两次销毁队列的函数就可以实现了
具体实现如下：
- 总结
最主要的就是要弄懂两个队列之间的转换，只要弄清楚了这个其他的就是小菜一碟了！
还有就是记得要传地址！！！
2.用栈实现队列
题目链接：232. 用栈实现队列 – 力扣（LeetCode）
具体思路：
刚刚我们成功的用队列实现了栈，现在我们来解决用栈实现队列的问题
与上一题的实现思路也很相近，首先我们也要先创建两个栈，但是不同的是，我们这里要专门拿一个栈只用来存储数据，一个只用来插入数据，那是因为栈是后进先出，所以传到另一个栈的时候顺序会变，那我们决定好两个队列的作用后又该做什么呢？因为这里的实现更复杂，接下来将一步一步的给大家分析
- 初始化
与上一题一样，就是初始化两个栈，直接调用栈初始化的函数就可以了，记得一定要传地址！
具体实现如下
- 插入数据
因为我们这里分了两个栈，一个栈是专门用来插入数据的，我们将数据插入那个栈里就可以了
具体实现如下：
- 删除数据
这一步是最难的，但是也不要有畏难心理，只要理解了还是很好写出来的
先说结论，如果专门删除数据的栈里有数据，就在那个栈内进行删除就可以了，如果没有就将存数据的栈里的数据传给删除数据的栈，第二种情况的实现是与上一题类似的，所以我们着重解释一下第一种情况
我们先看一段视频，当我们将要删除的数据传到另一个栈时，这时数据的顺序就反过来了，这时的栈顶就是队列的队头，所以直接出栈顶就可以实现出队头了
同样的，只要pop栈里还有数据，我们就可以通过只删除pop栈顶的方式就能实现删除队列的头节点，当pop栈内没有数据时，再将新增的数据放进去就可以了
具体实现如下：
- 寻找队头元素
这里的实现其实可以完全照搬插入数据的代码，因为pop栈的栈顶就是队头，如果pop栈内不存在数据，只要将push栈内的数据存进去就好了，只是这里的实现不用删除队头罢了
具体实现如下：
- 判断是否为空队列
与上一题一样的，直接将两个栈一起判断就可以了
具体实现如下：
- 销毁队列
直接销毁两个栈就可以啦
具体实现如下：
- 总结
虽然同样是创建两个栈，但是我认为这一题比上一道题更有难度，两个栈对应的功能和两个栈之间的关系如果没有完全弄懂就是做不出来的，建议大家可以多画图来理解，加油！
3.设计循环队列
题目链接：622. 设计循环队列 – 力扣（LeetCode）
具体思路：
首先，因为是循环队列，所以这个队列的大小肯定是固定的，然后我们就要开始思考实现中可能会遇上的问题，例如假如有k个元素，开辟多少空间合适，关于空和满的判断又该如何判断，插入数据该从哪里插入，带来的改动是怎么样，等等
由于都比较繁琐，接下来将在不同的函数实现中解决这些问题
- 结构体的创建
首先结构体内要有一个数组用来存数据，这里用指针来表示，因为还要手动开辟空间大小，然后需要一个头节点，一个尾节点，还需要一个数据来表示循环队列的大小，最后我们可以用一个数据来表示循环队列的有效元素，这样有利于我们判断队列的空和满，但是这里我不会使用，具体原因看到后面就知道了
具体实现如下：
- 循环队列的初始化
首先我们需要判断到底需要开辟多少空间，但是这里肯定有人就要问了：k个元素开辟k个空间就好了啊，有什么好考虑的？
要注意，我的结构体中是没有包含能代表有效元素的数据的，那么考虑到后面队列为空或者队列为满的判断，如果开辟的空间为k的话，那么当队列满了或者为空时，条件都是head == tail，是无法准确判断的，所以这里我们开辟k+1个空间，多开辟一个空间，用来存尾节点，这样的话，当队列为空时，判断条件就是head == tail ，而队列为满时，判断条件是tail的后一位是head就可以了 ，至于这里为什么不说是tail + 1 == head，到后面你就会知道了
至于其它的，就与普通的队列初始化一样了，只是多了一个给循环队列的空间数据赋值罢了
具体实现如下
- 判断队列是否为空
在前面我们有提到，当head == tail时队列就为空，这里直接写上去就可以了
具体实现如下：
- 判断队列是否满了
在前面我们有提到，当tail的下一位与head对应的下标相同时队列就满了，那我们为什么不直接对tail+1然后与head相比呢？这是因为如果tail已经到了最后一位时，如果加一就会越界，但是这肯定是不对的，我们要设法让tail回到0，这里可以采用判断语句，但是我采取的是计算余数的方法
(tail + 1) % (k + 1)
这样的话，当tail越界时就会除余为0，而当没有越界时也不会影响正常的判断
具体实现如下：
- 插入数据
与队列的插入数据实现基本相同，在tail所对应的下标元素插入数据，然后tail++就可以了，但是要注意的是，如果tail在末尾处的话，tail再加一就会越界，所以这里我们采用除余的方法来解决问题：
tail = (tail + 1) % (k + 1)
当tail == k + 1时， tail会因为除余而等于0，这样就不会越界了，当tail < k + 1时也不会有任何影响
当然，在插入数据前，我们也要判断数据是否为满，满了就不能插入数据了，直接使用判断是否为满的函数就可以了，但是为了让大家更深的理解，这里就没有直接代入了
具体实现如下：
- 删除数据
与队列的删除数据也是很相似的，直接将head往前进一步就可以了，具体的放越界操作是与插入数据的tail的做法相同的
当然这里也要判断是否为空，为空的话就不能删除数据了
具体实现如下：
- 返回头节点的数据
直接返回head对应下标的数据就可以了，在之前记得先判断队列是否为空
具体实现如下：
- 返回尾节点的数据
尾节点对应的节点是tail的前一个节点，这里也涉及到了越界的问题，当tail对应的下标为0时，直接-1的话也会造成越界，所以我们这里也采用了除余的方法，首先是tail-1算出减一对应的结果，然后加上总空间大小k + 1，最后再除余总空间大小就可以了
当然也要判断队列是否为空
具体实现如下：
- 销毁循环队列
与队列的销毁是相同的，先释放数组节点，然后将其他所有的值赋值为0
具体实现如下：
- 总结
最关键的就是要创建k+1个节点，还有利用除余的特性来对tail和head两个节点进行位置的判断，只要能想清楚这两点，这道题还是比较轻松的
4.有效的括号
具体思路：
首先我们要明确用什么样的方式来比较，目前根据我们的知识可能会想到快慢指针，遍历对比，等等，但是只要仔细一想，这些都是无法实现的，这道题我们将利用栈后进先出的特点来完成这道题目
首先，我们要先创造一个栈用来存关于左括号的值，然后遍历这个字符串，只要是左括号我们就将左括号存进去，如果不是左括号我们就从栈里面出栈拿出一个左括号与当前的右括号相比较，如果能匹配上就继续遍历字符串，如果匹配失败就返回false，如果字符串已经遍历完成了，直接判断栈是否为空，为空就说明全部匹配上了，不为空就说明匹配失败了，这就是大体思路
接下来让我们来完善细节：
首先是如果第一个元素就是右括号该怎么办呢，此时栈内还没有存数据，所以是拿不出数据的，因此在每次比较前我们也要判断栈是否为空，如果为空就返回false
在对比时，我们要先用一个新的变量来存当前栈顶的数据，当匹配成功后我们再出栈，不要提前出栈了
对于匹配的条件判断式，这里也十分的巧妙：
char x = StackTop(&ps);
if (
(x == ‘(‘ && *s == ‘)’) ||
(x == ‘{‘ && *s == ‘}’) ||
(x == ‘[‘ && *s == ‘]’))
{
StackPop(&ps);
}
如果字符串遍历成功，直接返回栈判空的函数就可以了
具体实现如下：
- 总结
还是很考验思维的，主要是在利用栈后进先出的特点，如果没有人告诉要用栈的方式实现的话，我觉得还是很难想出来的，至少我没有想出来，然后我认为最妙的地方就是左括号与右括号匹配的条件判断式，当时差点就用siwch来再赋值一个新的变量比较了，但是应该也可以实现，只不过代码会更为繁琐
最后的总结
虽然只有四道题，但是要完全理解其中的原理我认为还是要花上一段时间的，就像这边文章不知不觉间也写了四千多字了，写了两天才写完，重做题目的过程中也收获了许多，希望我的文章能对大家的解题带来帮助，只能说任重而道远吧，加油加油！
评论（1）