Question

Language: Java

A function is said to have side effects if it changes something outside of its scope or does something other than return a value.

A void function is obviously intended to have side effects; since it doesn't return anything, it is expected to change something. On the other hand, if a function does return something, it is usually expected that it will have no side effects

In this lab, you will complete a method that is intended to have no side effects; you should be able to run this method as many times as you want on an object, with no difference in the result.

Problem Statement
Complete this function so that it returns a count of the number of times an object x of generic type T is found on a Stack.

(In this case, the stack is implemented with linked nodes, but that should be irrelevant to your code; your function should work the same with any implementation of a Stack).

When the method ends the Stack should store exactly the same data as at the beginning of the method. However, your function will need to alter the Stack data as it runs.

Answer 1

Here is the completed code for this method. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

Note: Since you did not provide the method header (prototype of the method you need), I have created the method entirely from scratch. And below are two different implementations. Choose whichever you prefer. Assuming a stack has basic operations: push(), pop() and isEmpty().

1) Method using loop and a temporary stack to solve this problem.

/**
 * method to count number of times x occur in a given stack, without
 * changing order of elements in stack.
 * 
 * @param <T>
 *            any type
 * @param x
 *            value to be counted
 * @param stack
 *            stack of T type elements
 * @return count of x in stack
 */
public static <T> int count(T x, Stack<T> stack) {
        // initializing count to 0
        int c = 0;
        // creating a temporary stack
        Stack<T> temp = new Stack<T>();
        // looping until stack is empty
        while (!stack.isEmpty()) {
                // removing top value
                T value = stack.pop();
                // if this value equals x, updating count
                if (value.equals(x)) {
                        c++;
                }
                // pushing top value to temp stack
                temp.push(value);
        }
        // now simply moving each element from temp stack to original stack, so
        // that elements will be back in original order.
        while (!temp.isEmpty()) {
                stack.push(temp.pop());
        }
        //returning count
        return c;
}

2) Method using recursion to solve this problem without using another stack.

/**
 * same method, but written recursively, thus avoiding the need to use a
 * secondary stack
 */
public static <T> int count(T x, Stack<T> stack) {
        // base case: if stack is empty, returning 0
        if (stack.isEmpty()) {
                return 0;
        }

        // initializing count to 0
        int c = 0;
        // removing top value
        T value = stack.pop();
        // if this value equals x, updating count
        if (value.equals(x)) {
                c++;
        }
        // finding count of x in remaining stack, recursively, and adding to
        // count
        c += count(x, stack);
        // pushing back removed value.
        stack.push(value);

        // returning count
        return c;
}