## 队列 Queue
* 队列是一种特殊的线性表，只能在头尾两端操作
* 队尾（rear）: 只能从**队尾添加**元素，即 enQueue，入队
* 队头（front）: 只能从**队头移除**元素，即 deQueue，出队
* 队列遵循**先进先出**的原则，First In First Out，FIFO
## 实现队列
* 队列的内部实现可以使用**动态数组**或**双向链表**实现，但是优先使用**双向链表 LinkedList**，因为队列主要是操作**头尾**元素
* 官方 JDK 源码的 Queue 是一个接口，由 LinkedList 实现了该接口
```java
import java.util.LinkedList;
import java.util.List;
public class Queue {
private List list;
public Queue() {
list = new LinkedList<>();
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
// 入队，将元素添加至链表尾部
public void enQueue(E ele) {
list.add(ele);
}
// 出队，删除并返回链表的头节点元素
public E deQueue() {
return list.remove(0);
}
// 获取队头元素但不出队，获取链表的头节点元素
public E front() {
return list.get(0);
}
}
```
## 双端队列 Deque
* 双端队列是在队头和队尾都可以添加、删除元素的特殊队列
## 实现双端队列
```java
import java.util.LinkedList;
import java.util.List;
public class Deque {
private List list;
public Deque() {
list = new LinkedList<>();
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
// 从队头入队
public void enQueueFront(E ele) {
list.add(0,ele);
}
// 从队尾入队
public void enQueueRear(E ele) {
list.add(ele);
}
// 从队头出队
public E deQueueFront() {
return list.remove(0);
}
// 从队尾出队
public E deQueueRear() {
return list.remove(list.size()-1);
}
// 获取队头元素
public E front() {
return list.get(0);
}
// 获取队尾元素
public E rear() {
return list.get(list.size()-1);
}
}
```
## 参考
* [恋上数据结构与算法（第一季）](https://ke.qq.com/course/385223)
* [小码哥《恋上数据结构与算法》笔记（六）：队列](https://juejin.im/post/5dfb1fc4e51d4557f26e601b)
数据结构 | 队列Queue
