logo Practice-It logo

mirrorSplit

Language/Type: Java Collections Stacks and Queues
Author: Stuart Reges (on 04/02)

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).

Type your solution here:


This is a method problem. Write a Java method as described. Do not write a complete program or class; just the method(s) above.

You must log in before you can solve this problem.


Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.