队列是具有一定操作约束的线性表，对比堆栈的插入删除只在一端进行，队列是在一端插入（入队），在另一端删除（出队），也就是我们经常说的先进先出。
队列示意图
除了利用数组实现队列外，我们还可以通过一个单链表，来实现队列的链式存储。那么我们的队头变量front和队尾变量rear应该指向链表的哪一头呢。在单链表中链表的头可以方便的进行插入和删除的操作，而链表的尾由于找不到前一个结点的位置，因此只能做插入操作。队列遵循先进先出，也就是队头来进行删除操作，所以我们选择front指向链表的头，rear来指向链表的尾。
具体代码实现如下：
public class Node {
private Object date; //每个结点的数据
private Node next; //每个结点指向的下一个结点
public Node() {
this.date = null;
this.next = null;
}
public Node(Object date) {
this.date = date;
this.next = null;
}
public Object getDate() {
return date;
}
public Node getNext() {
return next;
}
public void setDate(Object date) {
this.date = date;
}
public void setNext(Node next) {
this.next = next;
}
}
public class MyLinkQueue {
private Node front; //队头
private Node rear; //队尾
private int size; //记录队列数量
//初始化
public MyLinkQueue() {
this.front = null;
this.rear = null;
this.size = 0;
}
//入队
public void AddQ(Object data) {
Node node = new Node(data);//有新元素入栈，创建一个相应的结点对象，申请空间
if(size == 0) { //如果是添加的第一个队列，将其设置为头结点
front = node;
}else { //否则将尾结点的下一个结点更新为新结点
rear.setNext(node);
}
rear = node; //更新rear
size += 1; //更新size
System.out.println("入队元素为" + node.getDate());
}
public void DeleteQ() {
if(size == 0) {
System.out.println("这是一个空队列");
rear = null; //更新rear
}else {
Object data = front.getDate();
front = front.getNext(); //更新头结点
System.out.println("出队元素为" + data);
size -= 1; //更新size
}
}
}
public static void main(String[] args) {
MyLinkQueue myQueue = new MyLinkQueue();
myQueue.AddQ("第1个");
myQueue.AddQ("第2个");
myQueue.AddQ("第3个");
myQueue.DeleteQ();
myQueue.DeleteQ();
myQueue.DeleteQ();
myQueue.DeleteQ();
myQueue.DeleteQ();
myQueue.DeleteQ();
}
/*
输出结果为：
入队元素为第1个
入队元素为第2个
入队元素为第3个
出队元素为第1个
出队元素为第2个
出队元素为第3个
这是一个空队列
这是一个空队列
这是一个空队列
*/
