Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: [ means inclusive, while ( means exclusive of the end point).
int stackSize = 300;
int[] buffer =newint[stackSize * 3];
int[] stackPointer = {0,0,0}; // stack pointers to track top elementvoidpush(int stackNum, int value) {
/* Find the index of the top element in the array + 1, and
increment the stack pointer */int index = stackNum * stackSize + stackPointer[stackNum]+ 1;
stackPointer[stackNum]++;
buffer[index]= value;
}
intpop(int stackNum) {
int index = stackNum * stackSize + stackPointer[stackNum];
stackPointer[stackNum]--;
int value = buffer[index];
buffer[index]= 0;
return value;
}
intpeek(int stackNum) {
int index = stackNum * stackSize + stackPointer[stackNum];
return buffer[index];
}
booleanisEmpty(int stackNum) {
return stackPointer[stackNum]== stackNum * stackSize;
}
Define two stacks beginning at the array endpoints and growing in opposite directions.
Define the third stack as starting in the middle and growing in any direction you want.
Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.
So this is what happens:
First stack grows from left to right.
Second stack grows from right to left.
Third stack starts from the middle. Suppose odd sized array for simplicity. Then third stack grows like this:
5 3 1 2 4
First and second stacks are allowed to grow maximum at the half size of array. The third stack can grow to fill in the whole array at a maximum.
Worst case scenario is when one of the first two arrays(arrays at both ends) grows at 50% of the array. Then there is a 50% waste of the array. To optimize the efficiency the third array (i.e. the array in the middle) must be selected to be the one that grows quicker than the other two.