如何用一个数组实现三个栈
Explain how you would implement three stacks in a single array, such that neither stack overflows unless the total array is full.
[解决办法]
采用交叉索引的方法，
一号栈所占数组索引为0, 3, 6, 9, 12......(K*3 + 0)
二号栈所占数组索引为1，4，7，10，13 ......(K*3 + 1)
三号栈所占数组索引为2, 5, 8, 11, 14......(K*3 + 2)
在栈中定义一个变量k保存当前栈的元素数目,对各号栈进行入栈与出栈操作时，利用不同的递推公式计算出在数组中的实际索引值.
[解决办法]
楼上的方法貌似不好吧？如果是那样不可保证“neither stack overflows unless the total array is full.”
我的方法：
第一个栈A：从最左向右增长
第二个栈B：从最右向左增长
第三个栈C：从数组中间位置mid处向两边增长
第三个栈的增长规律可以如下：
第一个入栈C的元素进mid处
第二个入栈C的元素进mid+1处
第三个入栈C的元素进mid-1处
第四个入栈C的元素进mid+2处
...
为了保证栈C满足“neither stack overflows unless the total array is full.”，
可令mid=floor((length-1)/2)（length为数组长度，并假设数组下标从0开始，floor()为向下取整函数）。
[解决办法]
如果可以规定入栈操作的优先级的话，那上面的方案中，入栈优先级为：栈C>栈A>栈B
如果不可规定入栈操作的优先级，上面的方法也不可行。
[解决办法]
题目有问题。即使一个数组实现两个栈，也不可能在没有额外空间的情况下"neither stack overflows unless the total array is full"。要么空出一个位置标志栈顶，要么需要额外空间做标志。
假设题意允许额外空间作标志，分别记录三个栈的高度，利用1楼的交叉索引法，
0号栈所占数组索引为0，3，6，9，12......(K*3 + 0)
1号栈所占数组索引为1，4，7，10，13......(K*3 + 1)
2号栈所占数组索引为2，5，8，11，14......(K*3 + 2)
三个栈都从左往右增长。在这段空间占满之前，栈顶元素下标可以直接用记录的栈高计算出，因此插入、查询、删除复杂度都是O(1)。
当一个栈满后，插入元素时，不妨设要往0号栈插入，则新加入元素在1号栈的预留空间中从右向左增长，若1号栈预留空间也满，则在2号栈预留空间从右向左增长，若也满则数组已满，无法压栈；若1号栈已超过预留空间大小并占了2号栈的空间，则将1号栈的最后一个空间位置腾给0号栈的新元素，而把原来的元素移到2号栈右端，已再2号栈空间中的1号栈元素顺序左移。删除元素时是逆过程。查找元素仍然可通过直接计算下标得到。因此插入、删除复杂度是O(n)，查询复杂度是O(1)。
如果不允许用额外空间作标志，则需要在数组内部留空做标志，仍可采用上面的空间布局，栈顶留一空位即可，但所有的插入、删除、查询复杂度都是O(n)。
[解决办法]
静态链表也有它的问题，相对来说，空间利用率比较差。这个要看你怎么看问题。从题目的要求来看，对空间利用率的要求还是比较高的，所以从这个角度来看，静态链表不是好办法，还不如直接平均选择三个位置作为堆栈的起始位置，遇上一个堆栈满的时候，平移一个堆栈的位置（通常可以让两个堆栈起始位置相同，方向相反，而我们只移动第三个堆栈）。而因为移动堆栈的概率相对来说应该不算太高，所以实际上复杂度还可以接受。如果发现中间的堆栈增长最快，还可以通过换成移动另外两个堆栈来提高效率
[解决办法]
2楼甚合我意
如果只是模拟2个堆栈的话，那一个从低向高PUSH 一个从高向低PUSH， 空间利用和效率都没问题
关键现在要加入第3个堆栈C，要处理以下：
1）初始位置：我认为是左起1/3处，向右递增PUSH，
2）PUSH POP处理： 显然应该还是堆栈，不可能左边PUSH一下，右边PUSH一下，，元素的次序乱了
3）推论： 要达到题目要求的充分利用空间，在必要时必须移动堆栈C ~~~~~~
4) 为提高效率，仅当A B C 进行PUSH且可能与产生重叠时，将C移动到A B两个栈顶所夹区间段的居中位置
