一、实现一个简单队列
1、链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表有一系节点组成，节点可以在运行时动态生成。每个节点包括两个部分，一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。
2、数组的缺陷：
数组是有长度限制的，如果我们要往数组中存储数据，在我们不知道要存储多少的时候，要怎么初始化数组长度呢？我们只能给数组一个固定的初始长度，所以，我们不能让数组的长度随我们存储数据的增多而增加。
3、队列应运而生：
人类是很聪明的动物，于是乎，我们创造了队列这种数据结构，队列的长度可以随我们存储数据的增多而增长，也可以随我们存储数据的减少而减少。
4、链表、数组和队列的共同点：
链表、数组和队列本质上是相同的，他们都是一种存储数据的容器。
5、数组和队列的不同点：
数组长度固定，队列长度可以变化。
6、数组与链表的不同点：
1）数组是连续的，链表是离散的。
也就是说，数组表示的是一连串连续地址。链表节点表示的地址是不连续的。
2）数组利于查找，链表不利于查找。
因为数组可以看做是一种天然的数据结构，它得天独厚之处在于它的连续性，为我们的查找提供了很大的便利。
相反，对于链表，由于它的不连续性，使得每查找一个节点都要遍历一遍链表，消耗多大，不利于查找。
3）数组不利于删除和插入，链表利于删除和插入。
上天是公平的。
对于数组，它的连续性为删除和插入操作造成了阻碍。当插入或删除一个数时，都需要移动该数位置之后的所有的数，需要遍历整个数组。
对于链表，当插入或删除一个数时，只需要改变该数上一个节点的next指针。而不需要遍历整个链表。
二、用数组实现一个队列并优化：
1、用数组实现一个简单队列：
前面我们已经学习了如何用数组和链表实现一个简单队列，用数组实现简单队列add方法如下：
/**
* 实现泛型队列
* @author zr
*
* @param <E>
*/
public class STList<E> implements NetJavaList<E>{
//队列内部初始用来装对象的数组，长度为0
private Object [] srcA = new Object [0];
//向队列中加入一个对象
public void add(E e) {
//1、新建一个数组，长度是原数组长度+1
Object [] destA = new Object [srcA.length+1];//如果该数组长度为10，那么srcA.length就为9
//2、将要加入的对象放入新数组的最后一个位置
destA[srcA.length]=e;//注意：数组的位置从0开始，因为数组长度为10，0~9，故最后一个位置是9
//3、将原数组中的东西放到新数组中：使用系统提供的数组copy方法
System.arraycopy(srcA, 0, destA, 0, srcA.length);
//指向新建的数组
srcA=destA;
}
//取得队列中指定位置的一个对象，如果指定了类型，则转为指定类型返回
public E get(int index) {
E st=(E)srcA[index];
return st;
}
public int size() {
return srcA.length;
}
}
这样实现的队列，有很多缺点：
1）不能对队列中的对象进行插入和删除操作；
2）使用该队列的人不能设置数组的初始长度；
3）每增加一个对象，就要开辟一个空间，并且都要将数组中的所有元素重新赋值，使得程序效率变低。
2、用数组实现队列并优化：
针对以上问题，提出一些解决方案：
1）对队列进行扩展，加入insert和delete方法；
2）重载构造方法，传入参数，让使用者可以对某些属性进行初始化
3）增加效率（优化）：
举个例子：
假如我们要开个会，有两种方案：
i） 每来一个人就去买一张椅子；
ii） 一开始就买好10张椅子，当十张椅子坐满了，再去买5张椅子，当这5张椅子也坐满了，又去买5张……
比较两种方案，显然，方案2）更节省人力。
同理，我们把实际问题应用与程序中：
因为每增加一个对象，就要开辟一个空间，并且都要将数组中的每个元素重新赋值。虽然每次所需的空间不大，但是程序运行所需的时间却很多，这就给计算机造成了负担。如果我们每次开辟多个空间，即实例化一个数组对象，这样，每add一个对象，就放到数组中，就不需要每次对数组中的所有元素重新赋值，当数组存满时，再实例化一个数组对象，这样一来，开辟空间的次数变少了，所花的时间也变少了，对数组中所有元素赋值的时间也变少了，效率自然就提高了。
/**
* 用数组实现一个队列并优化
* @author zr
*
*/
public class ArrayQueue<E> {
private int inlength;//数组的初始长度
private int count;//添加对象的次数
private int incount;//数组每次增长的长度
private int arraycount;//数组增长的次数
private Object [] obj;
// private Object [] obj=new Object[inlength];
{
System.out.println("aaa");
}
/**
* ArrayQueue aq=new ArrayQueue
* 定义一个构造函数，用来初始化inlength和incount的值
* @param inlenght 数组的初始长度
* @param incount 数组每次增长的长度
*/
public ArrayQueue(int inlength,int incount){
System.out.println("bbb");
this.inlength=inlength;
this.incount=incount;
obj=new Object[inlength];
}
public static void main(String[] args){
ArrayQueue aq=new ArrayQueue(100,10);
}
/**
* 定义一个无参构造器，分别给定了inlength和incount默认值，inlength=10,incount=5
*/
public ArrayQueue(){
this(10,5);
}
/**
* 定义了一个构造方法，用于初始化incount的值，并给定了inlength的默认值10
* @param incount
*/
public ArrayQueue(int incount){
this(10,incount);
}
/**
* 在队列中指定位置之后插入一个元素
* @param index 指定的位置
* @param e 插入的对象
*/
public void insert(int index,E e){
//当指定位置小于或等于数组长度时
if(index<obj.length){
//新建一个数组，长度是原数组长度+1
Object [] obj2=new Object[obj.length+1];
for(int i=0;i<obj.length+1;i++){
//将index位置之前（包括index）的元素放到新数组中
if(i<index||i==index){
obj2[i]=obj[i];
}
else if(i==index+1){
//将插入的元素放到index之后的位置
obj2[i]=e;
}else{
//将index之后元素的位置向后移动一个位置
obj2[i]=obj[i-1];
}
}
obj=obj2;
}
//当指定位置大于数组长度时
else{
System.out.println("您指定的位置大于队列长度，不能插入！");
}
}
/**
* 删除队列中指定位置的一个元素
* @param index 指定的位置
*/
public void delete(int index){
//当指定位置小于数组长度时
if(index<obj.length){
//新建一个数组，长度是原数组长度-1
Object [] obj2=new Object[obj.length-1];
for(int i=0;i<obj.length-1;i++){
//将index位置之前的元素放到新数组中
if(i<index){
obj2[i]=obj[i];
}
//把index位置之后的元素向前移动一个位置
else{
obj2[i]=obj[i+1];
}
}
//指向新的数组
obj=obj2;
}else{
System.out.println("您指定的位置超出了队列的长度，不能删除！");
}
}
/**
* 向队列中加入一个对象
* @param e 队列中加入的对象
*/
public void add(E e){
// System.out.println("obj.length="+obj.length);
count++;
// System.out.println("count="+count);
int length=inlength+arraycount*incount;//为保存对象预留的长度
//当数组的长度超过length时
if(count>length){
//1、新建一个数组，长度是原数组长度+incount
Object [] obj2=new Object[obj.length+incount];
arraycount++;//数组每增长一次加1
//2、将原数组中的东西放到新数组中
for(int i=0;i<obj.length;i++){
obj2[i]=obj[i];
}
//3、将要加入的对象放入新数组的最后一个位置
obj2[obj.length]=e;
//指向新建的数组
obj=obj2;
}
//当数组的长度小于length时，把对象添加到已存在的数组中
obj[count-1]=e;
}
/**
* 取得队列中指定位置的一个对象
* @param index 指定的位置
* @return 返回指定位置的对象
*/
public E get(int index){
E e0=(E) obj[index];
return e0;
}
/**
* 得到队列的长度，即队列中元素的个数
* @return 返回队列中元素的个数
*/
public int size(){
return obj.length;
}
}
三、用链表实现一个队列并扩展
《用链表实现队列》中，链表实现的队列只能添加数据。下面我们在此基础上进行扩展，定义了delete和insert方法，可以对队列中的元素进行删除和插入操作。
/**
* 链表节点类
* @author zr
*
*/
public class LinkNode {
public Object data;
public LinkNode next;
}
/**
* 用链表实现一个队列并扩展
* @author zr
*
*/
public class LinkListQueue<E> {
private LinkNode root;
LinkNode tem1=new LinkNode();//tem1作为一个临时节点
public LinkListQueue(LinkNode root){
this.root=root;
}
/**
* 在队列中指定位置之前插入一个对象
* @param index 指定的位置
* @param e 插入的元对象
*/
public void insert(int index,E e){
int length=size();
LinkNode tem=new LinkNode();
LinkNode tem2=new LinkNode();
tem2.data=e;
int c=1;
if(index<1){
System.out.println("位置从1开始！");
}else if(index==1){
tem2.next=root;
root=tem2;
}else if(index>1&&index<=length){
tem1=root;
while(c<index+1){
if(c==index-1){
tem2.next=tem1.next;
tem1.next=tem2;
tem1=tem2;
}else{
tem=tem1.next;
tem1=tem;
}
c++;
}
}else{
System.out.println("您指定的位置超出了队列长队，请重新指定！");
}
}
/**
* 删除队列中指定位置的某一元素
* @param index 指定的位置
*/
public void delete(int index){
LinkNode tem=new LinkNode();
int c=1;
int length=size();
if(index<0){
System.out.println("位置从1开始");
}else if(index==1){
root=root.next;
}else if(index<=length&&index>1){
tem1=root;
while(c<=index){
if(c==index-1){
tem=tem1.next.next;
tem1.next=tem;
tem1=tem;
}else{
tem=tem1.next;
tem1=tem;
}
c++;
}
}else{
System.out.println("您指定的位置超出了队列范围，请重新指定！");
}
}
/**
* 向队列中添加一个对象
* @param obj 所要添加的对象
*/
public void add(E e){
if(root==null){
root=new LinkNode();
root.data=e;
}else{
LinkNode tem=new LinkNode();
tem.data=e;
int length=size();
tem1=get(length);
tem1.next=tem;
tem1=tem;
}
}
/**
* 获得指定位置的节点
* @param index 指定的位置
* @return 返回指定位置的节点
*/
public LinkNode get(int index){
int length=size();
LinkNode node = new LinkNode();
LinkNode tem=new LinkNode();
if(index<1){
System.out.println("位置从1开始");
}else if(index>=1&&index<=length){
int c=1;
tem1=root;
while(c<index||c==index){
if(c==index){
node=tem1;
}
c++;
tem=tem1.next;
tem1=tem;
}
}else{
System.out.println("您指定的位置超出了队列范围，请重新指定位置！");
}
return node;
}
/**
* 计算队列的长度
* @return 返回队列的长度
*/
public int size(){
int length=0;
LinkNode tem2=new LinkNode();
LinkNode tem=new LinkNode();
tem2=root;
while(tem2!=null){
tem=tem2.next;
tem2=tem;
length++;
}
return length;
}
}
/**
* 测试用一个链表实现的队列
* @author zr
*
*/
public class LLQTest {
private static LinkNode root;
public static void main(String[] args) {
LinkListQueue<String> llq=new LinkListQueue<String>(root);
//对添加操作的测试
System.out.println("添加后：");
llq.add("a");
llq.add("b");
llq.add("c");
llq.add("d");
llq.add("e");
for(int i=1;i<=llq.size();i++){
LinkNode node=llq.get(i);
System.out.println(i+":"+node.data);
}
//对删除操作的测试
System.out.println("删除后：");
llq.delete(2);
for(int j=1;j<=llq.size();j++){
LinkNode ADnode=llq.get(j);
System.out.println(j+":"+ADnode.data);
}
//对插入操作的测试
System.out.println("插入后：");
llq.insert(2, "b");
for(int t=1;t<=llq.size();t++){
LinkNode AInode=llq.get(t);
System.out.println(t+":"+AInode.data);
}
}
}
结果：
添加后：
1:a
2:b
3:c
4:d
5:e
删除后：
1:a
2:c
3:d
4:e
插入后：
1:a
2:b
3:c
4:d
5:e
相关推荐
java 动态的数组链表 java 动态的数组链表 java 动态的数组链表
利用数组和链表实现队列的基本操作，如入队，出队，读出队首元素
数组、链表、队列、栈数据结构特点，各自优点和缺点 数组和链表.pdf
在队列的代码中，引用了链表的代码
Java数组链表效率-Java数组和链表三种遍历效率对比 数组和链表.pdf
go语言通过数组和链表的方式实现队列 数组和链表.pdf
python利用数组和链表实现栈和队列 数组和链表.pdf
线性结构和非线性结构、稀疏数组、队列、链表（LinkedList） 数组和链表.pdf
JavaSE-数组集合和链表集合 数组和链表.docx
队列关于数组与链表的实现， linux c语言
循环链表队列的代码实现 循环数组队列的代码实现
遍历数组和链表 数组和链表.pdf
Java基础-模拟HashMap集合（基于数组和链表） 数组和链表.pdf
pythonlist是数组还是链表实现的-数组和链表结构（python）-1 数组和链表.pdf
python算法-数组和链表 数组和链表.pdf
完整代码 正确产生结果 三个类分开写 class linklist { protected: struct node { int data; node *next; }; node *head; int length; public:
数组、链表、队列、栈的区别和联系 数组和链表.pdf
数组和链表的时间复杂度 (1) 数组和链表.pdf
数组、链表、堆栈和队列、线性表和顺序表 数组和链表.pdf
3-软件课程设计补充知识-数组和链表 数组和链表.ppt