06.队列

1.定义

一种操作受限的数据结构，只支持入列(enqueue)和出列(dequeue)

2.实现

用数组来实现

public class ArrayQueue {

    // 队列的长度
    private int len;
    // 队尾
    private int tail;
    // 队头
    private int head;
    // 数组
    int[] arr;

    public ArrayQueue(int len) {
        this.len = len;
        this.tail = 0;
        this.head = 0;
        arr = new int[len];
    }

    // 队列中加元素
    public boolean enqueue(int item) {
        if (tail == len) {
            // 说明队列已经满了
            if (head == 0) {
                return false;
            }
            // 搬移，将head-tail的元素搬迁到 0-(tail-head)
            for (int i = head; i < tail; i++) {
                arr[i - head] = arr[i];
            }
            // 更新搬移后的tail和head
            head = 0;
            tail = tail - head ;
        }
        arr[tail++] = item;
        return true;
    }

    // 出列也是从最后面先出
    public int dequeue() {
        // 如果二者相等，说明没有元素了
        if (head == tail) {
            return null;
        }
        int ret = arr[head];
        head++;
        return ret;
    }
}

image.png

用链表来实现

public class LinkedQueue {

    // 尾结点
    Node tailNode = null;
    // 头结点
    Node headNode = null;

    // 入队
    public boolean enqueue(int item) {
        if (tailNode == null) {
            headNode = tailNode = new Node(item, null);
        } else {
            tailNode.next = new Node(item, null);
            tailNode = tailNode.next;
        }
        return true;
    }

    // 出队
    public int dequeue() {
        if (headNode == null) {
            return null;
        }
        int ret = headNode.data;
        headNode = headNode.next;
        //注意更新一下tailhead
        if (headNode == null) {
            tailNode = null;
        }
        return ret;
    }

    class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

image.png

循环队列

• 不需要在tail ==n的时候搬移数据；
• 但是会少存储一个数据单元，tail所指向的元素为空；

• 判断条件： （tail==head）为空 （(tail+1)%n==head）满

  
  image.png

public class CircularQueue {
    // 初始数组，假定为int类型
    int[] arr;
    // 容量
    int size;
    // 头
    int head;
    // 尾
    int tail;

    // 初始化
    public CircularQueue(int size) {
        this.size = size;
        arr = new int[size];
        head = 0;
        tail = 0;
    }

    public boolean enQueue(int item) {
        // 队列已经满的标志
        if ((tail + 1) % size == head) {
            return false;
        }
        arr[tail] = item;
        // 对于tail增加要考虑
        tail = (tail + 1) % size;
        return true;
    }

    public int deQueue() {
        // 表示队列已经满
        if (tail == head) {
            return null;
        }
        int ret = arr[head];
        head = (head + 1) % size;
        return ret;
    }
}

3.用途

3.1 阻塞队列

在队列的基础上加了阻塞的操作，如果入队时候没有空余位置或者出队的时候没有元素，那么就阻塞等待。
利用此可以实现一个生产者-消费者模型：基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。

image.png

3.2并发队列

• 最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低；
• 基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因
  考虑使用CAS实现无锁队列，则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否，则允许入队，反之，本次入队失败。出队则是获取head位置，进行cas。

3.3 线程池设计

当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？

• 一种是直接拒绝请求；
• 阻塞排队，当有线程资源的时候再进行分配。做到公平的先来后到，那么可以使用队列。
  • 基于链表的实现，无界队列，导致过多的请求排队，从而是请求响应的时间比较长，不适合对时间敏感的系统；
  • 基于数组的实现，有界队列，队列已满的时候就会拒绝请求，是和对时间名的系统；

实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队

4.小结