各有千秋——数组，链表及用两者实现的队列

 

 

       计算机中两种基本的数据结构式数组及链表，前者是在自然顺序的内存中存储数据，而后者是通过其基本单元——节点的数据域和指针域来存储数据和记录数据间的相对位置，概括地说：数组中的数据位置是连续的，链表中的数据位置是离散的。

 

       这就决定了，在数组中找一个数据很容易（只需知道数组首地址及数据在数组中的位置）；而在链表中改变数据的相对位置很容易（只需改变个别节点的指针域就行）。他们各有优势，也各有劣势，并且优势与劣势恰好相反。

 

       正是这一不同决定了用他们来实现队列时，队列的优势与劣势。

 

       队列的特点是可以改变长度（存储数据的个数），是一种比较理想的数据结构。我们常常要对它进行“增删查改”的工作，或者更根本地说是“找”与“变”的工作。“找”就是找到索引位置的数据，数组队列非常擅长，

“变”就是改变数据间的相对位置关系，链表队列非常擅长。而当我们“变”数组队列时，往往要频繁地新建数组并逐个赋值；当我们“查”链表队列中的数据时，往往要遍历队列，工作量很大。

 

       总之两者各有千秋，适合用于各自擅长的场合，使用时要根据情况灵活选取

 

传上我的队列实现代码：

 

/**
 * 队列的接口，定义一些使用方法
 * @author 朱凌峰
 *
 * @param <E> 泛型
 */
public interface MyQueue<E> {
	//在队列末尾加上一个数据
	public void add(E e);
	//在队列中指定位置插入一个数据
	public void insert(E e,int index);
	//取出指定位置的一个数据
	public E get(int index);
	//删除指定位置的一个数据
	public void remove(int index);
	//改变指定位置的数据
	public void set(E e,int index);
	//获取队列长度
	public int size();
	//按顺序打印队列中的每个数据
	public void printQueue();
	//检验索引位置是否越界，如越界，则抛出异常
	public boolean judgeIndex(int index);
}

/**
 * 定义我自己的数组队列
 * 
 * @author 朱凌峰
 * 
 */
public class MyArrayList<E> implements MyQueue<E> {

	private Object[] dataArray;// 用于存储数据的数组
	int lengthIncreaseStep;// 每次数组长度增加的步长
	int countData = 0;// 数据个数计数器

	/**
	 * 默认构造方法 默认数组初始长度为10，每次数组长度增加的步长为10
	 */
	public MyArrayList() {
		this(10, 10);
	}

	/**
	 * 设定数组初始长度的构造方法
	 * 
	 * @param initLength
	 *            数组的初始长度
	 */
	public MyArrayList(int initLength) {
		this(initLength, 10);
	}

	/**
	 * 设定数组初始长度和每次数组长度增加的步长的构造方法
	 * 
	 * @param initLength
	 *            数组初始长度
	 * @param lengthIncreaseStep
	 *            数组长度增加的步长
	 */
	public MyArrayList(int initLength, int lengthIncreaseStep) {
		this.lengthIncreaseStep = lengthIncreaseStep;
		this.dataArray = new Object[initLength];
	}

	/**
	 * 添加一个数据到队列的末尾
	 * 
	 * @param msAdd
	 *            要添加的数据
	 */
	@Override
	public void add(E e) {
		// 如果数据个数等于当前数组长度
		if (countData == dataArray.length) {
			// 新建加长长度的数组
			Object[] lengthenedArray = new Object[this.dataArray.length
					+ this.lengthIncreaseStep];
			// 将原有数组里的数据从后往前逐个加入到新的数组中
			for (int i = 0; i < dataArray.length; i++) {
				lengthenedArray[i] = dataArray[i];
			}
			// 将添加的数据加入到新建数组中
			lengthenedArray[dataArray.length] = e;
			// 将新建数组指向原数组
			dataArray = lengthenedArray;
		} else {
			dataArray[countData] = e;
		}
		countData++;
	}
	/**
	 * 在索引位置前面一个位置插入数据(若要插在最后一个数据后面，则用add方法)
	 */
	public void insert(E e, int index) {
		if(this.judgeIndex(index)){
			//将原来队列的最后一个数据添加到队列末尾
			this.add(this.get(this.size()-1));
			//将原来最后第二个数据至index向后移动一位
			for(int i =this.size()-3 ;i >=index;i--){
				this.set(this.get(i), i+1);
			}
			//将index位置设置为新插入的数据
			this.set(e, index);
		}
	}

	/**
	 * 获取队列中指定位置的数据
	 * 
	 * @param index
	 *            数据在队列中的位置
	 * @return 指定位置的数据
	 */
	public E get(int index) {
		// 检查index是否有效
		if (judgeIndex(index)) {
			return (E) dataArray[index];
		}
		return null;	
	}

	/**
	 * 移除索引位置对应的数据
	 * @param index 索引位置
	 */
	public void remove(int index) {
		if(this.judgeIndex(index)){
			for (int i = index; i < this.size()-1; i++) {
				dataArray[i]=dataArray[i+1];
			}
			this.countData--;
		}
	}

	/**
	 *设置索引位置的数据值
	 *@param e 数据值
	 *@param index 索引位置
	 */
	public void set(E e, int index) {
		// 检查index是否有效
		if (judgeIndex(index)) {
			this.dataArray[index] = e;
		}
	}

	/**
	 * 获取队列的长度
	 * 
	 * @return 一个整数表示队列长度
	 */
	public int size() {
		return countData;
	}
	/**
	 * 按顺序打印队列中的每个数据，若队列为空则抛出异常
	 */
	public void printQueue() {
		if(this.size()==0)
			throw new java.lang.RuntimeException("队列为空");
		else {
			for (int i = 0; i < this.size(); i++) {
				System.out.println("队列中第"+i+"个数据为："+this.get(i));
			}
		}
	}

	/**
	 * 判断索引位置是否有效,若索引位置有效，则返回true,否则抛出异常
	 * 
	 * @param index
	 *            索引位置
	 * @return 若索引位置有效，则返回true
	 */
	@Override
	public boolean judgeIndex(int index) {
		// 判断索引位置是否有效
		if (index < 0 || index >= this.size()) {
			throw new java.lang.RuntimeException("索引位置" + index + "越界："
					+ ",当前队列大小为：" + this.size());
		}
		return true;
	}
	/**
	 * 将一个队列添加到当前队列的末尾
	 * @param arrayList 要添加到末尾的队列
	 */
	public void addAll(MyArrayList<E> arrayList){
		//新建一个长度为当前队列和要添加到末尾的队列长度之和的数组
		Object[] tempArray=new Object[this.size()+arrayList.size()];
		//将当前队列的每个数据一次添加到临时数组中
		for (int i = 0; i < this.size(); i++) {
			tempArray[i]=dataArray[i];
		}
		//将 要添加到末尾的队列中的每个每个数据添加到临时数组中
		for (int i = 0; i < arrayList.size() ; i++) {
			tempArray[i+this.size()]=arrayList.get(i);
		}
		//将原有数组指向临时数组
		dataArray=tempArray;
		//重新设置数据个数
		countData=this.size()+arrayList.size();
	}

}

/**
 * 链表的节点类
 * @author 朱凌峰
 *
 * @param <E>
 */
public class LinkNode<E> {
	//节点的数据
	private E data;
	//当前节点的子节点
	private LinkNode<E> child;
	private LinkNode<E> parent;//当前节点的父节点
	
	/**
	 * 带参构造器
	 * @param data	创建对象时赋予的初始参数
	 */
	public LinkNode(E data){
		this.data=data;
	}
	/**
	 * 获取当前节点的数据
	 * @return
	 */
	public E getData(){
		return this.data;
	}
	/**
	 * 重新赋予节点数据的值
	 * @param data 重新赋予的值
	 */
	public void setData(E data){
		this.data=data;
	}
	/**
	 * 设置父节点
	 * @param parent 
	 */
	public void setParent(LinkNode<E> parent){
		this.parent=parent;
	}
	/**
	 * 设置子节点
	 * @param child
	 */
	public void setChild(LinkNode<E> child){
		this.child=child;
	}
	/**
	 * 获取当前节点的付节点
	
	 * @return
	 */
	public LinkNode<E> getParent(){
		return this.parent;
	}
	/**
	 * 获取当前节点的子节点
	 * @return
	 */
	public LinkNode<E> getChild(){
		return this.child;
	}
}

package LinkNode20130717;

import zlfsQueue20130714and0716and0722.MyQueue;

/**
 * 用链表实现队列
 * @author 朱凌峰
 *
 */

public class LinkQueue<E> implements MyQueue<E>{

	
	//根节点
	private LinkNode<E> root;
	//最后一个节点
	private LinkNode<E> last;
	/**
	 * 在队列末尾添加一个数据
	 * @param e 要添加的数据
	 */
	public void add(E e){
		//新建一个节点
		LinkNode<E> tempNode=new LinkNode<E> (e);
		//如果队列中还没有节点，则新建一个根节点
		if(root==null){
			root=tempNode;
			//此时最后一个节点即为根节点
			last=root;
		}else{
			last.setChild(tempNode);//该节点为上一个节点的子节点
			tempNode.setParent(last);
			//该节点成为当前的最后一个节点
			last=tempNode;
		}
	}
	/**
	 * 获取指定位置节点的数据
	 * @param index 数据所在位置，根节点的位置为0
	 * @return 
	 */
	public E get(int index){
		LinkNode<E> nodeOfIndex=getNodeOfIndex(index);
		return nodeOfIndex.getData();
	}
	/**
	 * 获取链表队列的大小，即数据个数
	 * @return	
	 */
	public int size(){
		int count=0;
		LinkNode<E> tempNode=root;
		while(tempNode!=null){
			count++;
			tempNode=tempNode.getChild();
		}
		return count;
	}
	/**
	 * 删除指定位置的数据
	 * @param index
	 */
	public void remove(int index){
		LinkNode<E> nodeOfIndex=getNodeOfIndex(index);
		//如果删除根节点
		if(index==0){
			//获取索引位置的节点的子节点
			LinkNode<E> tempChild=nodeOfIndex.getChild();
			root=tempChild;
		}
		//如果删除最后一个节点
		else if(index==this.size()-1){
			//获取索引位置的节点的父节点
			LinkNode<E> tempParent=nodeOfIndex.getParent();
			tempParent=last;
		}
		else {
			//获取索引位置的节点的父节点和子节点
		LinkNode<E> tempParent=nodeOfIndex.getParent();
		LinkNode<E> tempChild=nodeOfIndex.getChild();
		//重新设置父子关系
		tempParent.setChild(tempChild);
		tempChild.setParent(tempParent);
		}
	}
	/**
	 *  重新设置指定位置的数据值
	 * @param e
	 * @param index
	 */
	public void set(E e,int index){
		LinkNode<E> nodeOfIndex=getNodeOfIndex(index);
		nodeOfIndex.setData(e);
	}


	/**
	 * 获取索引位置对应的节点
	 * @param index 索引位置
	 * @return 索引位置对应节点
	 */
	private LinkNode<E> getNodeOfIndex(int index){
		if(this.judgeIndex(index)){
			//找到索引位置对应的节点
			int count = 0;
			LinkNode<E> tempNode=root;
			while(count!=index){
				tempNode=tempNode.getChild();
				count++;
			}
			return tempNode;
		}
		return null;		
	}
	/**
	 * 依次打印队列中每个数据
	 */
	public void printLinkQueue(){
		if(root==null){
			throw new java.lang.RuntimeException("队列为空");
		}
		else{
			int count = 0;
			LinkNode<E> tempNode=root;
			while(tempNode!=null){
				System.out.println("队列中第"+count+"个数据为："
					+tempNode.getData());
				tempNode=tempNode.getChild();
				count++;
			}
		}
	}
	/**
	 * 插入一个数据到索引位置前面一个位置
	 * @param e 要插入的数据
	 * @param index	索引位置
	 */
	public void insert(E e, int index) {
		if (judgeIndex(index)) {
//			新建临时节点保存要插入的数据
			LinkNode<E> tempNode=new LinkNode<E>(e);
			if(index==0){
//				设置当前根节点和临时节点的父子关系
				root.setParent(tempNode);
				tempNode.setChild(root);
//				根节点为临时节点
				root=tempNode;	
			}
			else {
				tempNode.setChild(this.getNodeOfIndex(index));
				tempNode.setParent(this.getNodeOfIndex(index-1));
				
				this.getNodeOfIndex(index).setParent(tempNode);	
				this.getNodeOfIndex(index-1).setChild(tempNode);
			}
		}
	}
	/**
	 * 按顺序打印队列中的每个数据，若队列为空则抛出异常
	 */
	public void printQueue() {
		if(this.size()==0)
			throw new java.lang.RuntimeException("队列为空");
		else {
			for (int i = 0; i < this.size(); i++) {
				System.out.println("队列中第"+i+"个数据为："+this.get(i));
			}
		}	
	}
	/**
	 * 将一个队列添加到当前队列末尾
	 * @param linkQueue 要添加到末尾的队列
	 */
	public void addAll(LinkQueue<E> linkQueue) {
		this.last.setChild(linkQueue.root);
		linkQueue.root.setParent(this.last);
	}
	/**
	 * 判断索引位置是否有效
	 * @param index 索引位置
	 * @return 若索引位置有效，则返回true
	 */
	public boolean judgeIndex(int index) {
		//判断索引位置是否有效 
		if(index<0 || index>=this.size()){
			throw new java.lang.RuntimeException("索引位置越界："+index
					+",当前队列大小为："+this.size());
		}
		return true;
	}
}