链式队列介绍
链式队列拥有队列的特性，只不过和顺序队列的区别是，顺序队列底层用的是数组存储元素，而链式队列用的是链表结构存储数据，也就是把一个元素和指向下个结点的指针封装成一个结点，这里称为Node，当队列为空，头指针与尾指针均指向头结点，只不过头结点为空结点，下面是链式队列的结构图
一个结点抽象成Node类，代码如下：
private class Node {
private E data;
private Node next;
public Node(E data) {
this.data = data;
}
}
初始
成员变量
链式队列需要有个指向队首的指针，指向队尾的指针，这里把这两个均声明为Node类型，当然队列需要容量和统计队列内元素的个数，代码如下：
private final AtomicInteger size = new AtomicInteger();
private final int capacity;
// 队列的头结点
private Node head;
// 队列的尾结点
private Node tail;
构造函数
在构造函数中初始化队列，当队列为空时，头指针与尾指针均指向头结点，头结点不存储数据
public LinkQueue() {
this(Integer.MAX_VALUE);
}
public LinkQueue(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
tail = head = new Node(null);
}
public LinkQueue(E element) {
this(Integer.MAX_VALUE);
// 初始Node，只有一个节点
Node newNode = new Node(element);
head.next = newNode;
tail = newNode;
size.incrementAndGet();
}
基本操作
入队
链式队列也实现我们在顺序队列写好的接口，所以入队也有两种操作，抛异常和不抛异常，分别为add(E e)和offer(E e)，这里直接说offer方法，如果队列为空，让头结点指向新的节点，同时让为指针指向新节点，不为空直接正常入队即可，代码如下：
@Override
public boolean add(E e) {
if (offer(e))
return true;
else
throw new IllegalStateException("Queue full");
}
@Override
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
if (size.get() == capacity)
return false;
Node newNode = new Node(e);
if (head == null) {
head.next = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
size.incrementAndGet();
return true;
}
出队
出队也是比较简单的，直接移除队首结点即可，让头结点指向下一个结点，代码如下：
@Override
public E poll() {
if (!isEmpty()) {
Node node = head.next;
head.next = node.next;
size.decrementAndGet();
return node.data;
}
return null;
}
清空队列
清空队列是让除了头结点的结点全部清除掉，解除关联，代码如下：
@Override
public void clear() {
head.next = null;
tail = null;
size.set(0);
}