堆栈
队列
3.1 怎样用一个数组实现三个堆栈
3.1解答：
解法一：
将数组划分成3等份，每一份独立的用来实现堆栈。
*第一个堆栈：从 0
*第二个堆栈：从 n/3
*第三个堆栈：从2n/3 至 n
这种解法是基于对每个堆栈的使用没有额外的使用说明，所以我们直接为每个堆栈划分固定的大小。
解法二：
解法二中的，主要数组中还有空余的空间，堆栈就还能增长。
每次为堆栈分配一个空间的时候，在这个新空间中记录上一个空间地址。这样堆栈中的每个元素都有一个指针指向之前的元素。
这样的实现方法有一个问题就是如果一个堆栈弹出一个空间(释放空间)，这个空间并不会作为空闲空间现在数组后面。这样话我们就不能使用新产生的空闲空间。
为了解决这个问题，我们用一个列表来记录空闲的空间。当有新空闲空间出现，我们就把它加入到这个表中。如果需要新分配一个空间，就从这个表中删除一个元素。
这样的实现方法使得3个堆栈能够动态的使用数组的空间，但是这是以增大空间复杂度换来的。
（这个不是很明白，感觉释放的空间还是不能使用，而且 push操作会不会发生覆盖啊 ，求大牛解释！！！！）
3.2 适合实现一个堆栈，除了有函数push、pop函数之外还有min函数，min函数范围堆栈中的最小元素。要求push,pop和min三个函数的时间复杂度均为O(1)。
3.2解答：
在每个堆栈中的节点中记录目前堆栈中的最小值。那么调用min( )函数时只需要看看栈顶元素中记录的最小值即可。
但是这样解法存在的问题是，如果堆栈的需要记录的元素非常多，那么这样的方法将会消耗大量的空间。因为我们在每个堆栈的元素中都记录来了最小值。这个能不能改进呢？
我们可以在创建一个辅助的堆栈只用来记录最小的元素。
这样的方法就是不是有更高的效率呢，如果栈中元素有相同的局部最小值，第一种解法则存储了大量重复元素。而第二种算法，在用一个额外的堆栈s2中只记录最小值，如果栈中元素存在大量重复，s2不会重复记录，避免了大量的冗余数据的记录。
3.3 想象下啊：一堆盘子，如果堆得太高的话，就容易倒下来。所以在现实中如果盘子堆到一定高度，我们就会重新起一个堆。现在实现一个新的数据结构来模拟这样现象。SetOfStack当中包含很多的堆栈，当一个堆栈达到上限的时候，启用下一个堆栈。SetOfStack.push
和 SetOfStack.pop应该和普通堆栈的操作一样。
进阶：
实现一个函数popAt(int index)，指定在哪个堆栈上弹出元素。
3.3解答：
根据题意，我们的数据结构大体上应该是这么一个框架：
由于要和普通的堆栈的push()有相同的效果，也就是说每次push()都必须将元素放到最近使用的一个堆栈中。但是在这个堆栈已经满了情况下，那就必须建一个新的堆栈然后再入栈。那么push的实现如下:
那pop()如何实现呢？和push()差不多，也一定要在最近的一个堆栈上操作。但是如果最后一个堆栈是空的话，就应该将其移除。
那进阶的问题这么处理呢？
这个问题确实有点难度。实现起来也比较麻烦，因为整个系统看起来应该像一个“翻转”系统。如果我从堆栈1中弹出一个元素，那么我们需要将堆栈2底部的元素压到堆栈1的顶端。堆栈3的元素要到堆栈2....
注：你可能会不同意我的说法。认为实现这个函数不需要“翻转”整个堆栈。系统中的每个堆栈并不需要都是满栈的，这样的话也可以省下很多的时间复杂度，特别是在堆栈非常大的时候。但是如果假设除了最后一个堆栈之外，所有的堆栈必须满栈的话，这样的方法就不行了。具体采用什么样的结构，你可以在面试时和面试官好好沟通然后决定。
3.4 经典的汉诺塔问题，有3根柱子，柱子上串有N个尺寸不同的碟子。汉诺塔问题的起始状态为，所有的碟子都从小到大的穿在柱子上(下面的碟子最大)。在满足下面三个限制：(A) 每次只能移动一个碟子；(B) 只有每根柱子顶端的碟子才能移动；(C)任何碟子只能放在比它大的碟子上。写一段程序(要求使用堆栈)，将第一个根柱子上所有的碟子移动到移到最后一根柱子上。
3.4解答：
首先我们考虑解题的算法：将N个碟子从第一根柱子移到最后一根柱子。我们先从最简单的情况开始。如果只有一个碟子，那么直接将它移到最后的柱子。那两个碟子呢？
(1)先将第一个碟子从第一根柱子移到第二根
(2)将第二个碟子从第一根柱子上移动到第三根
(3)再将第二根柱子上的碟子移动到第三根上，完成！
那三个碟子呢?
(1)采用两个碟子移动的方法，讲上两个碟子移动到第二根柱子上
(2)将第三个碟子移动到第三根柱子
(3)在采用运来的方法将第二根柱子上的两个碟子移动到第三根柱子。
很明显采用递归算法就能解决本题：
3.5 用两个堆栈来实现一个队列
3.5解答：
堆栈和队列的最大区别在于：一个是先进后出，一个是后进先出。但是题目的要求使得peek和pop的动作恰好相反。那么我们就可以利用第二个堆栈完成入栈元素顺序的反转。(先所有的元素进堆栈S1，这样最先进栈的元素在栈底，最后的在栈顶；然后将S1中的元素依次弹出，并压入堆栈S2中。这样S2中先进的元素就在栈顶后进的就在栈底了。)
但是如果对队列和出队列的动作反复进行的话，我就要在S1和S2两个堆栈中反复的倒来倒去。其实有偷懒的方法。
当有元素要进入队列的时候，直接压如堆栈S1中，元素需要从队列中出列的话，检查S2中是否有元素，如果没有再采用之前的方法将S1中的元素“倒”入到S2中，如果S2中非空在直接弹出元素即为队列中出列的元素。这样的方法就免于在两个堆栈之间倒来倒去了：
3.6 写一个程序将堆栈升序排序。该堆栈就是一个普通的堆栈，不能有其他假设。函数实现是只能调用函数push(),pop(),peek()和isEmpty这几个函数。
3.6解答：
再建一个堆栈，从原堆栈中弹出一个元素到新的堆栈中。然后再比较原堆栈栈顶元素和新堆栈栈顶大小。如果符合排序规则，再次入新堆栈。如果不符合，在弹出新堆栈中的元素逐个比较直到满足排序关系。这样类似插入排序的方法，之间复杂度为O(n^2)。