Three Stack Implemention Using an Array?

Hello everyone, I know how to efficiently use an array to implement two stack,

Algorithm works as Put Top1 as -1 it means first stack will grow from Left to write and put Top2 as Max+1 , This(second) stack will grow from Right to Left,

Now can anybody please explain how to efficiently use an array to implement three stack.

Thanks and Happy Coding , Algorithm with Sudo Code will be very appreciable.

2 Likes

perhaps you can set top1=-1,top2=sizeofstack/2-1 and top3=size…
stack1 grows from left to right upto the mid ,then stack2 comes to play and when the size of stack2 is overflowed then stack3 comes into the picture…
Since you are using an array to implement stacks so it has to be static memory alloc.
In this way knowing the size of the individual stacks you can implement multiple stacks using a single array…
Hope this might help!

I don’t think they expect you to come up with an exact solution to this problem. Different approaches and their advantages could be discuused, depending upon the requirements.

1.) First you could have three stacks with fixed capacities, of say N/3 each. Where N is the size of the original array. The problem here would be that a lot of space may go unused. Although insertions and deletions would be relatively easy. Also unnecessary overflows, even when you have space available.

2.) A second approach could be having a variable boundary between stacks, but this could mean performance reductions. You could maintain two stacks at the endpoints of the array, like you do for two stacks. The third one could be implemented in the middle, modifying the push and the pop operation, so that whenever two boundaries collide, you just shift your middle stack towards free space.

3.) You could have one stack of constant space, and other two sharing a variable boundary, and other variations. Though the design should depend on the usage.

@s24w Stack1 grows left to right thats fine , please elaborate the scenario of stack2 in which direction it grows?

1 Like