1.队列(Queue)
1.1 关于队列
队列 ：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表， 队列具有先进先出 FIFO(First In First Out)的操作特性（队列是个接口）；
入队列：进行插入操作的一端称为队尾（ Tail/Rear ）
出队列：进行删除操作的一端称为队头（ Head/Front ）
下图通过图解来了解关于队列入队和出队的操作；
1.2队列与链表
在Java中，Queue是个接口，底层是通过链表实现的 ，具体情况如下图所示；
1.3 队列的基本使用方法
下图是使用队列时具体的基本方法；
注意：Queue是个接口，在实例化时该接口时，必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
2.用链表实现队列
我们本次使用的是双向链表；
2.1创建队列
public class MyLLQueue {
//创建静态内部类,实例对象作为队列中的节点
public static class Node {
int value;
Node next;
Node prev;
public Node(int value) {
this.value = value;
}
}
public Node front;//双向链表的头结点
public Node rear;//双向链表的尾结点
public int usedSize = 0;//记录队列中节点个数
}2.2入队列
思路：
1、创建一个要添加的值为value的节点node。
2.1判断当前队列是否为空？即链表头结点front是否为null,若为null，则该node既是front（队头）和也是rear（队尾）。
2.2若队头不为null，则将该节点的引用给当前队列的队尾的next，至此队尾就是我们新添加的节点；
4、队列里面的数据容量加一。
代码如下：
public boolean offer(int vale) {
Node node = new Node(vale);
if (isEmpty()) {
front = node;
rear = node;
} else {
rear.next = node;
node.prev = rear;
}
rear = node;
usedSize++;
return true;
}2.3 判断队列是否为空
private boolean isEmpty() {
return usedSize == 0;
}2.4出队列
1、队列为空，则直接返回队列为空的自定义异常。
public class EmptyException extends RuntimeException{
public EmptyException(String msg) {
super(msg);
}
}2、队列此时不为空。
2.1 此时队列中只有一个元素；（即队头的next域里存放的是空指针null），出队操作之后队列就为空，故此让队头和队尾都指向空指针；
2.2 此时队列中有多个元素：让队头的后域指向下一个节点，队头的前域指向空指针；
3、队列里面的数据容量减一；
//出队列---将双向链表第一个节点删除掉,并返回第一个删除节点的值
public int poll() {
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
if (isEmpty()) {
//队列为空,抛异常,提示不能对空队列进行出队操作
throw new EmptyException("队列为空,操作错误!!");
}
//用ret记录返回的队头元素的数据
int ret = front.value;
if (front.next == null) {
//当前链表只有一个节点
front = null;
rear = null;
usedSize--;
return ret;
}
front = front.next;
front.prev = null;
usedSize--;
return ret;
}2.5获取队头元素
思路类似于2,4部分
//获取队头元素的值,不出队列
int peek(){
if (isEmpty()) {
//队列为空,抛异常,提示不能对空队列进行出队操作
throw new EmptyException("队列为空,操作错误!!");
}
return front.value;
}2.6 双向链表（linkedlist）实现队列的完整代码
public class MyLLQueue {
//创建静态内部类,实例对象作为队列中的节点
public static class Node {
int value;
Node next;
Node prev;
public Node(int value) {
this.value = value;
}
}
public Node front;//双向链表的头结点
public Node rear;//双向链表的尾结点
public int usedSize = 0;//记录队列中节点个数
//为了体现队列的先进先出特点,规定从尾入,从头出(也可以头进尾出)
//插入操作,原理为双链表的尾插法
public boolean offer(int vale) {
Node node = new Node(vale);
if (isEmpty()) {
front = node;
rear = node;
} else {
rear.next = node;
node.prev = rear;
}
rear = node;
usedSize++;
return true;
}
private boolean isEmpty() {
return usedSize == 0;
}
//出队列---将双向链表第一个节点删除掉,并返回第一个删除节点的值
public int poll() {
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
if (isEmpty()) {
//队列为空,抛异常,提示不能对空队列进行出队操作
throw new EmptyException("队列为空,操作错误!!");
}
//用ret记录返回的队头元素的数据
int ret = front.value;
if (front.next == null) {
//当前链表只有一个节点
front = null;
rear = null;
usedSize--;
return ret;
}
front = front.next;
front.prev = null;
usedSize--;
return ret;
}
//获取队头元素的值,不出队列
int peek(){
if (isEmpty()) {
//队列为空,抛异常,提示不能对空队列进行出队操作
throw new EmptyException("队列为空,操作错误!!");
}
return front.value;
}
//获取队列的长度
public int size(){
return usedSize;
}
public static void main(String[] args) {
MyLLQueue myLLQueue = new MyLLQueue();
System.out.println(myLLQueue.isEmpty());
myLLQueue.offer(1);
myLLQueue.offer(2);
myLLQueue.offer(3);
System.out.println(myLLQueue.size());
System.out.println(myLLQueue.peek());
System.out.println(myLLQueue.poll());
System.out.println(myLLQueue.peek());
System.out.println(myLLQueue.size());
}
}
测试结果如下：
3. 双端队列 (Deque)
双端队列（deque）：是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，与queue类似在使用时必须创建LinkedList的对象，以下是详细图解：
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口，代码如下：
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现ps：本次内容就到这里，如果喜欢的话就请一键三连哦！！！
