ProAnswers.org

How to implement 3 stacks with one array

I want to implement 3 stacks with only 1 array. Is it possible?

How can I do it?

Yes, it is possible to implement 3 stacks in 1 array.

Procedure:
Let the array be a[n]
Take 3 pointers p1, p2, and p3.
Start p1 from a[0] and moves to a[1], a[2], a[3] so on
Start p3 from a[n-1] and moves to a[n-2], a[n-3],a[n-4] so on
Start p2 from a[n/3] and moves to a[n/3+1], a[n/3+2] so on

Now, either p1 reaches a[n/3] or p2 and p3 meet or both.

If both, then there is no more space left in the array.
If either of the two, we have space left in array. The space will be in the form of a block.

Repeat the above procedure in that block.

Take three pointers p, q, r
Array: A[n]
Start p from A[0] and move right A[0]->A[1]->A[2]->so on
Start r from A[n-1] and move left A[n-1]->A[n-2]->A[n-3]->so on
Start q from A[n/2] and move right A[n/2]->A[n/2+1]->A[n/2+2]->so on

Three cases:
(a)p reaches A[n/2]
(b)q and r meet.
©Both (a) and (b)
If ©, no space left
If (a), there is space left between q and r.So shift the pointer q to midway between q and r in the right direction.
If (b), there is space left between p and q.So shift the pointer q to midway between p and q in the left direction.