3.1.txt

I would grow one stack from the beginning of the array, the second stack from the end, and the third stack from the middle, alternating the sides and keeping track of the boundaries.

If the array is called M, and the stacks are called A, B and C, we'd have:

* A[i] = M[i],
* B[i] = M[M.size()-1-i], and
* C[i] = M[M.size()/2 + ((i+1)/2)*(-1)*(i%2)]

If we add sequential numbers to each spot, the array would look like:

[0,1,2,3,4,5,6,_,_,_,_,_,6,4,2,0,1,3,5,_,_,_,_,_,6,5,4,3,2,1,0]
             ^A_top      ^C_left     ^C_right    ^B_top

We'd check for collisions between A_top vs C_left and B_top vs C_right, to prevent stack overflowing.

This way, the space is fairly divided between each stack. If each stack pushes a value in turns, the number of spaces each stack occupies when a stack overflow occurs is approximately the same.

This would keep O(1) push and pop time, but can potentially fill before all spaces are occupied, if one of the edge stacks fills faster than the other.

If we want to use 100% of the array, we could shift the middle stack to accomodate for more spaces when we have a collision, making it a "floating" stack. However, for filled arrays this would take O(n) insertion time.

This can be generalized with more "middle" stacks, evenly distributed. If we don't want the insert time to be biased towards the edge stacks (which never have to be shifted), we could implement a circular array and have *all* stacks be "floating".