小谈队列

小谈队列

 

虽然数组是存储和访问速度最快的数据结构，但是却受创建时其长度、存储的类型就固定限制这一特性所限制。为此我们引入动态存储数据的数据结构——队列。说到队列，现实生活中还真有不少：食堂打菜的学生、超市等待结账的客户、影院排队购票的观影者，现实生活中总是存在排队现象。当我们把队列搬到计算机、搬到JAVA程序中，我们需要找寻队列的特性。

每次排队，人们总会自觉从后面加入队列，当然也有那些不遵循喜欢插队，不介意别人嫌弃的眼光的人。一般最先排队的那个人会最先接收业务处理，处理完毕走出队列，还有那些中途有事儿，退出队伍的人物。发现这些特性，我们基本明确了队列的几个普通方法。下面就是队列的数组实现代码。

import java.util.Arrays;


/**
 *  自定义自己的队列，利用数组实现的
 * @author Daily
 *
 */
public class MyQueque <E>{
	// 队列的属性
	private int size;			// 队列长度
	private Object [] array;	// 当前数组
	
	/**
	 *  定义MyQueque类的构造方法（默认添加方式）
	 */
	public MyQueque(){
		
	}

	/**
	 *  定义MyQueque类的构造方法（初始化时，添加一个元素）
	 *  @param ob	要添加的元素
	 */
	public MyQueque(E ob){
		add(ob);
	}
	
	/**
	 * 	默认方式
	 *  向队列中添加一个元素（队列只能从元素组最后一个位置添加元素）
	 * @param ob	要添加的元素
	 */
	public void add(E ob){
		// 创建一个数组对象
		Object [] newarray = new Object[size+1];
		// 存储原数组的前size-1个元素
		for (int i=0; i < size; i++){
			newarray[i] = array[i];
		}
		newarray[size] = ob;
		// size减小1个单位
		size++;
		// 在原数组中存入新开辟数组内存首地址的值
		array = newarray;
	}
	
	/**
	 *  向队列中添加一个元素（在特定的位置添加元素）
	 * @param index	给定的位置
	 * @param ob	要添加的元素
	 */
	public boolean add(int index, E ob){
		if (index > size){
			return false;
		}
		// 创建一个数组对象
		Object [] newarray = new Object[size+1];
		// 存储原数组的前size-1个元素
		for (int i=0; i < index; i++){
			newarray[i] = array[i];
		}
		newarray[index] = ob;
		for (int i=index+1; i<size+1; i++){
			newarray[i] = array[i-1];
		}
		// size减小1个单位
		size++;
		// 在原数组中存入新开辟数组内存首地址的值
		array = newarray;
		return true;
	}
	
	/**
	 *  默认删除元素（在数组最前面删除一个元素）
	 * @return		删除的元素
	 */
	public E delete(){
		// 创建一个数组对象
		Object [] newarray = new Object[size-1];
		// 存储原数组的前size-1个元素
		for (int i=1; i < size; i++){
			newarray[i-1] = array[i];
		}
		Object copy = array[0];
		// size减小1个单位
		size--;
		// 在原数组中存入新开辟数组内存首地址的值
		array = newarray;
		// 返回最后一个值
		return (E)copy;
	}
	
	/**
	 *  根据所给下标位置，删除元素
	 * @param index	下标位置
	 * @return		删除的元素
	 */
	public E delete(int index){
		if (index > size || index < 0){
			return null;
		}
		// 创建一个数组对象
		Object [] newarray = new Object[size-1];
		if (size-1>0){
			// 存储原数组的前size-1个元素
			for (int i=0; i < size-index; i++){
				newarray[i] = array[i];
			}
			for (int i=index+1; i<size; i++){
				newarray[i-1] = array[i];
			}	
		}
		Object copy = array[index];
		// size减小1个单位
		size--;
		// 在原数组中存入新开辟数组内存首地址的值
		array = newarray;
		// 返回最后一个值
		return (E)copy;
	}
	
	/**
	 *  根据元素值，删除数组中的元素（PS：当为Integer类型的变量时，无法与位置查找的删除方法进行区分)
	 * @param ob	删除的元素值
	 * @return		是否删除成功
	 */
	public boolean delete(E ob){
		int count = 0;
		boolean bl = false;
		for (int i=0; i<size; i++){
			if (array[i].equals(ob)){
				count++;
				bl = true;
			}
		}
		// 创建一个数组对象
		Object [] newarray = new Object[size-count];
		int u=0;
		// 存储原数组的前size-1个元素
		for (int i=0; i < size; i++){
			if (!array[i].equals(ob)){
				newarray[u] = array[i];
				u++;
			}
		}
		// size减小count个单位
		size = size -count;
		// 在原数组中存入新开辟数组内存首地址的值
		array = newarray;
		// 返回删除操作是否执行标志
		return bl;
	}
	
	/**
	 *  根据所给位置修改元素
	 * @param index	需要修改的位置
	 * @param ob	修改后的值
	 * @return		是否修改成功
	 */
	public boolean modify(int index,E ob){
		array[index] = ob;
		return true;
	}
	
	/**
	 *  根据所给位置查找元素
	 * @param index	需要查找的位置
	 * @return		该位置的元素
	 */
	public E get(int index){
		return (E)array[index];
	}
	
	/**
	 *  根据所给元素值查找位置
	 * @param index	需要查找的位置
	 * @return		该位置的元素
	 */
	public int [] get(Object ob){
		int count = 0; 
		for (int i=0; i<size; i++){
			if (array[i].equals(ob)){
				count++;
			}
		}
		int [] flag = new int [count];
		int u=0;
		for (int i=0; i<size; i++){
			if (array[i].equals(ob)){
				flag[u] = i;
				u++;
			}
		}
		return flag;
	}
	
	/**
	 *  得到队列的长度
	 * @return	队列的长度
	 */
	public int getSize(){
		return size;
	}
	
	/**
	 *  对队列进行排序
	 * @return	返回排好序的队列
	 */
	public E [] getSort(){
		Arrays.sort(array);
		return (E[])array;
	}
}

 PS:因为所有类型都是Object类型的子类，因而加入元素定义为Object类型的对象，实现了数组不能存储不同类型的功能。而队列每次加入或者删除一个元素的时候，都会新建一个数组来存储相应数据，实现了数据的动态存储。为了将队列中的所有数据规定为同一类型，我使用了泛型。