本文实例讲述了java基于链表实现队列。分享给大家供大家参考，具体如下：

在开始栈的实现之前，我们再来看看关于链表的只在头部进行的增加、删除、查找操作，时间复杂度均为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<E> { //获取队列中元素个数 int getSize(); //队列中元素是否为空 boolean isEmpty(); //入队列 void enqueue(E e); //出队列 public E dequeue(); //获取队首元素 public E getFront();}

2.LinkedListQueue类

package Queue;public class LinkedListQueue<E> implements Queue<E> { //将Node节点设计成私有的类中类 private class Node<E> { 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<E> 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<E> 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<E> 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<Integer> queue = new LinkedListQueue<Integer>(); 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程序设计有所帮助。