数组、链表、队列
1、 计算机中的存储方式可以大致分为两类：离散存储、有序存储。
其中的典型代表为链表和数组。
2、 数组的定义格式： 数据类型【】 数组名=new 数据类型【数组长度】；
数据类型【】 数组名={元素表}；
数据类型 数组名【】={元素表}；
java中的数组为定长，即在定义时必须给定数组的长度。
由于数组是按顺序存储，所以查找时可以直接根据数组中元素的下标获得所需数据。
3、 链表就像一条隐形的链子，一环扣一环。链表的基本单位是结点，每个结点包括两个部分：该结点中的存储的数据，以及所连接的下个结点。
链表中数据的查找则必须从头开始，依次通过每个结点获得它所连接的下个结点。
一个简单链表的实现可以用如下代码
//首先定义一个结点类
public class Node{
Object data;
Node next;
}
//通过结点的依次添加和连接获得一个链表
Node n1=new Node();
n1.data=所附的值；
Node n2=new Node();
n2.data=所附的值；
Node n3=new Node();
n3.data=所附的值；
... ...
n1.next=n2;
n2.next=n3;
... ...
由以上可以看出，如果使用链表直接存储数据，数据的添加过程将是一个非常繁琐的过程。但是使用队列优化后的链表使用起来就可以非常简单。
4、 队列也是一个存放东西的容器。但队列的使用比数组、链表更加灵活。一个完善的队列可以很方便的实现添加、删除、更改、获得长度、插入、查找等操作。因此通过把数组和链表转化为队列，可以实现对数组和链表的优化，增强其实用性。
以下是分别是用链表和数组实现队列的程序
/** * 定义一个结点类 * @author 陈琳 * @param <E> 泛型标识，便于使用者向链表中传入不同类型的数据 */public class ListNode<E> {private E data;private ListNode<E> next;/** * 设置结点中所存储的数据 * @param e 要存入的数据 */public void setData(E e){this.data=e;}/** * 设置结点所连接的下个结点 * @param next 结点所连接的下个结点 */public void setNext(ListNode next){this.next=next;}/** * 获得结点中所存储的数据 * @return 结点中所存储的数据 */public E getData(){return data;}/** * 获得结点所连接的下个结点 * @return 结点所连接的下个结点 */public ListNode getNext(){return next;}}/** * 定义一个以链表为基础的队列 * @author 陈琳 * @param <E> */public class SingleLinkList<E> {/** * 用root表示链表上的第一个结点，last表示链表上的最后一个结点 */ListNode root;private ListNode last;/** * 设置根节点 * @param e将根节点设置成的内容 */public void setRoot(ListNode e){root=e;}/** * 向链表中添加元素 * @param e添加的元素对象 */public void add(E e){if(root==null){root=new ListNode<E>();root.setData(e);last=root;}else{ListNode<E> tem=new ListNode<E>();tem.setData(e);last.setNext(tem);last=tem;}}/** * 获得链表的长度 * @return 链表的长度 */public int size(){if(root!=null) {int t=1;ListNode<E> tem=root.getNext();while(tem!=null){tem=tem.getNext();t++; }return t;}return 0;}/** * 根据索引值获得结点 * @param index 索引值 * @return 索引值所对应的结点 */public ListNode<E> getNode(int index){if(this.size()<index||index<0){System.out.println("下标越界");return null;}else{ListNode<E> tem=root;for(int i=1;i<index;i++){tem=tem.getNext();}return tem;}}/** * 由节点中数据的值获得此结点所在的位置 * @param e 指定的结点的数据域的值 * @return 指定的结点在链表中的额位置 */public int getIndex(E e){ListNode<E> tem=root;int i=1;for(;i<this.size();i++){tem=tem.getNext();while(tem.getData().equals(e)){break;}}return i;}/** * 在指定位置插入结点 * @param index 链表中指定的位置 * @param e 插入的结点的数据域的值 */public void insert(int index,E e){ListNode<E> newNode=new ListNode<E>();if(index==1){newNode.setData(e);newNode.setNext(root);root=newNode;}else{ListNode<E> tem=root;for(int i=2;i<index;i++){tem=tem.getNext();}newNode.setData(e);newNode.setNext(tem.getNext());tem.setNext(newNode);}}/** * 删除指定位置的结点 * @param index 指定的位置的索引值 */public void delete(int index){if(index==1) root=root.getNext();else{ListNode<E> tem=root;for(int i=2;i<index;i++){tem=tem.getNext();}tem.setNext(tem.getNext().getNext());}}/** * 更改指定位置的结点的值 * @param index 指定结点的位置 * @param e 结点数据域的值需改为的值 */public void update(int index,E e){ListNode<E> aimNode=this.getNode(index);aimNode.setData(e);}/** * 输出链表中各结点数据域的值 * @param root 根节点 */public void printSingleLinkList(ListNode<E> root){ListNode<E> tem=root;if(tem==null) return;System.out.println(tem.getData()+" ");tem=tem.getNext();printSingleLinkList(tem);}}/** * 定义一个数组转化为的队列 * @author 陈琳 */public class ArrayQueue<E> {private int initLength=100;private int increaseLength=10; static int count=0; /** * 用于传递数组初始长度和每次增加长度的构造器 * @param initLength 数组初始长度 * @param increaseLength 每次增加的长度 */ public ArrayQueue(int initLength,int increaseLength){ this.initLength=initLength; this.increaseLength=increaseLength; } /** * 用于传递数组初始长度的构造器 * @param initLength 数组初始长度 */ public ArrayQueue(int initLength){ this.initLength=initLength; } /** * 不用传递任何数据的构造器 */ public ArrayQueue(){ } //初始化数组 Object[] initstr = new Object[initLength]; /** * 向数组中添加元素 * @param e所添加的数据 */public void add(E e){count++;if(count>initstr.length){Object[] temstr = new Object[initstr.length+increaseLength];for(int i=0;i<initstr.length;i++){temstr[i]=initstr[i];}initstr=temstr;}initstr[count-1]=e;}/** * 获得数组中数据的个数 * @return 数据个数 */public int size(){return count;}/** * 通过索引值获得数组中的数据 * @param index 索引值 * @return 数组中的数据 */public E get(int index){if(index<0||index>initstr.length){System.out.println("下标越界");return null;}return (E) initstr[index];}/** * 向数组中插入元素 * @param index 插入的位置 * @param e 插入的数据 */public void insert(int index,E e){if(index>count||index<0){System.out.println("下角标越界");return;} if(count>initstr.length){Object[] temstr = new Object[initstr.length+increaseLength];for(int i=0;i<initstr.length;i++){temstr[i]=initstr[i];}initstr=temstr;}for(int i=count-1;i>=0;i--){if(i!=index-1){initstr[i+1]=initstr[i];continue;}initstr[index]=e;count++;return;}}/** * 删除数组中指定的元素 * @param index 要删除的元素的位置 */public void delete(int index){if(index>count||index<0){System.out.println("下角标越界");return;} for(;index<initstr.length-1;index++){initstr[index]=initstr[index+1];}Object[] temstr = new Object[initstr.length-1];for(int i=0;i<temstr.length;i++){temstr[i]=initstr[i];}initstr=temstr;count--;}/** * 更改数组中的元素 * @param index 要更改的元素的位置 * @param e 要更改为的对象 */public void update(int index,E e){initstr[index]=e;}/** * 遍历并打印数组 */public void printArray(){for(int i=0;i<count;i++){System.out.print("initstr["+i+"]="+initstr[i]+", ");if((i+1)%5==0)System.out.println("");}System.out.println(""+"\n");}}