JAVA Implement the static method declared as follows and answer the questions be
ID: 3806234 • Letter: J
Question
JAVA
Implement the static method declared as follows and answer the questions below:
/**
* Reports the smallest integer in the given {@code Queue}.
*
* @param q
* the queue of integer
* @return the smallest integer in the given queue
* @requires q /= empty_string
* @ensures
* min is in entries(q) and
* for all x: integer
* where (x is in entries(q))
* (min <= x)
*
*/
private static int min(Queue q) {...}
Why do you need the requires clause?
Why is the first line of the ensures clause important (min is in entries(q))? Explain what the implementation could do if this line was not included in the postcondition.
Implement the static method declared as follows:
/**
* Reports an array of two {@code int}s with the smallest and the
* largest integer in the given {@code Queue}.
*
* @param q
* the queue of integer
* @return an array of two {@code int}s with the smallest and the
* largest integer in the given queue
* @requires q /= empty_string
* @ensures
* { minAndMax[0], minAndMax[1] } is subset of entries(q) and
* for all x: integer
* where (x in in entries(q))
* (minAndMax[0] <= x <= minAndMax[1])
*
*/
private static int[] minAndMax(Queue q) {...}
Note that because in Java a function can return only one value and it is not possible to return other values through the parameters, we are forced to return an array with the minimum and maximum integers of the given queue as elements.
Consider the minAndMax operation again. Write a second implementation for this operation that uses the "Noah's Ark" algorithm. This algorithm takes entries from q in pairs, first comparing them to each other, then comparing the smaller of the pair to the minimum so far and the larger of the pair to the maximum so far.
/**
* Reports the smallest integer in the given {@code Queue}.
*
* @param q
* the queue of integer
* @return the smallest integer in the given queue
* @requires q /= empty_string
* @ensures
* min is in entries(q) and
* for all x: integer
* where (x is in entries(q))
* (min <= x)
*
*/
private static int min(Queue q) {...}
Explanation / Answer
1. "Requires" clause is required so that the program does not return Null Pointer Exception. There should be atleast one element in queue to avoid this.
2."min should be an element of queue" because if its not then it'll yield wrong results as it might return a value which is not in the queue(in case assumed integer happens to be the smallest element).
3. Implementation of Functions ::
Queue Class
import java.util.Arrays;
public class Queue<T> {
private int front;
private int rear;
private final int size;
T[] queue;
public Queue(int size) {
if(size<=0){
throw new IllegalArgumentException("Size cannot be less than or equal to zero");
}
this.size = size;
queue = (T[]) new Object[size];
front = -1;
rear = -1;
}
public int getSize(){
return this.size;
}
public boolean isEmpty() {
return (front == -1 && rear == -1);
}
public void enQueue(T value) {
if ((rear+1)%size==front) {
throw new IllegalStateException("Queue is full");
} else if (isEmpty()) {
front++;
rear++;
queue[rear] = value;
} else {
rear=(rear+1)%size;
queue[rear] = value;
}
}
public T deQueue() {
T value = null;
if (isEmpty()) {
throw new IllegalStateException("Queue is empty, cant dequeue");
} else if (front == rear) {
value = queue[front];
front = -1;
rear = -1;
} else {
value = queue[front];
front=(front+1)%size;
}
return value;
}
@Override
public String toString() {
return "Queue [front=" + front + ", rear=" + rear + ", size=" + size
+ ", queue=" + Arrays.toString(queue) + "]";
}
}
Class having implementation of above functions
import java.util.Iterator;
public class MinQueue {
private static int min(Queue q){
int len = q.getSize();
int[] arr = new int[len];
int actSize=0; // Filled size of queue as queue might not be full
while(!q.isEmpty()){
arr[actSize] = (int) q.deQueue();
actSize++;
}
for(int i=0;i<actSize;i++){
q.enQueue(arr[i]);
}
int min = arr[0];
for(int i=1;i<actSize;i++){
if(arr[i]<min)
min=arr[i];
}
return min;
}
private static int[] minAndMax(Queue q){
int len = q.getSize();
int[] arr = new int[len];
int actSize=0;
while(!q.isEmpty()){
arr[actSize] = (int) q.deQueue();
actSize++;
}
for(int i=0;i<actSize;i++){
q.enQueue(arr[i]);
}
int min = arr[0],max = arr[0];
for(int i=1;i<actSize;i++){
if(arr[i]<min)
min = arr[i];
if(arr[i]>max)
max = arr[i];
}
return new int[]{min,max};
}
private static int[] NoahArk(Queue q){
int len = q.getSize();
int[] arr = new int[len];
int actSize=0;
while(!q.isEmpty()){
arr[actSize] = (int) q.deQueue();
actSize++;
}
for(int i=0;i<actSize;i++){
q.enQueue(arr[i]);
}
if(actSize%2==0){
int min = arr[0],max = arr[0];
for(int i=0;i<actSize;i+=2){
int big = (arr[i]>arr[i+1])?arr[i]:arr[i+1];
int small = (arr[i]<arr[i+1])?arr[i]:arr[i+1];
if(small<min)
min = small;
if(big>max)
max = big;
}
return new int[]{min,max};
}else{
int min = arr[0],max = arr[0];
for(int i=1;i<actSize;i+=2){
int big = (arr[i]>arr[i+1])?arr[i]:arr[i+1];
int small = (arr[i]<arr[i+1])?arr[i]:arr[i+1];
if(small<min)
min = small;
if(big>max)
max = big;
}
return new int[]{min,max};
}
}
public static void main(String args[]){
Queue<Integer> newQueue = new Queue(6);
newQueue.enQueue(10);
newQueue.enQueue(20);
newQueue.enQueue(30);
newQueue.enQueue(40);
newQueue.enQueue(50);
newQueue.enQueue(60);
int[] arr1 = new int[2];
int[] arr2 = new int[2];
arr1 = minAndMax(newQueue);
arr2 = NoahArk(newQueue);
System.out.println("Min - "+min(newQueue));
System.out.println("Min - "+arr1[0]+" max - "+arr1[1]);
System.out.println("Min - "+arr2[0]+" max - "+arr2[1]);
}
}
Note:: Above is the array implementation of Queue....
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.