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

循环队列
循环队列是对顺序队列的改进，因为顺序队列不可避免的数据迁移操作，数据迁移操作会导致队列的性能下降，为了避免这个问题，将队列改造成循环的，当tail到达数组的最大下标时，重新指回数组下标为0的位置，这样就避免了数据迁移。先来看看循环队列的出队、入队操作：

文章插图

因为队列是循环队列，所以在进行入队、出队操作时，就不能像顺序队列那样对tail、head进行简单的加1操作，我们需要对tail、head加1后与数组的大小进行求余操作，来得出tail、head的值，这样才能进行循环操作。循环队列需要牺牲一个存储空间，对于一个存储空间为n的循环队列来说只能存放n-1为数据，因为如果不牺牲一个存储空间的话，当tail==head时，就有可能存在队空或者队满的情况。
循环队列的实现代码
/** * 环形队列,不需要数据迁移，提高性能 */public class CircularQueue { // 存放数据的数组 private String[] items; // 容器的大小 private int size = 0; // 第一个节点 private int head = 0; // 最后一个节点 private int tail = 0; // 构造函数 public CircularQueue(int size){ this.size = size; items = new String[size]; } /** * 入队操作 * @param data * @return */ public int enqueue(String data){ /** * 判断环形队列满了的条件，(tail+1)求余等于head */ if ((tail+1)%size == head) return -1; // 向队列中添加元素 items[tail] = data; // 因为是环形队列，所以下边是数组长度的余数 tail= (tail+1)%size; return 1; } /** * 出队操作 * @return */ public String dequeue(){ // 第一个元素和最后一个元素相等时，队列为空 if (head == tail) return null; String result = items[head]; // 因为是环形队列，所以下边是数组长度的余数 head = (head+1)% size ; return result; }}双端队列
双端队列是一种队头、队尾都可以进行入队、出队操作的队列，双端队列采用双向链表来实现，先来看一下双端队列的入队、出队操作：

文章插图

可以从动态图中看出，双端队列的每一端都是一个栈，都符合栈先进后出的特性，如果我们对双端队列进行禁止队头入队和队尾出队操作的限制，双端队列又变成了一个链式队列，双端队列是一种多功能的数据结构，我们可以使用它来提供队列和栈两种功能。
双端队列的实现代码
/** * 双端队列，使用双向链表实现 */public class DoubleEndsQueue { private static class Node { String item; Node next; Node prev; Node(Node prev, String element, Node next) { this.item = element; this.next = next; this.prev = prev; } } // 第一个节点 private Node first; // 最后一个节点 private Node last; /* * 在第一个节点前面入队 */ public void enqueueFirst(String e) { final Node f = first; final Node newNode = new Node(null, e, f); // 第一个节点指向新节点 first = newNode; if (f == null) // 最后一个节点也指向该节点 last = newNode; else // 当前节点的前节点指向新节点 f.prev = newNode; } /** * 在最后一个元素后面入队 * @param e */ public void enqueueLast(String e) { final Node l = last; final Node newNode = new Node(l, e, null); // 最后一个节点指向新节点 last = newNode; if (l == null) // 第一个节点指向新节点 first = newNode; else // 当前节点的下节点指向新节点 l.next = newNode; } /** * 从第一个节点出队 * @return */ public String dequeueFirst() { if (first == null) return null; final Node f = first; String element = f.item; Node next = f.next; f.item = null; f.next = null; // 第一个节点指向当先节点的next节点 first = next; if (next == null) // 说明队列为空 last = null; else next.prev = null; return element; } /** * 从最后节点出队 * @return */ public String dequeueLast() { final Node l = last; if (last == null) return null; String element = l.item; Node prev = l.prev; l.item = null; l.prev = null; last = prev; if (prev == null) first = null; else prev.next = null; return element; }// 输出队列全部内容 public void displayAll() { while (first !=null){ System.out.print(first.item+" "); first = first.next; } System.out.println("==============="); }}优先队列
优先队列为一种不必遵循队列先进先出(FIFO)特性的特殊队列，优先队列跟普通队列一样都只有一个队头和一个队尾并且也是从队头出队，队尾入队，不过在优先队列中，每次入队时，都会按照入队数据项的关键值进行排序(从大到小、从小到大)，这样保证了关键字最小的或者最大的项始终在队头，出队的时候优先级最高的就最先出队，这个就像我们医院就医一样，急救的病人要比普通的病人先就诊。一起来看看优先队列的出队、入队操作：