算术

地球人都知道栈最有效率的实现方式就是数组了。如果要求两个栈共享一个数组，为了充分利用空间，我们通常会一个栈放在底部向上生长，另一个放在顶部项下生长。现在，请设计一个算法，最有效率的在一个数组中实现三个栈。这里主要是指空间利用率。

我能想到的方法很简单，而且任何时候空间使用效率不低于整个数组的2/3。将整个数组均匀的分成3段，每段可以实现一个栈。如下图所示，每个栈都自左向右生长。

|AAAAAAAAAA....|BBBBBBBCCCCCCCC|CCCCCCCCCCCCCCC

当一个栈满时，它可以从栈底向左继续生长，只要左边的栈还有空间剩下就行。比如上例中的栈C，在满了之后就反向使用栈B中的剩余空间，直到于B的栈顶相遇为止。同样，但栈B满後，它可以在栈A中继续生长，栈A满后可以在栈C中继续发展。

这已策略保证了在至少2/3的数组空间被填满之前，所有的栈都可以不受限制的发展。当然缺陷也是很明显的，每个栈最长不能超过2/3的数组空间，而且只有一个栈可以占用超过1/3的数组空间。 当然基于这个思路我们可以进一步优化，比如只要记住栈B和C相遇的位置，我们可以允许B或C其中之一在栈A的右端继续发展。这样做算法会变得更加复杂，而总体的空间利用率并没有改善，因为栈B和C不可能被同时满足。

不知道有没有可能出现空间利用率更高的算法。