PrintReverse Methods (10 pts):- For *both* the Queue and Stack classes, write the below recursive methods to display the Queue and Stack in reverse.
/**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) {
return;
}
- Why do we need the private helper method here?
- Since
we are going to be traversing Node-by-Node, in a recursive
fashion, we want to pass one Node at a time to the reversePrint method.
- However, since Nodes are private, we cannot access them outside of the Queue or Stack class.
- We would therefore not be able to call this method in QueueTest.java or StackTest.java, for example.
- Not convinced? Try it and see for yourself
- Also, here is a review of private and other access modifiers
- Therefore, we write the public prinReverse method whose main task is to call the private printReverse method.
- It is the private printReverse method that does most of the work.
- However, we can call the public printReverse method in QueueTest.java or StackTest.java and other classes without provoking an error.
- Important: Test each method carefully inside of your QueueTest.java or StackTest.java to make sure that it is working properly.
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).
- First, update your class signature as follows to extend Comparable.
public class Queue<T extends Comparable<T>> {
public class Stack<T extends Comparable<T>> {
- 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
- For a review of Comparable and compareTo, see the information here
- Add the following method signatures to the Queue and Stack classes under the section for accessor methods.
/**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;
}
- Test your method in QueueTest.java and StackTest.java.
Search Methods (20 pts):
- 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:
/**Accessor Methods*/
/** * 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.
- Add the following method signatures to the Queue and Stack classes:
/**
* 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.
- To implement binarySearch, you can adapt the pseudocode provided below for binarySearch on an array.
- Test your method in QueueTest.java and StackTest.java.
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.