栈和队列高频面试题精讲_七月算法出品解析.ppt

栈和队列面试题精讲 七月算法 曹鹏 2015年4月23日 */21 提纲 线性表简介 面试题总体分析 一些例题 例1 元素出入栈顺序合法性判断 例2 用两个队列实现一个堆栈 例3 用两个堆栈实现一个队列 例4 支持查询最小值的堆栈 例5 单调堆栈——最大直方图 例6 单调队列——滑动窗口最大值 总结 线性表简介 堆栈和队列统称线性表 简单的线性结构 数组和链表可以实现这两种数据结构 堆栈 后进先出 (Last In First Out) 队列 先进先出 (First In First Out) */21 面试题总体分析 堆栈 基本理解 DFS 深度优先——按深度遍历 递归转非递归 队列 基本理解 BFS 广度优先——按层序遍历 */21 例1 元素出入栈顺序合法性判断 例1 给定一些元素的入栈顺序和出栈顺序，问是否可能？（假设所有元素都不相同） 分析： 模拟堆栈即可，如果当前要出栈的元素恰好在栈顶，则必须出栈，否则就入栈。（注意判断两个vector size一样) bool isPossible(vectorint in, vectorint out) { for (int i = 0, j = 0; j out.size(); ++j) { while (s.empty() || s.top() != out[j]) { if (i = in.size()) return false; s.push(in[i++]); } s.pop(); } return true; } */21 例2 用两个队列实现一个堆栈 例2 如何用两个队列实现一个堆栈？ 队列无论怎么折腾，元素顺序不会改变！ 两个队列来回倒，保证一个队列是空的，用空队列临时存储除队尾外所有元素 例如 q1非空，q2是空的，要出“栈”，实际上要出的是q1里面最后一个元素，我们把q1里面元素一个一个放入q2里面（所有元素的顺序不会变化），直到剩下一个，再让它出队即可 */21 例2 续 入“栈”：维护一个队列是空的 : O(1) push(x) ： if (!q1.empty()) q1.push(x); else q2.push(x); 出“栈”：用一个队列临时存放元素 : O(n) pop() ： if (!q1.empty()) { while (q1.size() 1) { q2.push(q1.front()); q1.pop(); } q1.pop(); } else { //类似操作} */21 例3 用两个堆栈实现一个队列 例3 如何堆栈实现一个队列？ s1负责“入队”，s2负责“出队”（反向） 入队直接入到s1里 要出队如果s2非空，则先从s2出，否则把s1里面全部元素压入s2中 理解： s1负责存放入队元素 s2负责出队并反向 每个元素实际上反向了两次，出入一次s1,出入一次s2 */21 例3 续 push(x): O(1) s1.push(x) pop: 均摊O(1) 每个元素出入两个栈各1次 if (s2.empty()) { while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } } s2.pop(); */21 例4 支持查找最小元素的堆栈 一个堆栈除了支持push, pop以外还要支持一个操作getMin得到当前堆栈里所有元素的最小值 方法1（笨） 用两个堆栈，s1和s2，s1正常使用, s2一直是空的 getMin的时候，把s1的元素一个一个弹出到s2，每弹出一个，顺便求当前的最小值，然后再从s2把元素一个一个弹回到s1，也清空了s2: O(n) */21 例4 续1 方法2 用两个堆栈，s1维护原来的值，s2维护最小值 它们元素个数一样多 push(x): O(1) s1.push(x);