看完这篇你还不知道这些队列，我这些图白作了 _队列

队列（queue）是一种采用先进先出(FIFO)策略的抽象数据结构，即最先进队列的数据元素，同样要最先出队列。队列跟我们排队买票一样，先来排队的肯定先买票，后来排队的的后买到票。队列如下图所示：

文章插图

队列有两个重要的概念，一个叫队头，一个叫队尾，队头指向的是第一个元素，而队尾指向的是最后一个元素。队列跟栈一样也是访问受限制的，所以队列也只有两个主要的操作：入队(enqueue)操作和出队(dequeue)操作。入队操作就是将一个元素添加到队尾，出队操作就是从队头取出一个元素。
队列的底层实现可以用数组和链表，基于数组实现的队列叫作顺序队列，基于链表实现的队列叫作链式队列，下面我们分别用数组和链表来简单的实现这两种队列。
【看完这篇你还不知道这些队列，我这些图白作了】基于数组的队列
不管使用那种方式来实现队列，都需要定义两个指针分别指向队头和队尾，本文中我们用head指向队头，tail指向队尾，后面的示例中这将默认使用这个，有特殊的地方我会进行说明，先来看看顺序队列的入队、出队操作。

文章插图

图中可以看出，入队时，队尾往后移动，队头保持不变，出队是队头往后移动，队尾保持不变。入队、出队操作的逻辑都比较简单，可能你有疑问的地方是：出队时为什么队头要往后移动而不是一直指向数组下标为0的位置？为什么呢？如果我们保持队头一直指向数组下标为0的位置，那每次出队操作后，后面的数据都需要往前挪一位，换句话说每次出队操作都需要进行数据迁移，而数据迁移的代价比较大，每次数据迁移的时间复杂度为O(n)，这样会极大的影响队列的使用性能。如果我们出队时，队头往后移动一位，这样我们就避免每次出队都进行数据迁移，我们只需要在只有在tail等于数组大小且head不等于0时，进行一次数据迁移，将已经出队留下的空间继续供入队时使用。下图是数据迁移的过程：

文章插图

数据迁移时，从head位置开始的数据都需要往前移动head位，这样就把出队后的空间腾出来，供后续入队操作使用。
基于数组的队列实现代码：
/** * 基于数组的队列 */public class ArrayQueue { // 存放数据的数组 private String[] items; // 容器的大小 private int size = 0; // 第一个节点 private int head = 0; // 最后一个节点 private int tail = 0; // 构造函数 public ArrayQueue(int size){ this.size = size; items = new String[size]; } /** * 入队操作 * @param data * @return */ public int enqueue(String data){ // 如果最后一个节点等于容器大小，说明队列满了 /** * 判断队列满了的条件，tail = size,head = 0, */ if (tail == size && head == 0) return -1; /** * 如果tail = size，但是head != 0,说明前有数据删除，队列未满，需要数据迁移 */ if (tail == size){ // head 后面的数据都需要往前迁移 head 位 for (int i= head;i< size;i++){ items[i-head] = items[i]; } // 将最后一个元素迁移 head 位 tail -=head; // 第一个元素指向 0 head = 0; } // 向队列中添加元素 items[tail] = data; tail++; return 1; } /** * 出队操作 * @return */ public String dequeue(){ // 第一个元素和最后一个元素相等时，队列为空 if (head == tail) return null; String result = items[head]; // 第一个元素后移一次，这样做的好处是在出队时不需要数据迁移 head ++ ; return result; }}链式队列
链式队列实现起来相对顺序队列来说要简单很多，我们先来看看链式队列的入队、出队操作：

文章插图

从图中可以看出链式队列入队操作是将tail的next指向新增的节点，然后将tail指向新增的节点，出队操作时，将head节点指向head.next节点。链式队列与顺序队列比起来不需要进行数据的迁移，但是链式队列增加了存储成本。
基于链表的队列实现代码
/** * 基于链表的队列 */public class LinkQueue { // 指向队首 private Node head; // 指向队尾 private Node tail; /** * 入队操作 * @param data * @return */ public int enqueue(String data){ Node node = new Node(data,null); // 判断队列中是否有元素 if (tail == null) { tail = node; head = node; }else { tail.next = node; tail = node; } return 1; } /** * 出队操作 * @return */ public String dequeue(){ if (head==null) return null; String data = https://www.isolves.com/it/cxkf/bk/2019-09-02/head.data; head = head.next; // 取出元素后，头指针为空，说明队列中没有元素，tail也需要制为空 if (head == null){ tail = null; } return data; } class Node{ private String data; private Node next; public Node(String data,Node node){ this.data = data; next = node; } }}