GitHub源码分享
我的项目主页：https://github.com/gozhuyinglong/blog-demos
本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures
1. 队列（queue）
队列和栈一样，也是一个操作受限制的线性表。不同的是队列的插入在一端进行，咱们称为队尾（rear）；而删除（取出）在另一端进行，咱们称为队头（front）。
队列是一个先进先出（FIFO - First In First Out）的有序列表，其操作只有两种：
- 入队（enqueue）：向队尾增加一个元素
- 出队（dequeue）：从队头删除（取出）一个元素
2. 队列的数组实现
如同栈一样，对队列的每一种操作，链表实现或数组实现都给出疾速的运行工夫。队列的链表实现是简略而间接的，咱们就不过介绍了。上面咱们探讨如何应用数组实现一个队列。
先看下图，咱们须要申明一个数组，并保护两个指针：
- head指针：指向待入列的元素地位
- tail指针：指向待入列的存储地位
能够看出，达到队尾后无奈再增加新的元素，而后后面已入列的地位还空着。
下面问题咱们能够将数组进行首尾相连，造成一个环形数组，即指针达到数组尾部后，从新指向数组头部，如下图所示。
这里须要留神几点：
- 判断空队列能够通过head == tail
- 判断队列满不能再通过head与tail重合，而是须要空出一个存储空间来，即：head == tail + 1。而环形数组须要取模运算，所以正确判断队列满：head == (tail + 1) % capacity。
- 数组实在容量应为：指定容量 + 1
3. 代码实现
上面代码是应用环形数组实现的队列，所以又叫做环形队列。
其容量为：指定容量 + 1，head 与t ail 初始值为0。队列存储元素应用了泛型，所以能够操作你想用的数据类型。上面看具体实现：
public class ArrayQueueDemo { public static void main(String[] args) { ArrayQueue<Integer> queue = new ArrayQueue<>(5); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("出队： --> " + queue.get()); System.out.println("入队：1 --> " + queue.add(1)); System.out.println("入队：2 --> " + queue.add(2)); System.out.println("入队：3 --> " + queue.add(3)); System.out.println("入队：4 --> " + queue.add(4)); System.out.println("入队：5 --> " + queue.add(5)); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("出队： --> " + queue.get()); System.out.println("入队：6 --> " + queue.add(6)); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("入队：7 --> " + queue.add(7)); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("入队：8 --> " + queue.add(8)); System.out.println("入队：9 --> " + queue.add(9)); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.println("出队： --> " + queue.get()); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); System.out.println("入队：10 --> " + queue.add(10)); System.out.printf("头指针: %s\t尾指针: %s\t队列大小: %s\t容量: %s\n", queue.head, queue.tail, queue.size(), queue.capacity); } private static class ArrayQueue<T> { private final T[] queue; // 存储队列数据元素 private final int capacity; // 容量 private int head = 0; // 头部指针，指向队头元素 private int tail = 0; // 尾部指针，指向下一个待入队元素的存储地位 public ArrayQueue(int capacity) { this.capacity = capacity + 1; // 环形队列须要空出一个地位，来满足队列满时head与tail不重合 this.queue = (T[]) new Object[this.capacity]; } /** * 向队列增加一个元素 * * @param data * @return */ public boolean add(T data) { // 队列满，增加失败 if (isFull()) { return false; } // tail指向下一个待入队元素的存储地位，所以先赋值再让指针加1 queue[tail] = data; // 环形数组须要取模运算 tail = (tail + 1) % capacity; return true; } /** * 从队列中获取一个元素 * * @return */ public T get() { if (isEmpty()) { return null; } // head指向头元素地位，所以先取出再让指针加1 T data = queue[head]; // 环形数组须要取模运算 head = (head + 1) % capacity; return data; } /** * 以后队列大小 * * @return */ public int size() { int size = tail - head; if (size < 0) { size += capacity; } return size; } /** * 队列是否为空：当tail与head指向同一地位时，示意队列为空 * * @return */ public boolean isEmpty() { return tail == head; } /** * 队列是否已满：因为预留了一个地位，所以tail须要加1；环形队列须要取模运算 * * @return */ public boolean isFull() { return head == (tail + 1) % capacity; } }}输入后果：
头指针: 0 尾指针: 0 队列大小: 0 容量: 6出队： --> null入队：1 --> true入队：2 --> true入队：3 --> true入队：4 --> true入队：5 --> true头指针: 0 尾指针: 5 队列大小: 5 容量: 6出队： --> 1入队：6 --> true头指针: 1 尾指针: 0 队列大小: 5 容量: 6入队：7 --> false出队： --> 2出队： --> 3头指针: 3 尾指针: 0 队列大小: 3 容量: 6入队：8 --> true入队：9 --> true头指针: 3 尾指针: 2 队列大小: 5 容量: 6出队： --> 4出队： --> 5出队： --> 6出队： --> 8出队： --> 9头指针: 2 尾指针: 2 队列大小: 0 容量: 6入队：10 --> true头指针: 2 尾指针: 3 队列大小: 1 容量: 6