最近读《算法（第四版）》，作者在介绍背包（Bag）、队列（Queue）和栈（Stack）时顺便简单介绍了 Java 泛型。

比如现在要实现一个栈（一种存储数据的结构），这个栈应该可以存储任意类型的数据，无论是整数、字符串还是我们自己定义的数据结构。一种特别的 Java 机制能够做到这一点，它就是泛型，也叫做参数化类型。

参数化类型，就是让类支持接受类型（类）作为参数，在创建该类对象的时候，我们将具体的类型传递给类，进而创建出支持具体类型的该类对象。

比如，假如 Stack 是泛型类，那么，我们可以将 String 类型作为参数传递给 Stack 类，以创建支持 String 类型的 Stack 对象。

Stack<String> stack = new Stack<String>();
stack.push("Test");
...
String next = stack.pop();

如果没有泛型，我们必须为需要收集的每种数据类型定义（并实现）不同的 API。有了泛型，我们只需要一份 API（和一次实现）就能够处理所有类型的数据。所以泛型简化了代码。

同时，如果你尝试向支持 String 类型的 stack 变量中添加一个 Integer 对象（或是任何其他非 String 类型的数据），你会得到一个编译时错误。所以，泛型使代码更加“静态”，减少了出错的机会。

那么如何实现一个泛型类，也就是如何运用泛型让普通类支持处理所有数据类型？

比如这是一个未实现泛型的定容栈（一种初级栈），它目前只支持存储 String 类型的对象：

public class FixedCapacityStack {
	private String[] a;
	private int N;

	public FixedCapacityStack(int cap) { a = new String[cap]; }

	public boolean isEmpty() { return N == 0; }

	public int size() { return N; }

	public void push(String item) { a[N++] = item; }

	public String pop() { return a[--N]; }

	public boolean isFull() { return N == a.length; }
}

既然泛型即参数化类型（接受类型作为参数），那么要将 FixedCapacityStack 泛型化，首先要像定义带参数函数那样在类定义中添加参数：

public class FixedCapacityStack<Item> {
	...
}

相比于非泛型的类定义，上述定义多了一个 <Item>，这就是 FixedCapacityStack 类的类型参数。

有了类型参数之后，再将类中所有用到具体类型（String）的地方用 Item 代替（类似于在函数内部使用传递过来的参数）：

public class FixedCapacityStack<Item> {
	private Item[] a;
	private int N;

	public FixedCapacityStack(int cap) { a = (Item[]) new Object[cap]; }

	public boolean isEmpty() { return N == 0; }

	public int size() { return N; }

	public void push(Item item) { a[N++] = item; }

	public Item pop() { return a[--N]; }

	public boolean isFull() { return N == a.length; }
}

这样就实现了 FixedCapacityStack 的泛型类。

有一个注意点是，在非泛型的 FixedCapacityStack 类中，使用 a = new String[cap]; 语句创建字符串数组，而在后来的泛型类中，我们用 a = (Item[]) new Object[cap]; 语句创建泛型数组，能不能用 a = new Item[cap]; 语句来创建？答案是不能。由于某些历史和技术原因，直接创建泛型数组在 Java 中是不允许的

所以总结一下，实现一个泛型类：

第一步：在类定义中添加泛型标识 <Item>；

第二步：将类中（除创建泛型数组外的）所有用到具体类型的地方用 Item 代替；

第三步：需要创建泛型数组时，使用类型转换（a = (Item[]) new Object[cap];）来间接创建泛型数组。