Use an array to implement a pair of stacks such that one grows from the bottom (with its first item stored at index 0) and the other grows from the top (with its first item stored at the highest array index). As the stacks grow, the top of the stacks will move closer together. The stacks are full when the two top elements are stored in adjacent array elements (top2 == top1 + 1).

Design, code, and test a class DoubleStack that implements this data structure. DoubleStack should support the normal stack operations (push, pop, peek, empty, etc.), as well as reallocation that is automatically called when the stacks are full. Each stack method should have an additional int parameter that indicates which of the stacks (1 or 2) is being processed. For example, push(1, item) will push item onto stack 1.

[0] top1] top2] stack 1 stack 2