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; } } } }