1.6K
Question: How do we implement 2 stacks using only one array? Our stack routines should not indicate an exception unless every slot in the array is used?
SOLUTION:
Algorithm:
- Start with two indexes, one at the left end and other at the right end
- The left index simulates the first stack and the right index simulates the second stack.
- If we want to push an element into the first stack then put the element at left index.
- Similarly, if we want to push an element into the second stack then put the element at the right index.
- First stack grows towards the right and the second stack grows towards left.
CAN WE EXTEND THIS METHOD FOR 3 STACKS?
Sure we can, but the possibility is limited by the size of the array, here is one scenario:-
To implement 3 stacks we keep the following information:-
- The index of the first stack (Top1) : This indicates the size of the first stack.
- The index of the second stack (Top2) : This indicates the size of the second stack.
- Starting index of the third stack (base address of the third stack).
- Top index of the third stack
Now let us try to define the PUSH and POP operations:-
PUSHING
- For pushing on to the first stack, we need to see if adding a new element causes it to bump into the third stack. If so, try to shift the third stack upwards. Insert the new element at (start1 + Top1).
- For pushing on tho the second stack, we need to see if adding a new element causes it to bump into the third stack. If so, try to shift the third stack downward. Insert the new element at (start2 – Top2).
- When pushing to the third stack, see if it bumps the second stack. If so, try to shift the third stack downward and try pushing again. Insert the new element at (start3 + Top3).
POPING
- For pop, we do not need to shift, just decrement the size of the appropriate stack.
