链表(Linked list)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必按顺序存储，所以插入和删除速度超快。
关于这种队列的数据结构，记住4个字就好：先进先出。
Queue接口继承Collection接口，模拟队列：先进先出(FIFO)。
void add(Object e):将e插入到队列尾部；
Object element():获取队列头部的元素；
boolean offer(Object e):将e插入到队列的尾部，当使用有容量限制的队列时，此方法比add(Object e)方法更好。
Object peek():获取队列头部的元素。如果此双端队列为空，则返回 null。
Object poll():获取并删除队列头部的元素。如果此双端队列为空，则返回 null。
Object remove():获取并删除队列头部的元素。
- PriorityQueue
PriorityQueue是一个比较标准的队列实现类，注意了：这个东西保存队列元素的顺序并不是按照加入队列的顺序，而是按照队列元素的大小重新进行排序。我从来没有用过，所以这里不整理了。用一块代码演示下好了：
import java.util.PriorityQueue; public class Linkin
{
public static void main(String[] args)
{
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.offer(1);
pq.offer(-3);
pq.offer(2);
pq.offer(0);
//pq.offer(null); java.lang.NullPointerException 不能插入空值
System.out.println(pq);//[-3, 0, 2, 1] 顺序莫名其妙的变了，神经病
System.out.println(pq.poll());//-3
} }
- LinkedList 同时实现了2个接口：List Deque。它可以被当成双端队列来使用，自然也可以当成栈。
LinkedList实现了Deque接口，而Deque是Queue的子接口。ArrayDeque是Deque一个典型的实现类，他是一个基于数组实现的双端队列。
Deque自定义方法：
void addFirst(Object e):把元素插入到该双向队列的开头；
void addLast(Object e):把该元素插入到该双向队列的末尾。
Object getFirst():获取但不删除队列第一个元素；
Object getLast():获取但不删除队列最后一个元素；
boolean offerFirst(Object e):将指定的元素插入到该双向队列的开头；
boolean offerLast(Object e):将指定元素插入到双向队列的末尾；
Object removeFirst():删除第一个元素
Object removeLast():删除最后一个元素
LinkedList
Object peekFirst():获取但不删除队列第一个元素，如队列为null,返回null;
Object peekLast():获取但不删除队列最后一个元素，如队列为null,返回null;
Object pollFirst():获取并删除队列第一个元素，如队列为null,返回null;
Object pollLast():获取并删除队列最后一个元素，如队列为null,返回null;
Object pop():从此双端队列所表示的堆栈中弹出一个元素。
void push(Object e):将e推入进该队列栈中。
Object removeFirst():获取并删除队列第一个元素。
Object removeFirstOccurrence(Object o):删除队列第一次出现的o元素；
removeLast():获取并删除队列最后一个元素；
removeLastOccurrence(Object o):删除队列中最后一次出现的o元素；
import java.util.LinkedList; public class Linkin
{
public static void main(String[] args)
{
LinkedList<String> names = new LinkedList<String>();
//将字符串元素加入到队列的尾部
names.offer("LinkinPark...");
//将一个字符串元素加入栈的顶部
names.push("Binger...");
//将字符串元素添加到队列的头部
names.offerFirst("huhu...");
for (String string : names)
{
System.out.println(string);
}
//访问但不删除栈顶的元素
System.out.println(names.peekFirst());
//访问但不删除队列的最后一个元素
System.out.println(names.peekLast());
//将栈顶的元素弹出栈
System.out.println(names.poll());
//下面的输入已经将队列中的第一个元素给删除了
System.out.println(names);
//访问并删除队列的最后一个元素
System.out.println(names.pollLast());
System.out.println(names);
} }
- 各种线性表性能分析