Beauty Of Algorithms 9 Summary. Queue

队列的概念

• 先进者先出
• 支持两个操作：入队 enqueue()，放一个数据到队尾；出队 dequeue()，从队头取一个元素。
• 队列也是一种操作受限的线性表

  数组实现 ( 顺序队列 )

public class ArrayQueue {
    private String[] items;
    private int n = 0;
    private int head = 0;
    private int tail = 0;

    public ArrayQueue(int n) {
        items = new String[n];
        this.n = n;
    }

    public void enqueue(String item) throws Exception {
        if (tail == n) {
            throw new Exception("queue is full , cant enter any more !");
        }
        items[tail] = item;
        tail++;
    }

    public String dequeue() throws Exception {
        if (head == tail) {
            throw new Exception("queue is empty !");
        }
        String ret = items[head];
        head++;
        return ret;
    }

    public void printQueue() {
        for (int i = head; i < tail; i++) {
            System.out.print(items[i] + " ");
        }
    }

    public static void main(String[] args) throws Exception {
        ArrayQueue arrayQueue = new ArrayQueue(10);
        arrayQueue.enqueue("1");
        arrayQueue.enqueue("2");
        arrayQueue.enqueue("3");
        arrayQueue.enqueue("4");
        arrayQueue.enqueue("4");

        arrayQueue.printQueue();
        System.out.println(" ");
        System.out.println("***************************");
        System.out.println(arrayQueue.dequeue());
        System.out.println("***************************");

        arrayQueue.printQueue();
    }

}

假溢出

以上代码中的出队入队会造成假溢出现象，即随着不断的出队，head在增加，head前面的数组空间是被空着的。

修改入队方法

public void enqueue2(String item) throws Exception {
    if (tail == n) {
        if (head == 0) {
            throw new Exception("queue is full , cant enter any more !");
        }
        for (int i = head; i < tail; i++) {
            items[i - head] = items[i];
        }
        tail -= head;
        head = 0;
    }
    items[tail] = item;
    tail++;
}

链表实现

链表无需考虑溢出

public class SingleLinkQueue<T> {
    private class Node<T> {
        private T data;
        private Node<T> next;

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<T> tail;
    private Node<T> head;
    private int size;

    public SingleLinkQueue() {
        head = tail = null;
    }

    public void enqueue(T item) {
        Node<T> node = new Node<T>(item, null);
        if (head == null) {
            head = node;
            tail = node;
        }

        tail.next = node;
        tail = node;
        size++;
    }

    public T dequeue() throws Exception {
        if (head == null) {
            throw new Exception("Queue is empty, no element to dequeue !");
        }
        T ret = head.data;
        head = head.next;
        size--;
        return ret;
    }

    public void printQueue(){
        Node<T> tem = head;
        while (tem!= null){
            System.out.print(tem.data + " ");
            tem = tem.next;
        }
    }

    public static void main(String[] args) throws Exception {
        SingleLinkQueue<String> singleLinkQueue = new SingleLinkQueue<>();
        singleLinkQueue.enqueue("1");
        singleLinkQueue.enqueue("2");
        singleLinkQueue.enqueue("3");
        singleLinkQueue.enqueue("4");
        singleLinkQueue.printQueue();
        System.out.println("\n***************************");
        System.out.println(singleLinkQueue.dequeue());
        System.out.println("***************************");
        singleLinkQueue.printQueue();
    }

}

循环队列 ( 基于数组 )

循环队列可以实现不进行数据搬移而解决假溢出现象。

public class CircularQueue {
    private String[] items;
    int n = 0;
    int head = 0;
    int tail = 0;

    public CircularQueue(int n) {
        this.n = n;
        items = new String[n];
    }

    public void enqueue(String item) throws Exception {
        if ((tail + 1) % n == head) {
            throw new Exception("queue is full ,cant enqueue any more items !");
        }
        items[tail] = item;
        tail = (tail + 1) % n;
    }

    public String dequeue() throws Exception {
        if (tail == head) {
            throw new Exception("queue is empty !");
        }
        String ret = items[head];
        head = (head + 1) % n;
        return ret;
    }

    public void printQueue() {
        for (int i = head; i % n != tail; i++) {
            System.out.print(items[i] + " ");
        }
    }

    public static void main(String[] args) throws Exception {
        CircularQueue circularQueue = new CircularQueue(10);
        circularQueue.enqueue("1");
        circularQueue.enqueue("2");
        circularQueue.enqueue("3");
        circularQueue.enqueue("4");
        circularQueue.enqueue("4");

        circularQueue.printQueue();
        System.out.println(" ");
        System.out.println("***************************");
        System.out.println(circularQueue.dequeue());
        System.out.println("***************************");

        circularQueue.printQueue();
    }

}

队列的常见应用

阻塞队列

• 在队列的基础上增加阻塞操作，就成了阻塞队列。

• 阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；

  如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。

• 从上面的定义可以看出这就是一个“生产者-消费者模型”。

  这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。

  当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，

  这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。

  不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，

  比如配置几个消费者，来应对一个生产者。

并发队列

• 在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
• 并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作
• 实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

线程池资源枯竭时的处理

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

思考

如何实现无锁的并发队列？