扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
本文实例讲述了java基于链表实现队列。分享给大家供大家参考，具体如下：
创新互联建站是一家专注于成都做网站、成都网站设计与策划设计,达茂旗网站建设哪家好?创新互联建站做网站,专注于网站建设10多年,网设计领域的专业建站公司;建站业务涵盖:达茂旗等地区。达茂旗做网站价格咨询:028-86922220
在开始栈的实现之前，我们再来看看关于链表的只在头部进行的增加、删除、查找操作，时间复杂度均为O(1)。
对于队列这种数据结构，需要在线性结构的一端插入元素，另外一端删除元素。因此此时基于链表来实现队列，则有一端的时间复杂度为O(n)。因此我们不能使用之前已经实现的链表结构，我们需要改进我们的链表。思路如下：
1.参考在链表头部删除、增加元素的时间复杂度为O(1)的思路，我们在链表的尾部设立一个Node型的变量tail来记录链表的尾部在哪，此时再head端和tail端添加元素都是及其简单的，在head端删除元素也是及其简单的，但对于在tail端删除元素时，是无法在时间复杂度为O(1)的情况进行的，也就是从tail端删除元素时不容易的。
2.只在头部head删除元素（队首），在尾部tail端添加元素（队尾）。
3.由于在基于链表实现队列时不涉及到操作链表中间元素，此时我们改进的链表中，不在使用虚拟头节，因此也就可能造成在没有虚拟头节点的情况下，链表为空。
前言，在写本小节之前，我们已经实现了一个基于静态数组的队列，转到查看。此处我们实现基于链表的队列。
在实现基于静态数组的队列的时候，我们已经新建了一个package，此时我们在该package下新建一个LinkedListQueue类，用来实现Queue接口，目录结构为：
1.Queue接口代码
package Queue; public interface Queue{ //获取队列中元素个数 int getSize(); //队列中元素是否为空 boolean isEmpty(); //入队列 void enqueue(E e); //出队列 public E dequeue(); //获取队首元素 public E getFront(); }
2.LinkedListQueue类
package Queue; public class LinkedListQueueimplements Queue { //将Node节点设计成私有的类中类 private class Node { public E e; public Node next; //两个参数的构造函数 public Node(E e, Node next) { this.e = e; this.next = next; } //一个参数的构造函数 public Node(E e) { this.e = e; this.next = null; } //无参构造函数 public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node head, tail; private int size; //显示初始化 public LinkedListQueue() { head = null; tail = null; size = 0; } //获取队列中节点个数 @Override public int getSize() { return size; } //队列中是否为空 @Override public boolean isEmpty() { return size == 0; } //链表尾部进队操作 @Override public void enqueue(E e) { if (tail == null) { tail = new Node(e); head = tail; } else { tail.next = new Node(e); tail = tail.next; } size++; } //链表头部出队操作 @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("链表为空"); } Node retNode = head; head = head.next; retNode.next = null; if (head == null) {//当链表只有一个元素时 tail = null; } size--; return retNode.e; } //获取队首元素 @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("链表为空"); } return head.e; } //为了便于测试，重写object类toString()方法 @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue: front "); Node cur = head; while (cur != null) { res.append(cur + "->"); cur = cur.next; } res.append("NULL tail"); return res.toString(); } }
3.为了便于测试，在LinkedListQueue类中添加一个main函数
//测试用例
public static void main(String[] args) {
LinkedListQueue queue = new LinkedListQueue();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if (i % 3 == 2) {//每添加3个元素出队列一个
queue.dequeue();
System.out.println(queue);
}
}
} 4.结果为
结果分析：每进队3个元素出队列一个。
关于本小节，若您觉得还行、还过得去，记得给个推荐哦~，谢谢！！
本节源码 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LinkedListQueue.java
更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网