Practice-It

Write a method called mirrorSplit that takes a stack of integers as a parameter and that splits each value into two halves, adding new values to the stack in a mirror position. For example, suppose that a stack s stores the following values:

        bottom [14, 20, 8, 12] top

If we make the following call:

        mirrorSplit(s);

Then after the call, the stack should store the following values:

        bottom [7, 10, 4, 6, 6, 4, 10, 7] top
                ^   ^  ^  ^  ^  ^   ^  ^
                |   |  |  +--+  |   |  |
                |   |  +--------+   |  |
                |   +---------------+  |
                +----------------------+
                    mirror positions

The first value 14 has been split in half into two 7s which appear in mirror positions (first and last). The second value 20 has been split in half into two 10s which appear in mirror positions (second and second-to-last). And so on. This example included just even numbers in which case you get a true mirror image. If the stack contains odd numbers, they should be split so as to add up to the original with the larger value appearing closer to the bottom of the stack. For example, if the stack stores these values:

       bottom [13, 5, 12] top

After the call, it would store the following values:

        bottom [7, 3, 6, 6, 2, 6] top
                ^  ^  ^  ^  ^  ^
                |  |  +--+  |  |
                |  +--------+  |
                +--------------+
                mirror positions

The first value 13 has been split into 7 and 6 with the 7 included as the first value and 6 included as the last value. The value 5 has been split into 3 and 2 with 3 appearing as the second value and 2 appearing as the second-to-last value. And so on.

You are to use one queue as auxiliary storage to solve this problem. You may not use any other auxiliary data structures to solve this problem, although you can have as many simple variables as you like. You also may not solve the problem recursively. Your solution must run in O(n) time where n is the size of the stack. Use the Stack and Queue structures described in the cheat sheet and obey the restrictions described there (recall that you can't use the peek method or a foreach loop or iterator).