队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。因为队列只允许在一段插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
顺序队列中的溢出现象：
（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2）"真上溢"现象：当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3）"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
图from baike队列的常用操作：
（1）初始化队列： 初始条件：队列 不存在。操作结果：构造了一个空队或者带有一个对头的的队列；
（2）入队操作：初始条件： 队列存在。操作结果： 对已存在的队列，插入一个元素x 到队尾，队发生变化；
（3）出队操作：初始条件: 队列 存在且非空，操作结果： 删除队首元素，并返回其值，队发生变化；
（4）读队头元素：初始条件: 队列 存在且非空，操作结果： 读队头元素，并返回其值，队不变；
（5）判队空操作：初始条件： 队列 存在，操作结果： 若队列为空则返回为true，否则返回为false；
（6）清空队列操作：初始条件：队列存在，操作结果：清空队列，队列的长度为0；
（7）计算队列长度：初始条件：队列存在，操作结果：计算并返回队列长度。
队列常用操作算法的时间和空间复杂度均为O(1)；
实现代码：
package com.wxisme.linkqueue;
import java.util.Scanner;
/**
* 链队列的实现
* @time 2015/8/16 0:16
* @author wxisme
*
*/
public class LinkQueue<T> {
private class Node {
private T data;
private Node next;
public Node() {}
public Node(T data) {
this.data = data;
}
}
private Node front; /*队头*/
private Node rear; /*队尾*/
private int size; /*长度*/
public LinkQueue() {
front = null;
rear = null;
}
public LinkQueue(T data) {
front = new Node(data);
rear = front;
size ++;
}
//队列的长度
public int size() {
return size;
}
//从队尾入队
public void add(T data) {
if(front == null) {
front = new Node(data);
rear = front;
size ++;
}
else {
Node node = new Node(data);
rear.next = node;
rear = node;
size ++;
}
}
//从队头出队
public T remove() {
T t = null;
if(front != null) {
t = front.data;
Node node = front;
front = front.next;
node.next = null;//释放对头元素的引用，等待垃圾回收。
size --;
}
else {
try {
throw new Exception("队列已经为空，不能移除元素！");
} catch (Exception e) {
e.printStackTrace();
}
}
return t;
}
//读取对头元素
public T peek() {
if(front == null) {
try {
throw new Exception("队列为空，不能读取对头元素！");
} catch (Exception e) {
e.printStackTrace();
}
return null;
}
else {
return front.data;
}
}
//清空队列
public void clear() {
front = rear = null;
size = 0;
}
//判断是否为空
public boolean isEmpty() {
return size==0;
}
public String toString() {
if(isEmpty()) {
return "[]";
}
else {
StringBuilder str = new StringBuilder("[" + front.data);
for(Node node=front.next; node!=null; node=node.next) {
str.append(","+node.data);
}
str.append("]");
return str.toString();
}
}
/**
* 测试代码
* @param args
*/
public static void main(String[] args) {
LinkQueue<Character> queue = new LinkQueue<Character>();
Scanner scan = new Scanner(System.in);
for(int i=0; i<5; i++) {
queue.add((char)('a'+i));
}
System.out.println(queue);
queue.remove();
System.out.println(queue);
System.out.println("队列是否为空：" + queue.isEmpty());
System.out.println("队列的长度：" + queue.size());
System.out.println("队头元素为：" + queue.peek());
System.out.println("清空队列");
queue.clear();
System.out.println("队列是否为空：" + queue.isEmpty());
}
}
测试结果：
[a,b,c,d,e]
[b,c,d,e]
队列是否为空：false
队列的长度：4
队头元素为：b
清空队列
队列是否为空：true