数据结构与算法-基础（五）队列（Qeque）
队列是一种线性表，添加或者删除操作只能在头尾两端进行，并且限制只能从队尾添加元素，即入队（enQueue） ，也只能从队头移除元素，即出队（deQueue） 。所以队列的特点可以总结为先进先出 - First In First Out (FIFO) 。
根据队列的定义设计接口如下表：
| 函数 | 释义 |
|---|---|
int size() | 元素数量 |
boolean isEmpty() | 是否为空 |
void clear() | 清空 |
void enQueue(E element) | 入队 |
E dequeue() | 出队 |
E front() | 获取队列的头元素 |
E 是泛型类型
实现
队列可以通过动态数组或链表来实现，因为队列只能在头尾操作这个性质，所以就可以封装动态数组或者链表，暴露出操作头部或者尾部的接口 API。建议优先选择双向链表，有利于操作头部或者尾部。
先创建一个 Queue 的类结构，在结构中创建一个私有的 list 存放数据：
public class Queue<E> {
private List<E> list = new LinkList<>();
}复制代码队列的元素数量可以直接访问 list 的 size() 方法：
int size() {
return list.size();
}复制代码判断队列是否有元素，也可以直接访问 list 的 isEmpty() 方法：
boolean isEmpty() {
return list.isEmpty();
}复制代码清空队列同样可以直接使用 list 的 clear() 方法：
void clear() {
list.clear();
}复制代码接下来，开始实现队列的重要三个方法。
首先是入队方法，因为入队是从队尾添加元素，所以就相当于给 list 添加元素：
void enQueue(E element) {
list.add(element);
}复制代码出队操作，是从队头移除元素，所以就相当于给 list 删除索引是 0 的元素：
E deQueue() {
return list.remove(0);
}复制代码获取队头元素也是相当于获取到 list 索引为 0 的元素：
E front() {
return list.get(0);
}复制代码到这里，就已经实现完队列的全部接口。现在的队列是只能从队尾入队，从队头出队。那么不管队头或者队尾，都可以操作入队和入队呢？双端队列就解决了这个问题。
双端队列（Deque）
双端队列是可以在队列的两头都可以操作入队和出队。所以增加了相关的接口
| 函数 | 释义 |
|---|---|
void enQueueRear(E element) | 从队尾入队 |
E deQueueFront() | 从队头出队 |
void enQueueFront(E element) | 从队头出队 |
E deQueueRear() | 从队尾出队 |
E front() | 获取队列的头元素 |
E rear() | 获取队列的尾元素 |
看表中的方法，队尾入队、队头出队和获取队列的头元素在上面已经实现了。接下来就只需要实现剩下的三个方法。实现的方法也是非常简单。
首先实现从队头入队，也就是添加元素到 list 中索引为 0 的位置：
void enQueueFront(E element) {
list.add(0, element);
}复制代码接下来实现从队尾出队，就是移除 list 的最后一个位置的元素：
E deQueueRear() {
return list.remove(list.size() - 1);
}复制代码最后实现获取队列尾部元素，也就是获取 list 的最后一个位置的元素：
E rear() {
return list.get(list.size() -1);
}复制代码截止到这里，就已经全部实现完队列和双端队列了。通过封装动态数组或者链表实现队列，是一个非常容易实现的方式。若对动态数组或者链表的结构感兴趣，可以看《数据结构与算法-基础》系列的前几期的文章。
\
作者：我为双鱼狂
链接：https://juejin.cn/post/7027061983149031454