Netjava Lesson10 会变的数组——自定义队列

2013.07.28

 

上课内容：自定义队列

 

这节课我们学习自定义队列。首先我们来回顾一下上节课的内容，上节课我们讲的是数组，我们知道了数组的一些优点和缺点，这里我们总结一下：
优点：
1、数组可以快速地通过下标访问自己所需要的数据，访问速度快。
2、数组是引用传递，这里我们在五子棋里就用到了数组常量，地址不允许改变，但可以改变里面的值，非常方便
3、数组存储的是同以数据类型，不会把自己搞乱
4、一个数组可以存储大量数据，起到简化代码的作用

 

缺点：
1、数组的大小一开始就被限定了
2、数组的类型一开始也被限定了，如果想寸其他数据类型的就要新建一个数组

 

通过数组的缺点，我们发现数组的局限性在于其大小被限定，如果开始放的很大会耗费资源，如果开始创建的小的话就有可能不够用。那么如果我们想改变数组大小该怎么办呢？我们今天用自定义队列来实现。
自定义队列当然还是数组，但是可以通过不断新建数组改变队列长度的大小，我们说数组名是地址，那么我们用改变后长度的数组地址赋给原地址就可以了！
比如说：

int[] array = new int[1];
array[0]=1;
int[] array2 = new int[2];
array = array2;

 那么此时array[0]的值为0，且长度为2，这就是数组名指向的是地址的含义。

 

我们下来建立一个字符串队列：

//初始化队列长度
int size;
//初始化队列数组
String[] array;
//添加add方法
public void add(String str){
	//新建一个临时数组，长度为原来队列加一
	String[] temp = new String[size+1];
	//循环把原数组值赋给临时数组
	for(int i = 0;i<size;i++){
		temp[i] = array[i];
	}
	//把要加入的值赋给临时数组
	temp[size] = str;
	//临时数组地址给原数组
	array = temp;
	//队列长度增加1
	size++;
}

 

然后我们可以接着依次定义其他的一些方法，比如在指定位置插入一个字符串，删除指定位置字符串，获取队列大小等……
那么当我想建立一个队列存储我的一个自定义类，就要新建一个来存放整型的队列类，这样显然会很麻烦。为了简化，我们引入了泛型。下面我们介绍一下泛型：
泛型用E表示，这里我们要注意泛型的类型参数只能是类类型（包括自定义类），不能是简单类型。而Object表示所有的类的祖先，所有的类都继承它。那么我们现在就要用泛型来代表这种类，下面是用泛型我具体实现的队列。

定义队列前，我们下创建一个接口：

public interface List<E> {
	public void add(E e);//将指定的元素添加到此列表的尾部。
	public void inner(int index,E element);//将指定的元素插入此列表中的指定位置。
	public E get(int Index);//返回此列表中指定位置上的元素。
	public void set(int index,E element);//用指定的元素替代此列表中指定位置上的元素。
	public void remove(int index);//移除此列表中指定位置上的元素。
	public int size();//返回此列表中的元素数。
	public void clear();//清空队列
}

 

下面我们创建CustomList来实现这个接口：

/**
 * 定义自定义的对象实现类，实现接口List
 * 
 * @author TTH
 * 
 * @param <E>数据类型
 */
public class CustomList<E> implements List<E> {
	// 初始化数组大小
	private int size = 0;
	//定义数组对象
	private Object[] array;

	/**
	 * 构造方法
	 */
	public CustomList() {
		array = new Object[0];
	}

	/**
	 * 构造方法
	 * 
	 * @param length数组长度
	 */
	public CustomList(int length) {
		array = new Object[length];
	}

	/**
	 * 将指定的元素添加到此列表的尾部
	 */
	public void add(E e) {
		//建立临时的数组，长度为原数组加一
		Object[] arraytemp = new Object[array.length + 1];
		//对数组进行循环
		for (int i = 0; i < array.length; i++) {
			//将原数组的值赋给临时数组
			arraytemp[i] = array[i];
		}
		//把新增的值赋给临时数组
		arraytemp[array.length] = e;
		//将临时数组的地址给原数组
		array = arraytemp;
		//数组大小加一
				size++;
	}

	/**
	 * 将指定的元素插入此列表中的指定位置
	 */
	public void inner(int index, E e) {
		//定义临时数组，长度为原数组加一
		Object[] arraytemp = new Object[array.length + 1];
		//对要插入位置前进行循环
		for (int i = 0; i < index; i++) {
			//将要插入位置前的数据给临时数组
			arraytemp[i] = array[i];
		}
		//将要插入的数据赋给临时数组
		arraytemp[index] = e;
		//对插入位置后面进行循环
		for (int i = index; i < array.length; i++) {
			//将要插入后的数据给临时数组
			arraytemp[i + 1] = array[i];
		}
		//将临时数组的地址给原数组
		array = arraytemp;
		//数组大小加一
		size++;
	}

	/**
	 * 返回此列表中指定位置上的元素
	 * 
	 * @param index指定的位置
	 */
	public E get(int index) {
		//判断指定位置是否不在数组范围内
		if (index < 0 || index > size)
			//如果不在范围，返回空
			return null;
		//否则返回该位置的数据类型
		return (E) array[index];
	}

	/**
	 * 用指定的元素替代此列表中指定位置上的元素。
	 */
	public void set(int index, E e) {
		array[index] = e;
	}

	/**
	 * 移除此列表中指定位置上的元素
	 */
	public void remove(int index) {
		Object[] arraytemp = new Object[array.length - 1];
		for (int i = 0; i < index; i++) {
			arraytemp[i] = array[i];
		}
		for (int i = index; i < array.length - 1; i++) {
			arraytemp[i] = array[i + 1];
		}
		array = arraytemp;
		//数组大小减一
				size--;
	}

	/**
	 * 返回此列表中的元素数
	 */
	public int size() {
		return size;
	}

	/**
	 * 清空队列
	 */
	public void clear() {
		//长度为0
		size=0;
		//队列重置
		array = new Object[0];
	}
}