In: Computer Science
Without using extra structures, write a recursive method
recursivenumberOfNonZeros (Queue<Integer> q)in Test class (in
stacks_queues package) that receives a queue contains integer
objects and return total number of non zeros in this queue. Then
don’t forget to test the method in the main.
Note: Make sure not to change the order of the other values in
queue after calling the method.
I have implemented the recursivenumberOfNonZeros (Queue<Integer> q) method which returns total of non zero elements of Queue. So for this method, we have to create one auxillary method (extra method) which maintain the elements order after removing and then count sum of removed element.
It means that we have two methods::
1> public intrecursivenumberOfNonZeros (Queue<Integer> q) :- This method call the recursiveTotal(q,q.size()) which maintain the order and also retrn the total sum of queue elements in recusive mannar.
2> public int recursiveTotal(Queue<Integer> q, int size) :- This method calculate sum of non zero element of queue and also add each element into the queue simultaneously so we can maintain the queue order. It will return sum of queue elements when queue size will becomes zero.
In this method, we remove element then after add that element and call the method recusively by calculating sum of non ero elements.
Note: In below program, I used in-build linkedlist class of java collection framework which is used to store the elements in the Queue data structure. Because Queue<Geneirc> is interface so we can not create object so we have to pass reference of another data structure for storing elements then after we can use Queue methods like q.remove(), q.peek(), etc.
I never used any data structure which calculate sum of non zero elements using recursion. It means that I did not used any data structure in recursiveNumberOfNonZeros() method.
Program:-
package stacks_queues;
/*
Here we have to use linkedlist which is
used to create the object of Queue
*/
import java.util.LinkedList;
/*
Here Queue is interface so we have to use linkedlist and give
the reference to the queue object
*/
import java.util.Queue;
public class Test {
/**
* return the sum of queue elements
* @param q
* @return sum of non zero elements
*/
public int recursiveNumberOfNonZeros(Queue<Integer> q){
// sum variable pass to the recursiveTotal() which will add the queue elemnts
int sum = 0;
// call the recursiveTotal() methhod
int total = recursiveTotal(q,q.size(),sum);
// return the total of non zero queue elements
return total;
}
/**
* return sum of non zero elemnts (Auxillary function)
* @param q store elements first in first out mannar
* @param size store the queue length
* @param sum of non zero element
* @return
*/
public int recursiveTotal(Queue<Integer> q, int size, int sum) {
// when size of queue is become zro then method returns zero
if(size == 0){
return sum;
}
int removedElement = 0;
// check whether element of queue is zero or not
if((removedElement = q.remove()) != 0){
// decrement the current size of the queue
size--;
// add removed element so order of queue is not changed
q.add(removedElement);
// calculate sum
sum = sum + removedElement;
// call recursively by calculating each removed element
return recursiveTotal(q, size, sum);
}
// add zero element when queue element is zero
q.add(0);
// decrement the current size of the queue
size--;
// call recursively when queue element is zero
return recursiveTotal(q, size, sum);
}
public static void main(String[] args) {
// now create an object of Test class
Test test = new Test();
// crete an Queue which hold Integers
Queue<Integer> q = new LinkedList<>();
// add element to the queue
q.add(0);
q.add(20);
q.add(30);
q.add(0);
q.add(50);
// call the recursiveNumberOfNonZeors(q)
System.out.println("result of recursiveNumberOfNonZeros(q) is "+test.recursiveNumberOfNonZeros(q));
System.out.println("\nOrder of Queue is same");
System.out.println("Queue : "+q.toString());
}
}
Output:-
I hope you will understand how to calculate the sum of non zero element without affecting the queue order.
Do you feel needful and useful then please upvote me.
Thank you.