牛客网《BAT面试算法精品课》笔记三：队列和栈

牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 队列和栈的基本性质 1.栈是先进后出的 2.队列是先进先出的 3.栈和队列在实现结构上可以有数组和链表两种形式 01.数组结构实现比较容易 02.用链表结构比较复杂，因为牵扯很多指针操作 栈结构基本操作 1.pop操作，栈顶弹出1个元素 2.top或peek操作，访问栈顶元素但不弹出 3.push操作，栈顶压入一个元素 4.size操作，返回栈中元素个数 队列的基本操作： 与栈操作不同的是，push操作为在队头加入元素，而pop操作是从队列尾部弹出一个元素。栈和队列的基本操作，都是时间复杂度为O(1)的操作。 双端队列结构在首尾都可以压入和弹出元素； 优先级队列会根据元素的优先级值，决定元素的弹出顺序。 优先级队列的结构为堆结构，并不是线性结构。 深度优先遍历(DFS)可以用栈来实现： 1进去，2进去，4进去,4是最深的节点要出去，4出去，5进去，5出去，(4，5都已经访问过)所以2出去，3进去，6进去，6出去，7进去，7出去，3出去，1出去。 [

](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042103-300x244.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042103.png) **宽度优先遍历可以用队列实现：** 1进去，1出去，把1的两个子节点2和3依次进去，2出去，把2的两个子节点4和5依次放进去，3出去，把3的两个子节点6和7依次放进去，然后4 5 6 7 依次出去。 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042104.png) **注意点：** ** 平时使用的递归函数实际上用到了提供的函数系统栈，递归的过程可以看做递归函数依次进入函数栈的处理过程。所以用递归函数实现的功能一定可以用非递归的方式实现。** 常见题型： **案例1.** 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作getmin. 要求： 01.pop，push，getMin操作时间复杂度都是O(1) 02.设计的栈类型可以使用现成的栈结构 方法一： 序列：1 2 1 5 4 3 依次进栈StackData，StackMin进栈规则是小于等于栈顶元素才能进去 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042105.png) 方法二; 将方法一中不压入那一步变为压入栈顶元素而已 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042106.png) 01.方法一和方法二都是利用第二个栈StackMin来保存每一步的最小值。 02.方法一和方法二所实现的所有操作，时间按复杂度都为O(1) 03.区别在于方法一稍省空间，略费时间；方法二稍费空间，略省时间 **案例2.** 编写一个类，只能用两个栈结构实现队列，支持队列的基本操作(add,poll,peek) 方法：两个栈，一个压入栈StackPush，一个弹出栈StackPop，将StackPush中的数据导入到StackPop中，顺序就变过来了。 例如序列：5 4 3 2 1 入栈StackPush： [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042107.png) 倒过来：入栈StackPop [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042108.png) 然后弹出，顺序就像队列一样了：5 4 3 2 1 两个重要的注意点： 01.如果StackPush要往StackPop中倒入数据，那么必须把StackPush中的所有数据一次性倒完 02.如果StackPop中有数据，则不能发生倒数据的行为。 **案例3.** 实现一个栈的逆序，但是只能用递归函数和这个栈本身的操作来实现，而不能自己申请另外的数据结构。 第一步：实现get方法 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042109.png) 第二步：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042110.png) 第三步： 第二步后会发现栈空了，直接返回3，而不把3放回栈中 第三层返回了3，3跑到第二层，2入栈，3跑到第一层，1入栈，最后结果为3 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042111.png) get方法为，把栈底元素删除并返回的功能。 以下下代码为，把栈中元素逆序的主方法 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042112.png) 结果： [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042113.png) **案例4.** 一个栈中元素类型为整数，现在想将该栈从顶到底从大到小排序，只许申请一个栈，除此之外可以申请新的变量，但不能申请额外的数据结构。如何完成排序。 例子：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042114.png) 将想要排序的栈记作stack，辅助栈记作help，在stack执行pop操作，弹出的元素记为cur。如果cur小于或等于help当前的栈顶元素，则将cur直接压入help中； 如果cur大于help的栈顶元素，则将help元素逐渐弹出，并且重新押回stack中，直到cur小于等于help的栈顶元素，然后将cur押入到help中。 一直执行上面的操作，直到stack全部元素都到了help，最后将help中的元素再押回stack中就完成排序了。 **案例5.** 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。以数组为[4,3,5,4,3,3,6,7]，w=3为例。因为第一个窗口[4,3,5]的最大值为5，，第二个窗口[3,5,4]的最大值为5，第三个窗口的最大值[5,4,3]的最大值为5，第四个窗口[4,3,3]的最大值为4，我五个窗口[3,3,6]的最大值为6，第六个窗口[3,6,7]的最大值为7.所以最终返回[5,5,5,4,6,7]。 普通解法的时间复杂度O(N*W)，也就是每次对每一个窗口遍历其中的w个数。 本体最优解可以做到时间复杂度O(N) [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042115.png) 如果qmax队头的下标等于i-w，弹出qmax当前队头下标。Res[1]:[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042116.png) 最终结果：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042117.png) 上面过程中，每个下标值最多进qmax一次，出qmax一次 **案例6.** 给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数。要求数组长度为N，则时间复杂度为O(N)，额外空间复杂度为O(N)。MaxTree的概念如下： 01.MaxTree是一颗二叉树，数组的每一个值对应一个二叉树结点 02.包括MaxTree树在内且在其中的每一颗子树上，值最大的节点都是树的头。 [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042118.png) 每个树的父节点是他左边第一个比它大的数和他右边比他第一个大的数中较小的一个，如果这个数是最大的数，那就是整棵树的头结点 该方法的正确性： 01.该方法可以生成一棵树，而不是森林 02.生成的这一棵树是二叉树，而不是多叉树，任何一个数在单独一侧，孩子的数量都不超过一个 [

3进去，1进去，得到1往左第一个比他大的数为3，然后1出去，2进去，得到2往左第一个比他大的数为3