队列和栈相关的笔试面试题，栈和队列自然是基础中的基础了，罗列了一些基本的，总之不要着急，在纸上理清楚之后再去实现，实现起来反而是非常快的，有一些地方是不常用到，比如通过栈来比较大小，进行排序等等操作。
基本性质
- 栈 先进后出 （弹夹） 支持 pop(弹出) push(压入) size
- 队列 先进先出 pop 从队尾弹出 push 从队头压入
- 双端队列 两端都可以进出队列
- 优先级队列 根据元素的优先集值 决定元素的弹出顺序 （优先级队列实质上是一种堆结构）
- DFS以及BFS DFS实质上就是通过栈来实现的 元素入栈的顺序 实质上就是深度优先遍历的顺序（DFS 与NLR LNR LRN 并不是一个东西）宽度优先遍历实质上是通过队列来实现的（注意开始的时候 根节点进队列 然后根节点出队列 之后以此把根节点的子元素进队列 具体更细节的可以参考二叉树相关章节的那个整理）
- 平时所使用的递归函数，实质上使用了系统提供的系统函数栈，递归函数的处理过程可以看做是一个函数进栈出栈的过程，任何递归函数可以实现的功能，都可以用非递归的方式实现。
- 在c++ 的题目中，常常用一个vector来模拟栈操作，注意看那个元素为栈顶，pop操作，相当于v.pop _back删除队尾的元素，push操作，相当于v.push _back，在队尾插入一个元素，top操作，相当于return v[len-1]，返回最后一个元素。
获取最小值的栈
特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作getmin，要求，pop，push，getMin操作的时间复杂度都是O(1)。设计的栈类可使用现成的结构。
- 思路，入栈的时候，用一个array，每次插入或者弹出一个元素的时候，进行排序。
- 采用两个栈 栈一 用于正常操作 用于元素正常入栈出栈 栈二 保存每一步的最小值 主要是栈二的压入以及弹出的规则 核心思想 用stackmin的栈保存每一步的最小值
- 方案一 压入的时候 如果当前元素比栈二的栈顶元素小 就压入栈 如果当前元素比栈二的栈顶元素大 则不压入栈 反之 则不入栈 注意，在弹出的时候 采用相反的操作 如果当前元素比栈顶（stack min 栈）元素大 则不弹出 反之 如果等于栈顶元素的话 则弹出栈二中的元素
- 方案二在压入的时候 如果当前元素比栈顶元素大 则压入原先的栈顶的元素 可以做到在弹出的时候 同步弹出 不容易出错 就是会稍费一点点空间
//注意使用线程的stack的STL进行操作 |
用两个栈实现队列 支持（add pull peak）基本题目了
- 队列特点 先进先出 栈特点 先进后出
- 首先是栈的功能分类 一个栈作为push栈 另一个栈作为pop栈 栈一作为压入栈，在push数据的时候，仅仅往栈一中push，另一个栈做为弹出栈，在弹出数据的时候，仅仅从另一个栈中拿数据，即为stackpop。
- 注意
1.stackpush往stackpop中倒入数据的时候，必须一次性地把stackpush中的数据倒完。如果stackpop不为空，则stackpush是绝对不能向stackpop中倒入数据的，（注意原子性 比如stackpop不为空 即元素还没有完全倒入stackpush中 则不能再往stackpush中插入数据）
2.每次从stackpop中弹出数据之后，还需要把stackpop中的数据再放回到stackpush中去，即是说，当stackpop中存在数据的时候，stack push 是绝对不能向其中倒入数据的。
- 在具体实现中，倒数据的操作没有具体的限定，只要满足不违反上述的三条规则即可。
注意一下开始的时候，在push之前，会做一下清空stackPop的操作，在pop的最后部分，则没有做将Pop中的内容放回到stackPush中的操作，如果这样的话，有的case就过不去，具体原因还没有找到…总之将所有的stack互换的操作方在一个函数中进行会比较好。
class TwoStack { |
用两个队列实现一个栈
与上一个题目相似，这种题目的关键，是要确定好push以及pop的时候，具体都应该如何操作，比如两个栈空的时候应该怎样，一个栈空的时候应该怎样等等。
实现栈的逆序操作 要一点技巧 特别能体现递归的技巧
实现一个栈的逆序操作，但是只能用递归函数和这个栈本身的操作来实现，而不能申请额外的数据结构。实际上考察了两个操作。编写一个函数，这个函数的功能是移除栈底元素并且返回。
- 考察递归函数的使用
- 递归函数一 通过返回值 将栈底元素的返回值 一层一层向上抛 函数的功能 得到栈底元素 并且返回 最后将栈底元素删除 所谓的删除 就是得到之后 不再往栈中重新push了 就是一个get函数 注意 这里 删除栈底元素的目的是为了每次把得到的栈底元素放在整个栈的最上面
- 递归函数二 实现整个栈元素的逆序的递归函数 把当前栈底元素删除并返回 继续递归 每次删除并且返回的栈底元素会被重新push到栈顶中 这样依次循环 完成整个逆序的操作 注意 在这个函数中 每递归一次就会删除一个当前栈底的元素
- 注意区别 第几层函数返回 以及最后一层返回时候的操作
下面这个图可以表示出递归操作的整个调用栈和操作流程的关系：
TODO (7niu)
//这个递归的用法太精妙了。。。
class StackReverse { |
利用一个额外的栈进行排序(小复杂)
栈中的元素类型为整形，想将该栈从顶到底按照从大到小的顺序排序，只许申请一个额外栈，除此之外可以申请新的变量，但不能申请额外的数据结构，如何完成排序操作?
- 需要申请一个辅助栈help，当前元素为current，如果current<=help栈顶元素，则入栈，如果current>help栈顶元素，将help中的元素弹回栈一，直到current<help栈的栈顶元素，整个过程完毕后，current是从小到大排列的，之后再将help中的元素一次放回到栈一种即可。
注意 要熟悉用vector或者数组 来模拟入栈和出栈的过程
用栈模拟的化，还是挺简单的，用数组模拟的话，一定要在开始的时候定义清楚，在开始的时候，栈顶指针存储在0号元素位置还是1号元素位置！！！要不然后面就搞晕了！！！
提示 在每次push 或者pop操作的最后 都把当前栈的元素打印一遍出来 这样在调试的时候 容易减少错误
#include <iostream> |
滑动窗口（难度较高）
给定一个数组以及一个滑动窗口，窗口每次向右移动一个元素，每次返回窗口中的最大的元素。比如数组[4,3,5,4,3,3,6,7]窗口的长度w=3，这样最后返回的结果就是[5,5,5,4,6,7]。
- 普通解法的时间复杂度为O(n*w)，即是每次遍历w窗口中的元素，并且从中选出最大值，将最大值依次弹出。
- (较难的一个方法)最好的时间复杂度为O(N)可以利用双端队列实现窗口中最大值的更新。双端队列qmax={},双端队列存放着数组中的下标值。
- 对数组进行遍历
- 队列为空 插入arr[i]
- 如果当前元素arr[i]<d.back()把下标i插入到队列队尾。
- 否则 一直从队尾弹出元素 直到arr[i]>=d.back()
- 当遍历的位置超过窗口的宽度，如果d中第一个元素index值大于i-w，则d中的第一个元素就是最大的元素，将这个元素放入结果数组中，否则就将队头元素弹出，直到符合上述要求，这里也是一层循环。
注意 做这个题的收获点
- 第一步 形成思路 可以用文字描述
- 第二部 在草稿纸上 把文字思路转换成代码表述 并且自己review（一定要习惯在纸上表述 事实证明 这个对思路的整理很有用的 可以减少一些弯路 因为你在电脑上直接实现 很容易陷入一个思路的混乱 全局观念不够 一次不能看到全部的代码 在纸上是帮助自己形成思路的过程 文字的表述和代码的表述有些gap 语言表述不可能很精确 转译的过程很见功力 比如这个题目用两个循环）
- 第三部 把代码用实现出来 debug
- 对于stack这类的题目 debug的时候 最好把每一个关键步骤之后的stack元素都输出来，这样对于一些细节，更容器发现问题。
class SlideWindow
{
deque<int> d;
public:
vector<int> slide(vector<int> arr, int n, int w)
{
int i=0;
int current;
int cIndex;
int fIndex;
vector<int> answer;
for(i=0; i<n; i++)
{
while(1)
{
if(d.empty())
{
d.push_back(i);
break;
}
cIndex=d.back();
current=arr[cIndex];
if(arr[i]<current)
{
d.push_back(i);
break;
}
else
{
d.pop_back();
}
}
if ((i+1)>=w)
{
while(1)
{
fIndex=d.front();
if((i-w)<fIndex)
{
answer.push_back(arr[fIndex]);
break;
}
d.pop_front();
}
}
}
return answer;
}
};MaxTree （比较发散的题目 本质上还是stack用于比较大小的应用）
给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组的长度为N，则时间复杂度为O(N)，额外空间复杂度为O(N)。MaxTree的概念如下：
1 MaxTree是一颗二叉树，数组的每一个值对应一个二叉树的节点。
2 包括MaxTree树在内且在其中的每一颗子树上，值最大的节点都是树的头。
概念上来看，这里的maxtree有点类似于大根堆。题干上给出了具体的解法，单独上是降低了一些：
对于一个没有重复元素的整数数组，请用其中元素构造一棵MaxTree，MaxTree定义为一棵二叉树，其中的节点与数组元素一一对应，同时对于MaxTree的每棵子树，它的根的元素值为子树的最大值。现有一建树方法，对于数组中的每个元素，其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。若两边都不存在比它大的数，那么它就是树根。请设计O(n)的算法实现这个方法，返回的数的结构是数组的形式，简化了一些难度。
这里记录一下证明过程，论述下为什么这种方法是有效的，需要证明两点
- 证明a: 按照该方法可以生成一个数而不是一个森林
- 证明b: 生成的树是一颗二叉树而并非是多叉树
证明a：数组中所有的元素都不相同，按照上面的方法，每个元素会找到一个比它大的数作为父节点，这样一定会有一个最大的父节点做为整个树的最顶端的元素。
证明b：采用反证的思路，要证明b实际上是证明，任何一个数在单独一侧的孩子的数量不超过1个假设数组的序列为 …A…a1..a2 并且A为父节点，a1与a2都是A的孩子，按照之前的规则，必然有A>a1 A>a2
如果a1<a2<A 则按照上面的规则，a1的父节点绝对不可能是A，最起码是a2
如果a2<a1<A 同理，a2的父节点也不能是A，最起码是a1
所以可以说明假设错误，假设中的这种情况是不存在的。
下面是具体的思路：
风格上与利用额外栈进行排序那个题目比较类似，都是结合栈的弹出，同时加上一些比较。
注意在最后比较两组index数组然后输出的时候，弄清楚比的是实际的值，还是index，这个地方稍微有点绕。
两次采用入栈比较的形式，得出两个index数组，之后遍历数组，找到较小元素的那个index。由于有时需要多次从数组中弹出元素，因此提前建立了一个map用于进行倒排索引，方便定位index。
#include <iostream> |
