The practical application of Java generics and the implementation of stack with array

1, Practical application of generics -- Realization of minimum function

I designed a generic function to get the minimum value of the array, and the element type of the array is a subclass of Number and implemented the compatible interface.

public <T extends Number & Comparable<? super T>> T min(T[] arr) {  //Because Number does not have implements Comparable, you need to & check the types together
        if (arr == null || arr.length == 0)  //Array uninitialized or empty
            return null;
        
        //If the array has elements, find the minimum        
        T min = arr[0];
        for (int i = 1; i < arr.length; i++) { //arr.length Is the number of elements of the array
            if (min.compareTo(arr[i]) > 0)  //>0 Explain min>arr[i]
                min = arr[i];
        }
        return min;
        
}

The T before min is the return value type, and the array of T type is passed in. The minimum value returned is also the T type.

The Comparable interface has only one method: compareTo(), which compares two sizes and returns an int value. Table 1 is the front large, 0 represents two equal, and - 1 represents the back (in brackets) large.

If the array element does not implement the Comparable interface, it is OK to directly be greater than or less than the comparison.

 

 

Test:

    Integer minInteger = min(new Integer[]{1, 2, 3}); //int Type array
    Double minDouble = min(new Double[]{1.2, 2.2,4.5});//double Type array
    System.out.println(minInteger);
    System.out.println(minDouble);
    
    // String typeError = min(new String[]{"1","3"});//Array of type String,Error report, unable to compile, because String No extends Number

 

Why do numeric arrays use Integer? Because the basic type does not implement the compatible interface, the wrapper types all implement this interface.

public final class Integer extends Number implements Comparable<Integer>

public final class Character implements java.io.Serializable,Comparable<Character> 

public final class String implements java.io.Serializable, Comparable<String>, CharSequence

 

Strictly speaking, basic types such as int, float and char are not classes. They do not inherit Object, nor do they have methods such as hashCode(), equals(). Basic types are at the same level as Object.

The wrapper types are all classes and inherit the Object. The direct parent of a numeric wrapper type is the Number class.

 

 

 

 

 

2. Using array to implement stack

To implement a stack, you need to have the basic methods of push(), pop() (return to the top of the stack and stack), peek() (return to the top of the stack but not stack), isEmpty(), size().

 

public class MyStack {
    private int[] arr; //An array of elements in the stack. Declared here as int Type array, modify as needed. You can also use generics
    private int capacity; //Stack capacity
    private int count; //Number of elements in the stack
    private static final int GROW_FACTOR = 2; //Growth factors. When the array capacity is not enough,*2 Double capacity (to be realized by yourself)

    //Construction method without initial capacity. Default capacity is 10
    public MyStack() {
        this.capacity = 10;
        this.arr=new int[10];
        this.count = 0;
    }

    //Construction method with initial capacity
    public MyStack(int initialCapacity) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException("Capacity is too small.");
        this.capacity = initialCapacity;
        this.arr = new int[initialCapacity];
        this.count = 0;
    }

    //Array expansion,Internal call, private
    private void addCapacity() {
        int newCapacity = capacity * GROW_FACTOR;
        arr = Arrays.copyOf(arr, newCapacity); //After the capacity of the array is determined, it cannot be modified later. Only copy To the new array, arr Point to new array
        capacity = newCapacity;
    }

    //Push
    public void push(int value) {
        if (count == capacity) { //Check the capacity first, and expand when it is full
            addCapacity();
        }
        arr[count++] = value;
    }

    //Returns the top element of the stack and exits the stack. The stack is exposed to external calls. Many functions are called by the stack itself (processing the elements in the stack), private. Exposure to external calls is fine.
    private int pop() {
        if (count == 0)
            throw new IllegalArgumentException("Stack is empty.");
        count--; //This element still exists in the array. To traverse the stack (array), use count Count, cannot directly traverse the entire array
        return arr[count];
    }

    //Return to top of stack element does not stack
    private int peek() {
        if (count == 0)
            throw new IllegalArgumentException("Stack is empty.");
        return arr[count-1];
    }

    //Judge whether the stack is empty
    private boolean isEmpty() {
        return count == 0;
    }

    //Returns the number of elements in the stack
    private int size() {
        return count;
    }
    
}

 

Use:

MyStack myStack = new MyStack(5);
myStack.push(1);  //Push
myStack.push(2);

 

 

Code in red above:

arr = Arrays.copyOf(arr, newCapacity);

 

Arrays.copyOf() has multiple overloaded methods, corresponding to the replication of arrays of different types. Look at the source code. Take int [] as an example:

public static int[] copyOf(int[] original, int newLength) {
        int[] copy = new int[newLength];
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
}

Parameters: length of source array and new array. Create a new array with the specified capacity, copy the elements in the source element group to the new array, and return the new array.

If the new length is less than the length of the source array, then copy as many as you can, until the new array is full;

If the newLength is greater than the length of the source array, the elements of the source array will be copied, and the remaining unfilled elements will be filled with the default value of the element type.

Tags: Java less

Posted on Sat, 14 Mar 2020 02:20:59 -0700 by webtechatlantic