Make delicious recipes!

Three stacks in single array



Problem: Given an array, implement three stacks using that array such that size exceed exception should not be raised for any stack until there is space left in array.


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.


This strategy works for any number of stacks, not just three!



Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal