概念解释

队列是一种对存取数据操作都有严格要求的数据结构，只能从尾部进入数据，从头部取出数据，遵循“先进先出”FIFO原则
队列的实现有两种方式，基于数组的实现叫做“顺序队列”，基于链表的实现叫做“链队列”。

顺序队列：<基于数组的实现>

需要两个指针分别标记“队头”和“队尾”，在存入数据时，队头指针保持不变，队尾指针向后移动。实质上队尾指针标记下一次存放数据要放置的位置。在取出数据时，队尾指针保持不变，队头指针每取出一个数据都向后挪动。
也就是说，队头指针指向下一次取出数据的位置，队尾指针指向下一次存入数据要存放的位置。
当队列内的数据都被取出时，队头和队尾的指针都指向某一个相同位置。

  1. public class ArrayQueue {
  2.     //盛放队列数据的数组
  3.     int[] arr;
  4.     //头指针
  5.     int head;
  6.     //尾指针
  7.     int tair;
  8.     //最大容量
  9.     int maxCapacity;
  11.     public ArrayQueue(int  maxCapacity){
  12.         arr = new int[maxCapacity];
  13.         maxCapacity = maxCapacity;
  14.         this.head = 0;
  15.         this.tair = 0;
  16.     }
  18.     public boolean isFull(){
  19.         return tair == maxCapacity;
  20.     }
  21.     public void add(int n){
  22.         if (!isFull()){
  23.             arr[tair] = n;
  24.             tair++;
  25.         }
  26.     }
  27.     public int get(){
  28.         if (isEmpty()){return -1;}
  29.         int result = arr[head];
  30.         head++;
  31.         return result;
  32.     }
  33.     //尾部指针为空，当头部指针指向尾部指针即指向空时，则队列为空
  34.     public boolean isEmpty(){
  35.         return head == tair;
  36.     }
  37. }

链队列：<基于链表的实现>

JAVA中提供的LinkedList中针对队列数据结构有具体的实现方法
不过注意区别具体方法的实现效果。
添加方法：
add方法添加元素失败时（达到队列最长长度）会抛出异常，offer方法会返回false
取出方法：
取出方法并保留元素：在队列为空时，peek方法会返回null值；element方法取出元素会抛出异常。
取出数据并不保留元素：在队列为空时，取出方法poll会返回null值，remove方法会抛出异常。

  1. Queue<Integer> queue = new LinkedList<>();
  2.         //添加元素
  3.         boolean offer = queue.offer(1);
  4.         boolean add = queue.add(2);
  5.         //当队列满时，add方法会抛出异常，offer方法会返回false；
  7.         //取出元素，并保留队列里的元素
  8.         Integer peek = queue.peek();
  9.         Integer element = queue.element();
  10.         //当队列为空时，element会抛出异常，peek会返回null；
  12.         //取出元素，不保留队列里的元素
  13.         Integer poll = queue.poll();
  14.         Integer remove = queue.remove();
  15.         //当队列为空时，remove方法会抛出异常，poll会返回null；

双端队列：deque double ended queue

双端队列，从头尾部都可以增加或者删除元素
【队列·双端队列】.jpg

特别队列：

优先级队列：PriorityQueue

元素携带了相关的优先级，优先级更高的元素排在队头
priorityQueue，提供了comparable接口，元素可以实现其方法，改变在队列中的顺序。

阻塞队列：BlockingQueue

当队列满时，等待队列有空余位置再存数据；当队列空时，等待队列中增加了数据再取出。
put( ) 和 take( ) 方法实现了阻塞逻辑。
另外阻塞队列还分为两种情况，一种是无限期地等待，一种是能设定等待时间。

延迟队列：DelayQueue

在指定时间内获取有效元素，头部元素是最接近失效时间的。给定一个接口设置延迟时间，元素会按照有效时间进行排序。

相关算法

一、求取队列中的最大值

定义一个队列，实现函数max_value，可以取出队列中的最大值。要求函数max_value，push_back和pop_front的均摊时间复杂度为O(1)。若队列为空，要求max_value，和pop_front返回值为 -1；
【分析】在进行增删操作时，队列里的最大值都可能发生改变。当我们增加元素时，要比较该元素与队列里的最大值之间关系，更大的值更新为最大值。当我们删除元素时，也要比较删除元素与最大值之间的关系，如果删除元素不是最大值那么不需要变动，如果删除元素是最大值，最大值要更新为剩余元素的最大值。
【实现】使用额外的队列来记录最大值发生的变化。max队列，队头元素是目前队列中的最大值，而其他元素是未来可能成为最大值的候选值
新增元素ele时， ele > max时， 取队列中队尾元素比较，如果满足，进行覆盖并循环比较，直到把所有比它小的值都覆盖为止。ele < max 时，将其存到max队列中。
【队列·求取队列里的最大值】.jpg

  1. public class MaxQueue {
  3.     LinkedList<Integer> queue;
  4.     LinkedList<Integer> max;
  6.     public MaxQueue(){
  7.         queue = new LinkedList<Integer>();
  8.         max = new LinkedList<Integer>();
  9.     }
  11.     public int maxValue(){
  12.         if (max.isEmpty()){return -1;}
  13.         return max.peekFirst();
  14.     }
  16.     public void push_back(int value){
  17.         queue.offer(value);
  18.         while (!max.isEmpty() && max.peekLast() < value){
  19.             max.pollLast();
  20.         }
  21.         max.add(value);
  22.     }
  24.     public int pop_front(){
  25.         if (!max.isEmpty() && queue.peekFirst().equals(max.peekFirst())){
  26.             max.pollFirst();
  27.         }
  28.         if (queue.isEmpty()){return -1;}
  29.         return queue.poll();
  30.     }
  31. }

二、滑动窗口的最大值

【描述】
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值
———————- ——-
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
【分析】
数组的长度为 n，窗口的大小为k，那么可形成的窗口数就为 n-k+1。通过队列来记录最大值
窗口未形成的阶段：遍历数组，更新窗口队列；
窗口已形成的阶段：每次窗口移动都是在头部移除元素，尾部增加元素。
在窗口移动过程中，记录其最大值的变化（最大值一直出现在第一位）；让队列中新添加的元素与max队列里的最大值作比较，如果已存在的更小，那么覆盖。如果已存在的更大，那么新添加的元素缀在已存在元素之后
【队列·滑动窗口内的最大值】.jpg

  1. public class SlideWindow {
  3.     public int[] maxSlidingWindow(int[] nums,int k){
  4.         //记录每个窗口的最大值，n-k+1为形成的窗口个数
  5.         int[] result = new int[nums.length - k + 1];
  7.         //使用队列记录最大值的候选值
  8.         Deque<Integer> deque = new ArrayDeque<>();
  10.         //窗口未形成阶段
  11.         for (int i = 0; i < k; i++) {
  12.             while (!deque.isEmpty() && deque.peekLast() < nums[i]){
  13.                 deque.pollLast();
  14.             }
  15.             deque.offerLast(nums[i]);
  16.         }
  17.         result[0] = deque.peekFirst();
  18.         //窗口已形成阶段
  19.         for (int i = k; i < nums.length; i++) {
  20.             //删除了元素nums[i-k]，添加了元素nums[i]
  21.             if (nums[i-k] == deque.peekFirst()){
  22.                 deque.pollFirst();
  23.             }
  24.             //新增
  25.             while (!deque.isEmpty() && deque.peekLast() < nums[i]){
  26.                 deque.pollLast();
  27.             }
  28.             deque.offerLast(nums[i]);
  29.             result[i-k+1] = deque.peekFirst();
  30.         }
  31.         return result;
  32.     }
  33. }

三、循环队列的设计与实现

循环队列也被称为“环形缓冲器”是为了解决，在队列存取数据时，空间无法重复利用的问题，通过构造环形结构重复使用。在普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使队列的前面仍有空间。但是使用循环队列，我们可以利用队列前面的空间重新存储元素。

【实现思路】可以借鉴滑动窗口的模式
【队列·循环队列】.jpg

  1. public class MyCircularQueue {
  2.     //存储元素的数组
  3.     int[] queue;
  4.     //能够存储的最大容量
  5.     int capacity;
  6.     //头指针
  7.     int head;
  8.     //实际队列长度
  9.     int count;
  11.     public MyCircularQueue(int k){
  12.         capacity = k;
  13.         queue = new int[k];
  14.         head = 0;
  15.         count = 0;
  16.     }
  18.     public boolean isEmpty(){
  19.         return count == 0;
  20.     }
  22.     public boolean isFull(){
  23.         return count == capacity;
  24.     }
  26.     public boolean enQueue(int value){
  27.         if (isFull()){return false;}
  28.         int index = (head + count) % capacity;
  29.         queue[index] = value;
  30.         return true;
  31.     }
  32.     public boolean deQueue(){
  33.         if (isEmpty()){return false;}
  34.         head = (head + 1) % capacity;
  35.         count--;
  36.         return true;
  37.     }
  38.     public int front(){
  39.         if (isEmpty()){return -1;}
  40.         return queue[head];
  41.     }
  43.     public int tair(){
  44.         if (isEmpty()){return -1;}
  45.         int index = (head + count - 1) % capacity;
  46.         return queue[index];
  47.     }
  48. }

结语：

推荐一个网站visualgo，图形化地展示数据结构与算法
https://visualgo.net/zh