队列

一、知识

队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。

队列跟栈一样，也是一种操作受限的线性表数据结构 。队列最基本的操作也是两个：入队：放一个数据到队列尾部；出队：从队列头部取一个元素。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

项目中用到的特殊队列：阻塞队列、并发队列等。（阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全）

二、应用

1. 设计循环双端队列

可以通过数组、链表实现循环双端队列，下面方法通过数组实现，需要注意的点为：头尾指针变动需要进行特殊处理。

class MyCircularDeque {

	//数组
    private int[] arr;
    //头指针
    private int start;
    //尾指针
    private int end;
    //队列长度
    private int size;

    public MyCircularDeque(int k) {
    	//循环队列有一个空间不能使用，需要开k+1个空间
        arr = new int[k + 1];
        size = k + 1;
        start = 0;
        end = 0;
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        //防止头节点减1变为负数
        start = (start - 1 + size) % size;
        arr[start] = value;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        arr[end] = value;
        //对size取模
        end = (end + 1) % size;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        //取模
        start = (start + 1) % size;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        //防止end减1变成负数
        end = (end - 1 + size) % size;
        return true;
    }

    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return arr[start];
    }

    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return arr[(end - 1 + size) % size];
    }

    public boolean isEmpty() {
        return end == start;
    }

    public boolean isFull() {
        return (end + 1) % size == start;
    }
}

2. 滑动窗口最大值

双端队列存储长为 k 的滑动窗口的下标，为什么存下标：判断该数是否在窗口中。将元素存入双端队列时，应将该元素与队列中最后的元素进行判断，小于则弹出最后的元素，直至队列中元素大于等于该元素或者队列为空，这样队首元素即为当前窗口的最大元素。

public int[] maxSlidingWindow(int[] nums, int k) {
    //双端队列
    Deque<Integer> deque = new ArrayDeque();
    //将 k 个元素加入双端队列
    for (int i = 0; i < k; i++) {
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
    }
    int[] arr = new int[nums.length - k + 1];
    arr[0] = nums[deque.peekFirst()];
    for (int i = k; i < nums.length; i++) {
        //判断队列元素是否在窗口中
        if (deque.peek() + k - 1 < i) {
            deque.poll();
        }
        //弹出队列中小于该元素的数
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        //将该数添加到队列中
        deque.offerLast(i);
        //当前窗口的最大值
        arr[i - k + 1] = nums[deque.peekFirst()];
    }
    return arr;
}

3. 队列的最大值

创建两个队列，一个为双端队列用于存储最大值（方法和第二题一样），需要出队时判断普通队列和双端队列的队首的值是否一样，一样则出队。

class MaxQueue {
    private Deque<Integer> deque;
    //双端队列
    private Deque<Integer> maxDeque;

    public MaxQueue() {
        deque = new ArrayDeque();
        maxDeque = new ArrayDeque();
    }

    public int max_value() {
        if (maxDeque.isEmpty()) {
            return -1;
        }
        return maxDeque.peek();
    }

    public void push_back(int value) {
        //与第二题一样
        while (!maxDeque.isEmpty() && maxDeque.peekLast() < value) {
            maxDeque.pollLast();
        }
        deque.offerLast(value);
        maxDeque.offerLast(value);
    }

    public int pop_front() {
        if (deque.isEmpty()) {
            return -1;
        }
        //两个对首值xiang'd
        if (deque.peek().equals(maxDeque.peek())) {
            maxDeque.poll();
        }
        return deque.poll();
    }
}