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;
	}

	@Override
	public 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();
	}

	@Override
	public 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;
		else
			i = 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;
}