面试的时候，栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容： （1）栈的创建 （2）队列的创建 （3）两个栈实现一个队列 （4）两个队列实现一个栈 （5）设计含最小函数min()的栈，要求min、push、pop、的时间复杂度都是O(1) （6）判断栈的push和pop序列是否一致 1、栈的创建：我们接下来通过链表的形式来创建栈，方便扩充。 代码实现： 入栈操作时，14、15行代码是关键。 运行效果： 2、队列的创建：队列的创建有两种形式：基于数组结构实现（顺序队列）、基于链表结构实现（链式队列）。 我们接下来通过链表的形式来创建队列，这样的话，队列在扩充时会比较方便。队列在出队时，从头结点head开始。 代码实现： 入栈时，和在普通的链表中添加结点的操作是一样的；出队时，出的永远都是head结点。 运行效果： 3、两个栈实现一个队列：思路： 栈1用于存储元素，栈2用于弹出元素，负负得正。 说的通俗一点，现在把数据1、2、3分别入栈一，然后从栈一中出来（3、2、1），放到栈二中，那么，从栈二中出来的数据（1、2、3）就符合队列的规律了，即负负得正。 完整版代码实现： 注意第22行和第30行代码的顺序，以及注释，需要仔细理解其含义。 运行效果： 4、两个队列实现一个栈：思路： 将1、2、3依次入队列一， 然后最上面的3留在队列一，将下面的2、3入队列二，将3出队列一，此时队列一空了，然后把队列二中的所有数据入队列一；将最上面的2留在队列一，将下面的3入队列二。。。依次循环。 代码实现： 运行效果： 5、设计含最小函数min()的栈，要求min、push、pop、的时间复杂度都是O(1)。min方法的作用是：就能返回是栈中的最小值。【微信面试题】 普通思路： 一般情况下，我们可能会这么想：利用min变量，每次添加元素时，都和min元素作比较，这样的话，就能保证min存放的是最小值。但是这样的话，会存在一个问题：如果最小的元素出栈了，那怎么知道剩下的元素中哪个是最小的元素呢？ 改进思路： 这里需要加一个辅助栈，用空间换取时间。辅助栈中，栈顶永远保存着当前栈中最小的数值。具体是这样的：原栈中，每次添加一个新元素时，就和辅助栈的栈顶元素相比较，如果新元素小，就把新元素的值放到辅助栈中，如果新元素大，就把辅助栈的栈顶元素再copy一遍放到辅助栈的栈顶；原栈中，出栈时， 完整代码实现： 6、判断栈的push和pop序列是否一致：通俗一点讲：已知一组数据1、2、3、4、5依次进栈，那么它的出栈方式有很多种，请判断一下给出的出栈方式是否是正确的？ 例如： 数据： 1、2、3、4、5 出栈1： 5、4、3、2、1（正确） 出栈2： 4、5、3、2、1（正确） 出栈3： 4、3、5、1、2（错误） 完整版代码： 代码比较简洁，但也比较难理解，要仔细体会。 运行效果：
1.程序员专场相亲活动： 声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系 [邮箱地址] 删除 |
注册
登录
