【数据结构】栈和队列OJ面试题

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

思路：由于C语言没有栈的接口，所以我们需要自己造一个“模子”。我们直接copy之前的实现的栈的接口就可以了（可以看我之前的博客【数据结构】栈和队列-CSDN博客copy接口），同时要注意要将typedef的STDataType从int类型改成char类型。在此之后，依次取出字符串中的字符判断，如果是左括号，则入栈。如果是右括号，则依次和栈顶字符去进行配对，然后出栈。再进行判断，配对则返回false，否则判断下一个字符。再while循环结束后还要再一次判空，排除栈中还有字符未进行判断的情况。

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

思路：由于C语言没有队列的接口，所以同样也需要我们自己造出一个“模子”来。再【数据结构】栈和队列-CSDN博客这篇博客中同样也有关于队列的接口，再这里我们直接copy一下队列的接口。

关于用队列实现栈，我们的思路是这样的，首先，创建出两个队列，一个队列用来在出栈时拷贝，一个队列用来在出栈时接受拷贝，所以这就要求一个队列必须是空的，而另一个队列的功能就是扮演栈的角色（因为队列出入数据是先进先出的，栈出入数据是先进后出的，所以在数据出栈的时候，只能用队列的拷贝来实现栈的数据出栈）。其他接口直接使用队列的接口就基本可以完成。

另外，要注意的是，在最后销毁栈的时候，需要先销毁两个队列再销毁栈，以免出现有野指针的情况。

 

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

思路：这道题同样需要用之前写的栈造一个“模子”。在解决这道题目时，需要我们创建两个栈去实现（st1用来存放数据，st2用来导数据）。当我们pop数据的时候，需要先将创建好的st1中的数据依次出栈到st2的栈中，然后将st2中的栈顶数据pop掉 ，最后将st2中的数据重新导回到st1中。在实现myQueuePeek（myQueuePeek接口要求我们返回队列开头的元素）接口的时候也是同样的方法，先将st1中的数据导到st2中，只不过接下来不需要pop栈顶元素，只需要记录下栈顶元素，然后再导回st1中，最后再返回记录下的元素就好了。其他的接口用之前实现栈的接口就可以基本解决了。

 

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

思路：在这道题目中，我们采用顺序表的方法来完成。首先需要动态申请一个数组，然后初始化结构体。结构体中的head指向数组中的第一个节点，tail指向数组中最后一个节点的下一个节点，k的意思是数组中一共有k个数据。这里有接口需要我们判空和判满，但是如果就按这种思路写下去的话，我们会发现判空和判满的条件是一样的，都是head==tail。

那么我们应该如何去解决这个问题呢？这里我们有两种解决方案。第一种是在多开一个数组的空间，这样当队列满的时候的判空条件就变成了tail+1==head了，就避免了判空和判满条件一样的情况了。第二种方法是加一个size去判断队列中数据的个数。在此我们采用第一种方法来完成代码。

还需要注意的一个接口是取队尾的接口，这个接口需要取tail前一个结点，但是有一种特殊的情况就是tail是数组中第一个空间，这时候tail在-1的话就会变成-1，而不是指向第5块空间。这是我们可以进行一个判断，如果tail是第一块空间，那么则返回地5块空间的数据，否则返回第tail-1块的空间就可以了。或者我们可以取第((tail-1)+(k+1))%(k+1)个数据就是队列的队尾数据。