数据结构之队列

数据结构之队列

本篇是数据结构与算法之美学习笔记

队列是一种可以实现“先进先出”的存储结构。就排队办理业务，先到的人先办理，不能插队。

CUP的资源是有限的，任务的处理速度与线程的个数并不是线性正相关的。相反，过多的线程反而会导致CPU频繁切换，处理能力下降，所以线程池的大小一般都是综合考虑要处理任务的特点和硬件环境来预先设置的。

当我们向一个固定大小的线程池中请求一个线程的时候，如果线程池中没有空闲资源了，这时候线程池怎么处理这个请求呢？是拒绝请求还是排队请求？各种处理策略是神马呢，这时候就要用到队列了。

队列有两个最基本的操作，入队enqueue(),放一个数据到队列的尾部；出队dequeue()，从队列头部取出一个元素。

顺序队列和链式队列

队列可以使用数组来实现也可以使用链表来实现，用数组实队列的栈叫做顺序队列，用链表实现的队列叫做链式队列。

使用数组来实现一个队列：

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

    //申请一个大小为n的数组
    public ArrayQueue(int n) {
        this.items = new String[n];
        this.n = n;
    }

    //入队
    public boolean enqueue(String item){
        //如果队列满了返回false
        if(tail == n) return false;
        items[tail] = item;
        ++tail;
        return true;
    }

    //出队
    public String dequeue(){
        //head == tail 表示队列为空
        if(head == tail) return  null;
        String res = items[head];
        ++head;
        return res;
    }

}

队列需要两个指针，一个指向队头，一个指向队尾。

当a、b、c、d一次进入队列之后，队列中的head指针指向下标为0的位置，tail下标为4的位置

当我们调用两次出队操作的之后，队列中的head指针指向下标为2的位置，tail指针位置不变。

随着不停的入队和出队操作，head和tail指针会不断的往后移动移动到最右边，即使数组中还有空闲的空间也不能往队列中添加数据了，那怎么办呢？

我们可以使用数据搬移，当然出队的时候不会出现空间不够的情况也就不用搬移，我们只需要在入队的时候集中触发一次数据搬移即可。根据这个思想，上面的出队操作不用变，入队操作可以改成下面的：

public boolean enqueue(String item){
        //tail==n 说明队列满了
        if(tail == n){
            //tail==n&&head==0说明整个队列都是满的
            if(head == 0) return  false;
            //搬移数据
            for (int i = head; i < tail; i++) {
              items[i-head] = items[i];
            }
            //更新tail 和 head
            tail -= head;
            head = 0;
        }

        items[tail] = item;
        ++tail;
        return true;
    }

从上面的代码可以看到，当tail指针移动到数据的最右边之后，如果有新数据插入，我们可以将head和tail之间的数据，整体搬移到数组0到tail-head的位置。

使用链表实现队列：

使用链表实现队列同样需要head和tail指针，分别指向链表的第一个结点和最后一个结点。

入队的时候，tail的next指针指向新的结点，然后tail变成新的结点的next。

出队的时候，head的next结点变成它后面的结点的next结点。

public class LinkedQueue {

    private Node head = null;
    private Node tail = null;

    //入队
    public void enqueue(String value){
       if(tail == null){
           Node newNode = new Node(value,null);
           head = newNode;
           tail = newNode;
       }else {
           tail.next = new Node(value,null);
           tail = tail.next;
       }
    }
   //出队
    public String dequeue(){
        if(head == null) return null;
        String value = head.data;
        head = head.next;
        if(head == null){
            tail = null;
        }
        return value;
    }

    private static class Node{
        private String data;
        private Node next;

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

        public String getData() {
            return data;
        }
    }
}

循环队列：

上面使用数组来实现的队列，当tail==n的时候，会有数据的搬移操作，这样入队的时候的性能就会收到影响。有没有办法解决呢？可以使用循环队列。

原本的数组是一条直线，有头有尾，现在我们把首位相连组成一个环

当tail == n 的时候，表示队列满了，当 head == tail的时候表示队列是空的。

public class CircleQueue {
    private String[] items;
    private int n = 0;//总大小
    private int head = 0;
    private int tail = 0;

    //申请一个大小为n的数组
    public CircleQueue(int n) {
        this.items = new String[n];
        this.n = n;
    }

    //入队
    public boolean enqueue(String item){
        //(tail+1)%n == head表示满了
        if((tail + 1)%n == head) return false;
        items[tail] = item;
        tail = (tail+1)%n;
        return true;
    }

    //出队
    public String dequeue(){
        //head == tail 表示队列为空
        if(head == tail) return  null;
        String res = items[head];
        head = (head+1)%n;
        return res;
    }

}

阻塞队列：

阻塞队列就是在队列的基础上加了阻塞操作，就是在队列空的时候，从头部取数据会被阻塞，直到队列中有了数据才会返回。如果队列已经满了，那么插入数据的操作会被阻塞，直到队列中有新的空闲位置的时候才返回。

并发队列：

在多线程的情况下，会有多个线程同时操作队列，这时候就会存在线程安全的问题。

线程安全的队列称为并发队列，最简单直接的方式就是在enqueue()和dequeue()的方法上加上锁。

不过锁的粒度比较大，同一时刻只能有一个存或者取的操作。

通过基于数组的循环队列，利用CAS原子操作，可以实现非常高的并发队列。

大部分资源有限的场景，当没有空闲资源的时候，基本上都可以用于排队请求，比如线程池，数据库连接池等。