一、分析
队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。允许插入的一端称为队尾，允许删除的一端称为队头。
链队是指采用链式存储结构实现的队列，它的基本操作如下：
1、初始化链队
2、销毁链队
3、清空链队
4、检测链队是否为空
5、返回链队的元素个数
6、返回链队头元素
7、向队尾插入元素
8、删除并返回队头元素
9、遍历链队
通常链队用单链表来表示，但一个链队还需要两个分别指示队头和队尾的指针才能唯一确定，和单链表一样，为了便于操作，附设一个头结点来指示队头。
在Java中，我们可以将链队中的结点视作一个类，类中拥有属性data、nextQueue和lastQueue分别表示数据、下一结点和队尾，链队的基本操作即为类的方法，每个结点就是一个对象。这样，初始化链队就是实例化头结点，销毁链队就是将头结点销毁，链队就会因为缺少引用而被销毁。
二、实现
1、定义类属性和构造函数
1 class InitQueue{ 2 3 private int [] data = new int[1]; //定义成数组是为了可以用null表示空 4 5 private InitQueue nextQueue; 6 7 private InitQueue lastQueue; 8 9 public InitQueue() { //头结点的初始化 10 this.data = null; 11 this.nextQueue = null; 12 this.lastQueue = this; 13 } 14 15 public InitQueue(int data) { //普通结点的初始化 16 this.data[0] = data; 17 this.nextQueue = null; 18 this.lastQueue = null; 19 } 20 }
2、清空链队
1 public void clearQueue() { 2 this.nextQueue = null; //头节点的下一结点置空 3 this.lastQueue = this; //尾指针指向头结点 4 }
3、检测链队是否为空
1 public boolean queueEmpty() { 2 if(this.nextQueue == null) { 3 return true; 4 } 5 return false; 6 }
4、返回链队的元素个数
1 public int queueLength() { 2 3 InitQueue theQueue = this.nextQueue; //获取头结点的下一结点地址（链队的第一个结点） 4 int i = 0; 5 6 for (i = 0; theQueue != null; i++) { //循环读取并计数 7 theQueue = theQueue.nextQueue; 8 } 9 return i; 10 }
5、返回链队头元素
1 public int [] getHead() { 2 if(this.nextQueue == null) { //如果链队为空，返回空 3 return null; 4 } 5 return this.nextQueue.data; 6 }
6、向队尾插入元素
1 public void enQueue(int input) { 2 InitQueue initQueue = new InitQueue(input); //实例化新结点 3 this.lastQueue.nextQueue = initQueue; //插入队尾 4 this.lastQueue = initQueue; //尾指针指向队尾 5 }
7、删除并返回队头元素
1 public int [] deQueue() { 2 3 if (this.nextQueue == null) { //如果链队为空，返回null 4 return null; 5 } 6 7 int [] i = this.nextQueue.data; //获取队头元素数据 8 this.nextQueue = this.nextQueue.nextQueue; //头指针向后移动一位 9 10 if (this.nextQueue == null) { //如果链队变空 11 this.lastQueue = this; //尾指针重新指向头结点 12 } 13 return i; 14 }
8、遍历链队
1 public String queueTraverse() { //这里用输出元素值表示遍历 2 3 InitQueue theQueue = this.nextQueue; 4 String s = ""; 5 6 while(theQueue != null) { //循环读取 7 s += theQueue.data[0] + "、"; 8 theQueue = theQueue.nextQueue; 9 } 10 11 if(s.length() == 0) { //如果未读取到元素值，则返回空字符串 12 return s; 13 } 14 return s.substring(0,s.length() - 1); //除去最后的顿号后返回 15 }
三、小结
以上就是链队用Java的实现，由于只定义了整数的数组，因此只能操作整数数据，但链队的基本思想都已实现。
四、纠正
隔了一段时间又回来看代码，猛地发现这段代码其实还不够完善。(⊙x⊙;)
将链队的基本操作定义成了InitQueue类的方法，实例化结点时，会使每个结点都拥有这些方法，然而其实只有头结点需要这些方法，其他结点都不需要。
因此可以再定义一个Operate类，将链队的基本操作定义成Operate类的静态方法，InitQueue类中只保留属性和构造方法，当需要对链队操作时，在头结点上调用Operate类中的方法即可。
InitQueue类中的data属性，其实可以定义成String类型，由于int类型的数据可以转化成String类型存储，这样链队可以操作的数据类型就变宽了。
这里我就不改了，放在这里提醒自己（其实是因为懒……（＞＜））。
- 还没有人评论，欢迎说说您的想法！
客服
