Practice-It

Write a method called reverseByN that takes a queue of integers and an integer n as parameters and that reverses each successive sequence of length n in the queue. For example, suppose that a variable called q stores the following sequence of values:

        front [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] back

and we make the following call:

        reverseByN(q, 3);

Then q should store the following values after the call:

        front [3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13] back

Notice that the first three values (1, 2, 3) have been reversed, as have the next three values (4, 5, 6), the next three values (7, 8, 9), and so on. If the size of the queue is not an even multiple of n, then there will be a sequence of fewer than n values at the end. This sequence should be reversed as well. For example, if q stores this sequence:

        front [8, 9, 15, 27, -3, 14, 42, 8, 73, 19] back

and we make the call:

        reverseByN(q, 4);

Then q should store the following values after the call:

        front [27, 15, 9, 8, 8, 42, 14, -3, 19, 73] back

Notice that the two sequences of length 4 have been reversed along with the sequence of two values at the end (73, 19). If n is greater than the size of the queue, then the method should reverse the entire sequence.

You are to use one stack 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 may not use recursion to solve this problem and your solution must run in O(n) time. Use the Stack and Queue interfaces and the ArrayStack and LinkedQueue implementations discussed in lecture. You may assume n >= 0.