Question: Please help me to figure out this queue and stack file. Thank you so much! import java.util.NoSuchElementException; public class Queue { private class Node {
Please help me to figure out this queue and stack file. Thank you so much!
import java.util.NoSuchElementException;
public class Queue
private class Node {
private T data;
private Node next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
private int length;
private Node front;
private Node end;
/**
* Default constructor for the Queue class
* @postcondition a new Queue object with all fields assigned default values
*/
public Queue() {}
/**
* Copy constructor for the Queue class
* @param original the Queue to copy
* @postcondition a new Queue object which is
* an identical, but distinct, copy of original
*/
public Queue(Queue
/**
* Returns the value stored at the front of the Queue
* @return the value at the front of the queue
* @precondition !isEmpty()
* @throws NoSuchElementException when the precondition is violated
*/
public T getFront() throws NoSuchElementException {return null;}
/**
* Returns the length of the Queue
* @return the length from 0 to n
*/
public int getLength() { return -1; }
/**
* Determines whether a Queue is empty
* @return whether the Queue is emtpy
*/
public boolean isEmpty() { return false; }
/**
* Determines whether two Queues contain
* the same values in the same order
* @param o the Object to compare to this
* @return whether o and this are equal
*/
@Override public boolean equals(Object o) { return false; }
/**
* Inserts a new value at the end of the Queue
* @param data the new data to insert
* @postcondition a new node at the end of the Queue
*/
public void enqueue(T data) {}
/**
* Removes the front element in the Queue
* @precondition !isEmpty()
* @throws NoSuchElementException when
* the precondition is violated
* @postcondition the front element has
* been removed
*/
public void dequeue() throws NoSuchElementException {}
/**
* Returns the values stored in the Queue
* as a String, separated by a blank space
* with a new line character at the end
* @return a String of Queue values
*/
@Override public String toString() {
String result = "";
result += " ";
return result;
}
}
Here is the stack file.
import java.util.NoSuchElementException;
public class Stack {
private class Node {
private T data;
private Node next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
private int length;
private Node top;
/****CONSTRUCTORS****/
/**
* Default constructor for the Stack class
* @postcondition a new Stack object with all fields
* assigned default values
*/
public Stack() {}
/**
* Copy constructor for the Stack class
* @param original the Stack to copy
* @postcondition a new Stack object which is
* an identical, but distinct, copy of original
*/
public Stack(Stack original) {}
/****ACCESSORS****/
/**
* Returns the value stored at the top
* of the Stack
* @return the value at the top of the Stack
* @precondition !isEmpty()
* @throws NoSuchElementException when the
* precondition is violated
*/
public T peek() throws NoSuchElementException {
return null;
}
/**
* Returns the length of the Stack
* @return the length from 0 to n
*/
public int getLength() { return -1; }
/**
* Determines whether a Stack is empty
* @return whether the Stack is emtpy
*/
public boolean isEmpty() { return false; }
/**
* Determines whether two Stacks contain
* the same values in the same order
* @param Q the Stack to compare to this
* @return whether Q and this are equal
*/
@Override public boolean equals(Object o) { return false; }
/****MUTATORS****/
/**
* Inserts a new value at the top of the Stack
* @param data the new data to insert
* @postcondition a new node at the end
* of the Stack
*/
public void push(T data) {}
/**
* Removes the top element of the Stack
* @precondition !isEmpty()
* @throws NoSuchElementException when
* the precondition is violated
* @postcondition the top element has
* been removed
*/
public void pop() throws NoSuchElementException{}
/****ADDITONAL OPERATIONS****/
/**
* Returns the values stored in the Stack
* as a String, separated by a blank space
* with a new line character at the end
* @return a String of Stack values
*/
@Override public String toString() {
String result = "";
result += " ";
return result;
}
}
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.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help