19章 泛型

1.修改程序清单19-1中的GenericStack类，使用数组而不是ArrayList来实现它。你应该在给栈添加新元素之前检查数组的大小如果数组满了，就创建一个新数组。该数组是当前数组大小的两倍，然后将当前数组的元素复制到新数组中。

public class GenericStack<E> {private E[] arr = (E[]) new Object[16];private int n = 0;public int getSize() {return n;}public E peek() {return arr[n - 1];}public void push(E o) {if (n == arr.length) {E[] tmp = (E[]) new Object[arr.length << 1];System.arraycopy(arr, 0, tmp, 0, arr.length);arr = tmp;}arr[n++] = o;}public E pop() {if (n == 0) return null;return arr[--n];}public boolean isEmpty() {return n == 0;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder("stack: [");for (E e : arr)sb.append(e).append(',').append(' ');sb.deleteCharAt(sb.length() - 1);sb.setCharAt(sb.length() - 1, ']');return sb.toString();}
}

2.程序清单19-1中，GenericStack是使用组合实现的。定义一个新的继承自ArrayList的栈类。画出UML类图，然后实现GenericStack。编写一个测试程序，提示用户输入5个字符串，然后以逆序显示它们。

public class GenericStack<E> extends ArrayList<E> {public int getSize() {return super.size();}public E peek() {return super.getLast();}public void push(E o) {super.add(o);}public E pop() {if (super.isEmpty()) return null;return super.removeLast();}public boolean isEmpty() {return super.isEmpty();}@Overridepublic String toString() {return "stack: " + super.toString();}public static void main(String[] args) {GenericStack<String> strings = new GenericStack<>();System.out.println("请输入5个字符串：");Scanner scanner = new Scanner(System.in);for (int i = 0; i < 5; i++)strings.add(scanner.next());scanner.close();for (int i = 0; i < 5; i++)System.out.println(strings.pop());}
}

3.编写以下方法，返回一个新的ArrayList。该新列表中包含来自原列表中的不重复元素。

public static <E> ArrayList<E> removeDuplicates(ArrayList<E> list) {return new ArrayList<E>(new HashSet<>(list));
}

4.为线性搜索实现以下泛型方法。

public static <E extends Comparable<E>> int linearSearch(E[] list, E key) {for (int i = 0; i < list.length; i++)if (list[i].compareTo(key) == 0)return i;return -1;
}

5.实现下面的方法，返回数组中的最大元素。编写一个测试程序，提示用户输入10个整数，调用该方法找到最大数并显示。

public class Test {public static <E extends Comparable<E>> E max(E[] list) {E m = list[0];for (int i = 1; i < list.length; i++)if (list[i].compareTo(m) > 0)m = list[i];return m;}public static void main(String[] args) {Integer[] integers = new Integer[10];Scanner scanner = new Scanner(System.in);for (int i = 0; i < 10; i++) {integers[i]=scanner.nextInt();}scanner.close();System.out.println(max(integers));}
}

6.编写一个泛型方法，返回二维数组中的最大元素。

public static <E extends Comparable<E>> E max(E[][] list) {E m = max(list[0]); // 使用第5题的结果for (int i = 1; i < list.length; i++) {E t = max(list[i]);if (t.compareTo(m) > 0)m = t;}return m;
}

7.使用二分查找法实现下面的方法。

public static <E extends Comparable<E>> int binarySearch(E[] list, E key) {int i = 0, j = list.length - 1;while (i <= j) {int m = (i + j) >> 1, compareRes = list[m].compareTo(key);if (compareRes == 0)return m;if (compareRes > 0)j = m - 1;elsei = m + 1;}return -1;
}

8.编写以下方法，打乱ArrayList。

public static <E> void shuffle(ArrayList<E> list) {Random random = new Random();for (int i = 0; i < list.size(); i++) {int j = random.nextInt();E tmp = list.get(i);list.set(i, list.get(j));list.set(j, tmp);}
}

9.编写以下方法，对ArrayList排序。

public class Test {public static <E extends Comparable<E>> void sort(ArrayList<E> list) {for (int i = 0; i < list.size() - 1; i++) {int k = i;for (int j = i + 1; j < list.size(); j++)if (list.get(j).compareTo(list.get(k)) < 0)k = j;if (k != i) {E tmp = list.get(i);list.set(i, list.get(k));list.set(k, tmp);}}}public static void main(String[] args) {ArrayList<Integer> list=new ArrayList<>(10);Scanner scanner = new Scanner(System.in);for (int i = 0; i < 10; i++)list.add(scanner.nextInt());sort(list);System.out.println(list);}
}

10.编写以下方法，返回ArrayList中的最大元素。

public static <E extends Comparable<E>> E max(ArrayList<E> list) {if (list.isEmpty()) return null;E m = list.getFirst();for (int i = 0; i < list.size(); i++)if (m.compareTo(list.get(i)) < 0)m = list.get(i);return m;
}