Solution: The obvious solution is to have the two stacks at the two ends of the array. The stacks will grow in opposite direction. When the two stacks collide and there is no more room in the array the stacks will over flow. This problem is probably one of the easier problems and targeted towards exercising your array index manipulation skills. See the figure below for a visual representation of the two stacks in the array.
Code (C#):
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Array2Stacks { ////// DualStack class implements 2 stacks in a single array. /// Stack A starts on the right and increases towards the left /// Stack B starts on the left and increases towards the right /// When both stacks meet there is no more room for adding items /// The cool thing about the dual stack is that both stacks share the /// same array with built in collision detection. If one stack was empty /// the other stack can potentially use the entire array. /// public class DualStack { int size = 50; //default array size int stackATop = -1; int stackBTop = 50; public DualStack(int size) { this.size = size; array = new object[this.size]; stackBTop = size; } //one array to hold the two stacks object[] array = null; //pushes an item on stack A public bool PushStackA(object obj) { if (stackATop < stackBTop - 1) //we have at least one empty slot in the array { array[++stackATop] = obj; return true; } else { //return false if stack is full return false; } } //pops an item from stack A public object PopStackA() { if (stackATop >= 0 && stackATop < stackBTop) { //take the element at the top of the stack object obj = array[stackATop]; stackATop--;//decrement stack top pointer return obj; } return null; } /// pushes an item on stack B public bool PushStackB(object obj) { if (stackBTop > stackATop + 1) //we have at least one empty slot between the stacks { array[--stackBTop] = obj; return true; } else { //stack is full return false; } } public object PopStackB() { if (stackBTop < this.size && stackBTop > stackATop) //stack is not empty { object obj = array[stackBTop]; stackBTop++; return obj; } else { //stack is empty return null; } } } }
Helped me a lot..Thanx :)
ReplyDeletewhat are the advantages and disadvantages of implementing 2 or n stacks using single array?
ReplyDeleteSavitha,
ReplyDeleteThe advantage is you can get by with a single buffer (save memory). This is true only if only one of the stacks is bigger than the other and you don't know the potential sizes of the stacks. This is how stack and heap are laid out for an operating system process. They both grow towards each other.
The disadvantage is it complicates things a big since you have to make sure you handle the case when the two stack meet. You don't want them to overwrite each others data.
thanks
ReplyDeleteactually my instructor asked me this following question , can u pls help me out in understanding this concept
ReplyDeletecan many stacks be implemented using 1 push and 1 pop?
can it be of different of different size? if NO what modification has to be done to make it YES?
need to implement it using C programme.
ReplyDeleteIn implement two stacks in one array push is very easy. but pop is difficult.
ReplyDeleteIn the popStackA() operation, isn't it enough if we check stackATop >= 0 alone.
ReplyDeleteWhy do we bother whether stackATop < stackBTop too?
>> In the popStackA() operation, isn't it enough if we check stackATop >= 0 alone.
ReplyDeleteWhy do we bother whether stackATop < stackBTop too?
I agree
I think there is no need of stackATop < stackBTop this condition in pop to stack
ReplyDeleteand similarly for stackb...