一.有效的括号：

20. 有效的括号 - 力扣（LeetCode）

首先拿到这个题目，我的第一个思路是利用双指针来走，看看是不是匹配的

但是这种情况就把双指针的这个思路直接pass了，明明是匹配的括号，用双指针一走就不是匹配的。所以这个思路直接pass。

还有一个思路就是用栈来解决问题，如果是左括号就入栈，如果是右括号就与出栈顶的左括号看看是不是匹配的。

是左括号就入栈

是右括号就让栈顶的左括号出栈顶，看看两个是否匹配，就这样一个个匹配，如果都匹配上了，就是有效括号

、

这就是一个整体的思路，这就利用了栈的后进先出，这就可以找到离右括号最近的左括号进行匹配。所以是左括号入栈，右括号和栈顶的左括号去匹配如果匹配上了，就继续。

思路就是这么个思路，现在来实现代码：

首先把我们写过的栈的实现copy过来

再创建一个栈来存放左括号，创建完再初始化一下：

接下来再判断是否为左括号，是就入栈，是右括号就去栈顶的数据与其看看是否匹配：

在else语句里就是考虑是右括号的情况，但是如果我们写的代码是左括号与右括号匹配的话，只匹配一次并没有什么效果，要全部遍历完匹配才是真正的匹配，所以我们这里是写左括号与右括号不匹配的情况：

这里入栈是特别多的情况有可能边入边出，也有可能，先入几个，再出几个，情况复杂，所以用栈来实现这些复杂的情况，这样就可以找到最近的左括号是否与右括号相匹配。

接下来我们运行一下：

发现这个用例没有通过，发现在栈里面还有左括号没有出来，还有一种情况：

如果是这种情况，前面的括号都匹配成功，但是发现栈顶里面还有数据，但按照上面的代码此时任然会返回true，所以这次是数量没有对上，我们在这里还要加一个栈的判空，如果栈里面还有数据那么肯定是false。

此时加了这种情况我们再来运行代码：

此时我们发现如果只有一个右括号的话，我们去取栈顶数据，此时栈顶为空，这里取的话就是对空指针的解引用就会报错。

现在加上这种情况，再来测试：

完美通过了。

整个代码如图：

二.用队列实现栈：

225. 用队列实现栈 - 力扣（LeetCode）

栈是后进先出，而队列是先进先出

比如说这两个队列，一个队列里存着1 1 2，现在要实现栈就是取出栈顶数据2，怎么操作呢，先把1 1拿去另一个空的队列，然后再把2拿出来。

现在3要入栈那么就是入不为空的队列

再想去栈顶数据还是先将 1 1出队列再把3取出来。

现在来实现代码：

首先还是把我们实现队列的功能拷贝过来。

然后栈的创建就是开辟一个给栈的内存空间，然后调用写好的队列初始化函数，这样栈的创建就写好了。

现在来实现入栈：

上面也介绍过了，这里入数据是入队列是入不为空的队列，所以这里要利用判空函数，看看数据存在哪里：

谁不为空就存在哪里。

现在来实现移除栈顶元素并返回函数：

这里还是跟上面一样，有数据的队列就先移动size-1的数到另一个空的队列 然后就返回剩下的那个值即可。

这里还是用到假设法，假设一个队列为空进行操作，不为空就换一下就行，这样省下了很多代码。

这就是假设法的完成。

现在来完成具体操作，就是将不为空的队列的前size-1的数据取出，导给为空的队列，一开始不为空的队列现在就剩下一个数据，那个数据就是栈顶元素。

这就是整个的实现过程。

现在来实现返回栈顶元素的函数：

实现队列的时候，我们完成了取出队尾的数据的函数，在这里只要判断一下哪个队列不为空，就利用这个函数去取出栈顶元素即可：

现在来实现对栈的判空：

这个就是对两个队列进行判空，如果两个队列都为空，则这个栈必定是空的，如果有一个不是，则栈就不为空。

现在来实现对栈的销毁：

这里就是利用封装好的对队列销毁的函数，销毁两个队列，并且释放掉开辟的空间即可。

前面队列的实现是之前写好的，而此题中我们写的部分的代码如图：

整个代码如图：

三.设计循环队列：

622. 设计循环队列 - 力扣（LeetCode）

这里用数组去实现这个循环队列。

先在要实现循环队列的结构体里,先定义一个整型指针变量来存放开辟的空间再定义head和tail的变量，这样方便后面找尾和找头时直接利用。还有题目要求的队列长度变量k。

还有一个值得注意的是tail指的是队尾数据的下一个，如果tail指向队尾，那么空的时候指向的那个位置，一个数据指向的也是那个位置，所以这样就区分不开。所以这里tail指向的是队尾数据的下一个。

这里想删除数据，怎么删除呢？

就是head++，然后给那个数据给占掉。

这里再插入数据3：

这里tail指向的是队列结尾的下一个位置，因为是循环队列所以就绕回来了。

所以在这里就是有限的空间，保证先进先出，重复使用来实现循环队列。

但是我们还要考虑几个问题什么时候为空，什么时候为满？

第一种就是head==tail时为空。

那什么时候为满呢？

当tail和head从第二个空开始时，不断插入数据，最后发现还是tail==head时是满的，所以当head==tail时不知道是空还是满的情况，所以我们在这里要解决一下这个问题。

方法一：利用size来记录一下，当size==k时就是满，size==0即为空。

方法二：额外多开一个空间，就是开k+1的空间。

方法二比较装所以我们用方法二来解决，上图我们是能存放3个数据，我们利用方法二再额外多开一个空间，但这个空间不能用来存放数据，只能用来判断是空还是满来使用的。

如图：

我们在这里放入了三个数据，但是已经满了，这里我们再删除两个数据：

此时再插入两个数据看看：

此时就不能再插入了，再插入就溢出了，因为虽然是额外开的空间，但是存储的数据个数还是k个所以在这里用额外开辟空间的方法就有效避免了head==tail时有可能即为空也为满的情况，所以在这里tail+1==head即为满，tail==head即为空。

但其实并不是这么简单还有一种情况：

这种情况队列也满了，但是tail+1！=head所以这里我们用到了一个非常巧妙的运算（tail+1）%（k+1）==head即为满，比如说这里k==3，tail==3，所以一模就是0，这里head=0，所以为满，因为这里是数组，所以下标特殊。

再考虑上面那种情况，k==3，tail==1，所以（tail+1）%（k+1）==2，此时head=2，所以为满，这个模的运算非常巧妙的将所有情况全部包括进去了。

综上所有的分析，现在我们来实现代码：

首先就是循环队列的创造：

再来实现循环队列的判空，根据上面的分析，如果head==tail即为空：

再来实现循环队列的判满，也就像上面分析的那样利用模运算来判断：

再来实现向循环队列插入一个元素。如果成功插入则返回真：

模一下的意义就是防止这个情况的出现，此时再来一个数据当出现这样的情况模一下，解决了回绕的问题。比如4%4=0这样tail就又回到了头的位置。

再来实现从循环队列中删除一个元素。如果成功删除则返回真：

这个模的情况也是解决回绕的问题。

再来实现从队首获取元素。如果队列为空，返回 -1 ：

再来实现获取队尾元素。如果队列为空，返回 -1 ：

利用三目运算符，如果tail在数组的头，就返回数组的尾，如果不是，tail指的是队尾的下一个数据，所以返回tail-1处的数据即可。

整个代码如图：

四.用栈实现队列：

232. 用栈实现队列 - 力扣（LeetCode）

要实现之前，栈是后进先出，队列是先进先出。

假设数据是1 1 2，现在想要出队列，就是出1，但是栈是后进先出，栈只能出2：

所以我们先把数据导到另一个栈里面去，然后顺序就是变成2 1 1，让他出栈就行：

然后现在想要入数据，比如说入3，这里又要怎么做呢：

这里我们可以直接放入另一个栈：

现在又想出数据了，因为是队列原本的顺序是1 1 2所以出的还是1，这样直接出2 和 1那个栈的数据就行，不用导过来导过去的了.

综上，我们可以定义两个栈，一个栈用来是入栈的，另一个是用来出栈的。

现在来实现队列的创造：

先开辟一个结构体指针的空间，然后再利用封装好的栈的初始化函数来初始化就行。

现在来实现将元素 x 推到队列的末尾：

这个功能简单的来说就是入栈，我们前面的思路已经讲过有数据直接放入专门入栈的栈中即可。

现在来实现返回队列开头的元素：

先全都将入栈的数据导到出栈的栈中，然后返回栈顶元素即可：

如果出栈的栈是空的，就将入栈的栈的数据导过来，如果不为空直接返回出栈的栈的栈顶元素即可。

 现在来实现从队列的开头移除并返回元素：

有了上一个函数的基础，这个就非常简单了，调用上一个函数，再将出栈的栈的栈顶数据删除即可：

现在来实现队列的判空：

还是对两个栈进行判空，如果都为空则队列也为空

现在来实现队列的销毁：

也就是销毁两个栈，再释放掉开辟的空间：

实现栈的功能的代码如图：

整个代码如图：

总结：这就是几个关于栈和队列的OJ题整个分析过程。