Then, add some recursion methods.

PrintReverse Methods:

/**Additional Operations*/

/**

* Prints in reverse order to the

* console, followed by a new line

* by calling the recursive helper

* method printReverse

*/

public void printReverse() {

return;

}

/**

* Recursively prints to the console

* the data in reverse order (no loops)

* @param node the current node

*/

private void printReverse(Node node) { }

Sorted Order Methods (10 pts):

• For both the Queue and Stack classes, write a recursive method to determine whether or not a Queue or Stack is in sorted order (smallest value to largest value).

public class Stack> {

• Because we want to call compareTo to compare data of type T in the below isSorted method, we need to make sure our class extends Comparable for the type of data we are storing. This signature guarantees that any type T stored in our Queue and Stack will implement Comparable and override compareTo

/**Accessor Methods*/

/**

* Determines whether data is sorted

* in ascending order by calling

* its recursive helper method isSorted()

* Note: when length == 0

* data is (trivially) sorted

* @return whether the data is sorted

*/

public boolean isSorted() {return false;}

/**

* Helper method to isSorted

* Recursively determines whether data is sorted

* @param node the current node

* @return whether the data is sorted

*/

private boolean isSorted(Node node) { return false;}

Search Methods:

• Now, add two search methods to the Queue and Stack classes - linear and binary search

• The first of these methods is going to be a simple linear search method.

• Note that the pseudocode for the two methods is given in the class notes.

• If you are uncertain how to begin, the best approach would be to look at the notes from the Lesson 7 and 8.

• Hint: Recall that you should not use == with Object types, but must use .equals()

• You will need to add the following methods to your two classes:

/**

* Uses the iterative linear search

* algorithm to locate a specific

* element and return its position

* @param element the value to search for

* @return the location of value

* from 1 to length

* Note that in the case length==0

* the element is considered not found

*/

public int linearSearch(T element) { return -1; }

• Next, add a method to perform recursive binary search on the Queue and Stack.

• Please note that you will receive no credit for your binarySearch method if it is not implemented recursively.

/**

* Returns the location from 1 to length where value is located

* by calling the private helper method binarySearch

* @param value the value to search for

* @return the location where value is

* stored from 1 to length, or -1 to

* indicate not found

* @precondition isSorted()

* @throws IllegalStateException when the precondition is violated.

*/

public int binarySearch(T value) throws IllegalStateException {

return -1;

}

/**

* Searches for the specified value in

* by implementing the recursive binarySearch algorithm

* @param low the lowest bounds of the search

* @param high the highest bounds of the search

* @param value the value to search for

* @return the location at which value is located

* from 1 to length or -1 to indicate not found

*/

private int binarySearch(int low, int high, T value) {

return -1;

}

• Important: For credit, you must implement the recursive version of binary search

recursive Binary Search Pseudocode

Pre: A[] is sorted in increasing order

method binarySearch(A[1 ... n], value, low, high)

if high < low

return not found

mid := low + (high-low)/2; //the midpoint formula

if a[mid] := value

return mid

else if value < A[mid] //search the left half

return binarySearch(A, value, low, mid-1)

else //search the right half

return binarySearch(A, value, mid+1, high)

Linear Search Pseudocode:

for each item in the container:

if that item has the desired value

stop the search and return the item's location return -1.