共计 3788 个字符，预计需要花费 10 分钟才能阅读完成。
本文已收录至我的 Github《算法图解》系列：https://github.com/vipstone/algorithm
后面咱们介绍了栈（Stack），队列和栈是比拟像的一种数据结构。咱们能够设想有很多辆汽车正在通过单行道的隧道，所有车辆不能插队、不能掉头，先进来的车也先进来，咱们能够把这种特色的数据结构称之为队列。
队列也属于逻辑构造，所谓的物理构造是指能够将数据存储在物理空间中，比方数组和链表都属于物理数据结构；而逻辑构造则是用于形容数据间的逻辑关系的，它能够由多种不同的物理构造来实现，比方队列和栈都属于逻辑构造。
队列个性
队列中的元素必须是先进先出（First In First Out，FIFO）的，它有两个重要的办法：入队（enqueue）和出队（dequeue）。队列的入口端叫队尾（rear），进口端叫队头（front），如下图所示：
手撸队列
学习了队列的基本知识之后，接下来咱们将应用代码来实现一个队列。
首先咱们先应用数组来实现一个队列，它的构造如下图所示：
1. 自定义队列—数组
public class MyQueue<E> {private Object[] queue; // 存储容器
private int head; // 头部指针
private int tail; // 尾部指针
private int size; // 队列理论存储长度
private int maxSize; // 最大容量
public MyQueue() {
// 无参构造函数，设置默认参数
this.maxSize = 10;
this.head = 0;
this.tail = -1;
this.size = 0;
this.queue = new Object[this.maxSize];
}
public MyQueue(int initSize) {
// 有参构造函数，设置参数
this.maxSize = initSize;
this.head = 0;
this.tail = -1;
this.size = 0;
this.queue = new Object[this.maxSize];
}
/**
* 查问队头元素
*/
public E peek() throws Exception {if (size == 0) {throw new Exception("队列中暂无数据");
}
return (E) this.queue[this.head];
}
/**
* 入列
*/
public boolean offer(E e) throws Exception {if (tail >= (maxSize - 1)) {throw new Exception("增加失败，队列已满");
}
this.queue[++tail] = e;
size++;
return true;
}
/**
* 出列
*/
public E poll() throws Exception {if (size == 0) {throw new Exception("删除失败，队列为空");
}
size--;
return (E) this.queue[head++];
}
/**
* 代码测试
*/
public static void main(String[] args) throws Exception {MyQueue queue = new MyQueue();
queue.offer("Hello");
queue.offer("Java");
System.out.println(queue.peek());
queue.poll();
System.out.println(queue.poll());
}
}以上代码的执行后果如下：
Hello
Java
2. 自定义队列—链表
用链表实现队列的数据结构如下图所示：
实现代码如下：
public class QueueByLinked {
/**
* 申明链表节点
*/
static class Node<E> {
E item; // 以后的值
Node<E> next; // 下一个节点
Node(E e) {this.item = e;}
}
private Node firstNode; // 队头元素
private Node lastNode; // 队尾元素
private int size; // 队列理论存储数量
private int maxSize; // 队列最大容量
public QueueByLinked(int maxSize) {if (maxSize <= 0) throw new RuntimeException("队列最大容量不能为空");
// 默认初始化函数
firstNode = lastNode = new Node(null);
this.size = 0;
this.maxSize = maxSize;
}
/**
* 判断队列是否为空
*/
public boolean isEmpty() {return size == 0;}
/**
* 入列
*/
public void offer(Object e) {
// 最大值效验
if (maxSize <= size) throw new RuntimeException("队列已满");
Node node = new Node(e);
lastNode = lastNode.next = node; // 设置最初一个节点和倒数第二个节点的 next
size++; // 队列数量 +1
}
/**
* 出列
*/
public Node poll() {if (isEmpty()) throw new RuntimeException("队列为空");
size--; // 队列数量 -1
return firstNode = firstNode.next; // 设置并返回队头元素（第一个节点是 null，以后元素则为 Node.next）}
/**
* 查问队头元素
*/
public Node peek() {if (isEmpty()) throw new RuntimeException("队列为空");
return firstNode.next; // 返回队头元素（第一个节点是 null，以后元素则为 Node.next）}
/**
* 代码测试
*/
public static void main(String[] args) {QueueByLinked queue = new QueueByLinked(10);
queue.offer("Hello");
queue.offer("JDK");
queue.offer("Java");
System.out.println(queue.poll().item);
System.out.println(queue.poll().item);
System.out.println(queue.poll().item);
}
}以上代码的执行后果如下：
Hello
JDK
Java
3. 扩大：应用 List 实现自定义队列
除了以上两种形式之外，咱们还能够应用 Java 本身的数据结构来实现队列，比方 List，咱们这里提供一个实现的思路（但并不倡议在理论工作中应用），实现代码如下：
import java.util.ArrayList;
import java.util.List;
/**
* 自定义队列（List 形式）*/
public class QueueByList<E> {
private List value; // 队列存储容器
public QueueByList() {
// 初始化
value = new ArrayList();}
/**
* 判断队列是否为空
*/
public boolean isEmpty() {return value.size() == 0;
}
/**
* 入列
*/
public void offer(Object e) {value.add(e);
}
/**
* 出列
*/
public E poll() {if (isEmpty()) throw new RuntimeException("队列为空");
E item = (E) value.get(0);
value.remove(0);
return item;
}
/**
* 查问队头元素
*/
public E peek() {if (isEmpty()) throw new RuntimeException("队列为空");
return (E) value.get(0);
}
/**
* 代码测试
*/
public static void main(String[] args) {QueueByList queue = new QueueByList();
queue.offer("Hello");
queue.offer("JDK");
queue.offer("Java");
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}以上代码的执行后果如下：
Hello
JDK
Java
队列应用场景
队列的常见应用场景有：
- 存储多线程中期待排队执行的工作；
- 存储多线程偏心锁中期待执行工作的线程；
- 常见消息中间件的工作队列等。
总结
通过以上三种队列的实现形式咱们能够看出，任意容器都是能够用来实现队列（Queue）的，只有保障队列的元素先进先出（FIFO），并且在实现类中须要蕴含队列的四个外围办法：入列、出列、查问队列是否为空、返回队头元素等，就能够称为实现了一个自定义的队列。
最初，给大家留一个问题：队列的类型都有哪些？欢送评论区留言，我会在下篇文章中给出答案。欢送关注我，每天和你一起提高一点点~
文末福利：搜寻公众号「Java 中文社群」发送“面试”，支付最新的面试材料。
