How to implement 3 stacks with one array?

How to implement 3 stacks with one array?

#Approch 1:- 

Space (not time) efficient. You could:

1) Define two stacks beginning at the array endpoints and growing in opposite directions.

2) Define the third stack as starting in the middle and growing in any direction you want.

3) Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.

You need to store the stack top for the first two stacks, and the beginning and end of the third stack in some structure.

Edit

Above you may see an example. The shifting is done with an equal space partitioning policy, although other strategies could be chosen depending upon your problem heuristics.

Alternative way:-

 the middle stack could be implemented using an alternating sequence for subsequent pushes. The resulting stack structure will be something like:

| Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5 |

In this case, you'll need to store the number n of elements on the middle stack and use the function:

f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3  

to know the next array element to use for this stack.

Although probably this will lead to less shifting, the implementation is not homogeneous for the three stacks, and inhomogeneity (you know) leads to special cases, more bugs and difficulties to maintain code.

#Approch 2:- 

Solution: Implementing two stacks is easy.
First stack grows from start to end while second one grows from end to start.
Overflow for any of them will not happen unless there really is no space left on the array.

For three stacks, following is required:

1. An auxiliary array to maintain the parent for each node.
2. Variables to store the current top of each stack.

With these two in place, data from all the stacks can be interspersed in the original array and one can still do push/pop/size operations for all the stacks.

 

When inserting any element, insert it at the end of all the elements in the normal array.
Store current-top of that stack as parent for the new element (in the parents' array) and update current-top to the new position.

When deleting, insert NULL in the stacks array for the deleted element and reset stack-top for that stack to the parent.

When the array is full, it will have some holes corresponding to deleted elements.
At this point, either the array can be compacted to bring all free space together or a linear search can be done for free space when inserting new elements.