栈和队列经典面试题详解

目录

题目一：20. 有效的括号 - 力扣（LeetCode）

题目二：225. 用队列实现栈 - 力扣（LeetCode）

题目三：232. 用栈实现队列 - 力扣（LeetCode）

题目四：622. 设计循环队列 - 力扣（LeetCode）

---

上一次我们详细讲解了栈和队列的实现，今天我们就来讲一下栈和队列的经典面试题目，以强化我们对栈和队列的理解。话不多说，我们来看题目。

题目一：20. 有效的括号 - 力扣（LeetCode）

这道题目就是一道经典的用栈来解决的问题，我们用c来实现的话就要先实现栈的各种函数，上篇文章我们已经讲过了，这里就不在赘述。

思路：用s指针遍历s，当*s为'('  或 ‘[’ 或  '{' 时进栈，当*s为‘)’或'['或'{'时出栈，然后进行匹配，匹配不成功直接返回false，匹配成功继续匹配，如栈为空且s正好遍历完数组，则返回true。

由于栈具有后进先出的特点，完美的契合了这道题目。代码如下：

这一部分代码是栈的实现，需要注意的一点是要把STDataType改成char，别的和我们之前讲过的一模一样，接下来是接口函数的实现：

大家看一下段代码正不正确，左括号入栈，有括号则出栈匹配，匹配不成功返回false，出while循环代表所有的左括号都匹配成功，返回true。

看似逻辑没有问题，那么我们运行一下代码：

这是什么情况？当s数组只有一个'['时解答错误，遇到错误不要慌张，我们来一步一步的读写代码，来找错误：

*s开始为'['进入while循环，入栈，s++, *s此时为'\0',出while循环，直接返回true。

哦！原来我们漏了一种情况：出了while循环栈不为空，虽然此时已经遍历完了数组，但是栈不为空说明有括号落单没有匹配，所以我们应该在while循环外加上判空的判断，代码如下：

这下代码就正确了。

题目二：225. 用队列实现栈 - 力扣（LeetCode）

这道题目让我们用两个队列来实现一个栈。

栈是后进先出，队列是先进先出，那么怎么用两个队列实现栈呢？

思路：两个队列，q1，q2，保持一个队列不为空（进数据），另一个队列为空（出队列）；进行出栈操作时则把不为空的队列的数据剪切到为空的队列中直至剩余最后一个元素停止，然后把删除初始时不为空的队列的最后一个元素，从而完成出栈的模拟。

代码如下：

这段代码在模拟栈的删除时，我们采用了假设法，希望大家能够好好理解理解，这个方法可以一定程度上的优化代码，什么？if...... if?通俗易懂的代码！！！

这段代码我们采用了结构体套结构体的方法，俗称“套娃”：

用obj结构体指针指向MyStack结构体，而MyStack结构体又由结构体Queue q1和Queue q2组成，不要被搞晕了，示意图如下：

还有就是myStackFree函数，要清楚的知道动态开辟的内存都有哪些，可不敢free非动态开辟的内存，也可不敢直接free(obj),这样动态开辟的链表找不到了，不就造成内存泄漏了吗？正确的做法是先调用QueueDestroy释放掉两个链表，然后在释放obj。

怎么说呢，这道题目没有什么实践意义，但是有一定的教学意义，能让我们更好的理解栈和队列。

题目三：232. 用栈实现队列 - 力扣（LeetCode）

这道题目与题目二大同小异，我们创建两个栈：stpush和stpop，stpush负责进入数据，stpop负责出数据。

入数据，就是stpush的入栈操作。又小伙伴会说，不对啊：你这样数据不就进入一个栈了吗？不成了后进先出了吗？

别急，当出数据时，我们和题目二一样进行导数据：把stpush的数据“剪切”到stpop中，这时原来元素的顺序就反过来了，我们在把stpop的栈顶数据删除，就模拟实现了队的出队操作。

思路示意图如下：

入队：

出队：

需要注意的一点是，在进行出队导数据时，我们要先看一下stpop栈中是否有数据，如果有的话就直接删除stpop栈顶数据即可，不可在把stpush中的数据导入进去，否则就会引起顺序错误：

知道了思路后，我们来写代码：

要说的一点是我们在实现出队函数时调用了Peek函数，简化了代码，销毁时还是要注意那块是动态开辟的内存，哪块不是，一定要仔细。

这道题目也是没有实践意义，但是有一定的教学意义。

题目四：622. 设计循环队列 - 力扣（LeetCode）

这是一道非常经典的题目，创建循环队列可以用数组和链表，笔者这次用数组来实现。

我们创建了一个循环队列的结构体，结构体成员变量如上图所示，head和tail可以让我们通过数组下标来访问循环队列收尾元素。

怎么通过数组实现呢？假设队列固定最多有5个元素，当head超过5时让它模5重新指向头即可。

这样就做到首尾相连了。

那么当循环队列为满和为空判定条件是什么？

坏事儿了！我们上面的思路队列为满和队列为空时都是head==tail。这该怎么办呢？我们可以额外多开辟一个空间。即队列最大容量为5时我们开辟6个元素的空间。

这样的话我们再来看看队列为满和队列为空时tail和head的关系：

为空：

仍然是head==tail；

为满：

情况二是情况一经过：出队，出队，入队，入队 操作形成的。

这两种情况统一都是：(tail+1)%(k+1)==head。

知道了思路，代码写起来就比较简单了：

入队：入队时要先判断队列满不满，不满则插入数据，插入数据直接往a[tail]位置插入，更新tail的位置：tail=(tail+1)%(k+1).模上k+1的原因是tail有可能表示数组的最后一个位置，加一会变为初始位置。

出队：出队操作，最后要更新head的位置，同样，head可能最开始就表示最后一个位置，也要模上k+1。

总之，就是要注意head和tail的值在0到k这个范围变化。

以上就是全部内容，希望大家能有所收获。