21 / 02 / 19

Java 数据结构丨队列

基本概念

队列，Queue，是一种特殊的线性表，它也类似栈，操作也有限制：只允许在表的前端进行删除操作，而在表的后端进行插入操作。
与栈的入栈、出栈类似，在队列中插入一个队列元素成为入队，从队列中删除一个队列元素成为出队。但与栈的特点相反，队列的元素只能先入先出(First In First Out，简称FIFO)。
队列的出口端叫作队头(front)，队列的入口端叫作队尾(rear)。

生活中，可以体现出队列特点的情景也不少：商城排队购物结算；客运站排队刷脸检票；红绿灯等候起步的车流......先进先出，公平有序。

实现队列

队列既可以用数组来实现，也可以用链表来实现。

当使用数组来实现队列时，执行一次出队操作：数据项被移除，同时队头指针增加一。

那么问题出现了：如果不断执行出队操作，队头的左侧空间是否失去了作用？如果此时要入队一个数据，但是队尾已经没有空间了，队尾指针不能再向后移动了，那么是不是需要将所有元素往数组开头移动，给队尾腾出空间呢？这很符合生活中排队的情境——前面的人出队了，后面一位补上。这就是顺序队列。

如果队头的左侧空闲的空间失去了作用，那队列的容量岂不是越来越小了？也不要忽略在数组中将所有元素往数组开始移动的开销，所以顺序队列的性能很低。在数组不扩容的前提下，为了避免队列不满却不能插入新数据项的问题，让队头队尾指针绕回到数组开头的位置，同时维持了队列容量的恒定，这就是循环队列。在物理存储上，队尾的位置也可以在队头之前，当再有元素入队时，队尾指针继续后移即可。

静态数组实现

class ArrayQueue {
    // 数组的大小
    private int maxSize;
    // 存储数据的数组
    private int[] queArray;
    // 队头
    private int front;
    // 队尾
    private int rear;
    // 队列现有元素数量
    private int nItems;

    public ArrayQueue(int s) {
        maxSize = s + 1;
        queArray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return (nItems == 0);
    }

    // 判断是否为满
    public boolean isFull() {
        return (nItems == maxSize);
    }

    // 现有元素个数
    public int size(){
        return nItems;
    }

    // 查看队头数据项的值
    public int peek(){
        return queArray[front];
    }

    // 入队
    public void enque(int value) throws Exception{
        if (isFull()){
            throw new Exception("队列已满！");
        }
        if (rear == maxSize-1){
            rear = -1;
        }
        queArray[++rear] = value;
        nItems++;
    }

    // 出队
    public int deque()throws Exception{
        if (isEmpty()){
            throw new Exception("队列是空的！");
        }
        if (front == maxSize){
            front = 0;
        }
        int temp = queArray[front++];
        nItems--;
        return temp;
    }

    // 输出队列
    public void show(){
        for (int i = front; i != rear+1; i = (i+1)%queArray.length){
            System.out.print(queArray[i] + " ");
        }
    }

}

单链表实现

class LinkedQueue<T> {
    // 链表结点
    class Node<T> {
        //数据域
        private T data;
        // 后续指针
        private Node<T> next;
        // 无参构造
        public Node() {
            this.data = null;
            this.next = null;
        }
        // 有参构造
        public Node(T data) {
            this.data = data;
            this.next = null;
        }

        public void setNext(Node<T> t) {
            this.next = t;
        }

        public T getData() {
            return this.data;
        }

        public Node<T> getNext() {
            return this.next;
        }
    }
    // 队头
    private Node<T> front;
    // 队尾
    private Node<T> rear;
    // 队列当前长度
    private int size;

    public LinkedQueue() {
        this.front = null;
        this.rear = null;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return (size == 0);
    }

    // 获取队列的长度
    public int size(){
        return size;
    }

    //查看队头的数据
    public T peek() throws Exception {
        if (isEmpty()) {
            throw new Exception("队列为空！");
        } else {
            return front.getData();
        }
    }

    //入队
    public boolean enQue(T t) {
        Node<T> newNode = new Node<>(t);
        //如果头等于空
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            //插入尾部
            rear.next = newNode;
            rear = newNode;
        }
        size++;
        return true;
    }

    //出队
    public Node<T> deQue() throws Exception {
        if(isEmpty()){
            throw new Exception("空队列异常！");
        } else {
            //得到队列头元素
            Node<T> value = front;
            front = front.next;
            value.next = null;
            size--;
            return value;
        }
    }
}

常用 API

入队(enque)，也可以称作 insert、add，就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将成为新的队尾。
出队(deque)，也可以称作 remove、delete，就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。
peek()，返回队头数据项的值，并不从队中删除这个数据项。
size()，返回队列内元素的数量。
isEmpty()，测试队列是否为空，返回布尔值。
isFull()，判断队列是否为满，返回布尔值。

优劣

在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。还可以使用队列进行异步处理、系统解耦、数据同步、流量削峰、缓冲、限流等。例如，不是所有的业务都必须实时处理、不是所有的请求都必须实时反馈结果给用户、不是所有的请求都必须 100% 处理成功、不知道谁依赖“我”的处理结果、不关心其他系统如何处理后续业务、不需要强一致性，只需保证最终一致性即可、想要保证数据处理的有序性等等，这些问题都考虑使用队列来解决。循环队列插入数据项和移除数据项的时间复杂度都是O(1)。

参考

Data Structure

Java