6. 队列

1、队列的基本概念

**队列（queue）**是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为**先进先出（FIFO—first in first out）**线性表。

队列的容量可以有限，也可以是无限的。

队列分为：

①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。

②、双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。

队列的实现

一、基于数组的Queue实现

一般情况下，对于Queue而言，最核心的操作是：插入队列(enqueue)、移出队列(dequeue)。因为在队列中，插入操作是插入到队列的最后，而移出操作是移出队列的头部元素。因此我们通常会使用两个变量**front（队头指针）和rear（队尾指针）**记录当前元素的位置。

假设我们有一个容量有限队列，用于存放字母，如下图所示：

img

当我们要插入一个元素时，因为总是插入到队列的最尾部，所以插入的位置是rear+1的位置。

当我们要移出一个元素时，是从队头指针front的位置开始移除(因为Queue头部的元素是最先加入进来的，根据FIFO原则，应该最先移除)。当移除一个元素之后，front应该加1，因为移出一个元素之后，下一个元素就变成了第一个元素。例如现在我们移出了5个元素：

img

当移出5个元素之后，队头指针就移动到了字母F的位置，前五个位置空下来了。队尾指针rear不变。 现在问题来了：队列头部移出的几个元素，位置空下来了。当我们添加元素的时候，从队尾开始加，当添加到最后一个位置时，怎么办？不让添加时不合理的，毕竟前几个位置已经空下来了。我们的期望是，当一个位置上的元素被移出之后，这个位置是可以被重复使用的。而我们这里讨论的是有限容量的数据，如果我们还继续添加元素，那么就要往队列头部来添加。 这实际上就涉及到了循环队列的概念。也就是当队尾指针到了数组的最后一个下标时，下一个位置应该就是数组的首部。 **因此，当队尾指针指向数组顶端的时候，我们要将队尾指针(rear)重置为-1，此时再加1，就是0，也就是数组顶端例。**如我们又添加了5个字母，那么结果应该如下图：

img

java 基于数组实现Queue

public class MyQueue {
    private Object[] queArray;
    //队列总大小
    private int maxSize;
    //前端
    private int front;
    //后端
    private int rear;
    //队列中元素的实际数目
    private int nItems;
     
    public MyQueue(int s){
        maxSize = s;
        queArray = new Object[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }
     
    //队列中新增数据
    public void insert(int value){
        if(isFull()){
            System.out.println("队列已满！！！");
        }else{
            //如果队列尾部指向顶了，那么循环回来，执行队列的第一个元素
            if(rear == maxSize -1){
                rear = -1;
            }
            //队尾指针加1，然后在队尾指针处插入新的数据
            queArray[++rear] = value;
            nItems++;
        }
    }
     
    //移除数据
    public Object remove(){
        Object removeValue = null ;
        if(!isEmpty()){
            removeValue = queArray[front];
            queArray[front] = null;
            front++;
            if(front == maxSize){
                front = 0;
            }
            nItems--;
            return removeValue;
        }
        return removeValue;
    }
     
    //查看对头数据
    public Object peekFront(){
        return queArray[front];
    }
     
     
    //判断队列是否满了
    public boolean isFull(){
        return (nItems == maxSize);
    }
     
    //判断队列是否为空
    public boolean isEmpty(){
        return (nItems ==0);
    }
     
    //返回队列的大小
    public int getSize(){
        return nItems;
    }
     
}

---

java中的队列Queue

典型代表：

ConcurrentLinkedQueue：

• ConcurrentLinkedQueue是由链表结构组成的线程安全的先进先出无界队列。
• 当多线程要共享访问集合时，ConcurrentLinkedQueue是一个比较好的选择。
• 不允许插入null元素
• 支持非阻塞地访问并发安全的队列，不会抛出ConcurrentModifiationException异常。

img

img

java中的双端队列(Deque)

Deque继承自Queue接口，也可以作为单端队列使用

典型代表：LinkedList

img

使用双端队列Deque实现栈的功能

java已经废弃了类Stack, 使用Deque定义了LIFO（后进先出）的栈操作

img

阻塞队列(BlockingQueue)

阻塞队列特点: 阻塞队列的特点就在于阻塞，它可以阻塞线程，让生产者消费者得以平衡，阻塞队列中有两个关键方法 Put 和 Take 方法

Take : 方法的功能是获取并移除队列的头结点，通常在队列里有数据的时候是可以正常移除的。可是一旦执行 take 方法的时候，队列里无数据，则阻塞，直到队列里有数据。一旦队列里有数据了，就会立刻解除阻塞状态，并且取到数据。

Put: 方法插入元素时，如果队列没有满，那就和普通的插入一样是正常的插入，但是如果队列已满，那么就无法继续插入，则阻塞，直到队列里有了空闲空间。如果后续队列有了空闲空间，比如消费者消费了一个元素，那么此时队列就会解除阻塞状态，并把需要添加的数据添加到队列中。

img

常见的阻塞队列成员:

1、ArrayBlockingQueue: 数组结构的有界阻塞队列，此队列按照先进先出(FIFO)原则对元素进行排序，同时支持公平锁和非公平锁。它的线程安全性由 ReentrantLock 来实现的。

public ArrayBlockingQueue(int capacity) {...}
public ArrayBlockingQueue(int capacity, boolean fair) {...}

• 如上所示，ArrayBlockingQueue 提供的构造函数中，我们需要指定队列的长度，同时我们也可以设置队列是都是公平的，当我们设置了容量后就不能再修改了，符合数组的特性，此队列按照先进先出（FIFO）的原则对元素进行排序。
• 和 ReentrantLock 一样，如果 ArrayBlockingQueue 被设置为非公平的，那么就存在插队的可能；如果设置为公平的，那么等待了最长时间的线程会被优先处理，其他线程不允许插队，不过这样的公平策略同时会带来一定的性能损耗，因为非公平的吞吐量通常会高于公平的情况。

2、LinkedBlockingQueue: 链表结构的有界阻塞队列，队列的默认大小为 Integer.MAX_VALUE，这个值是非常大的，几乎无法达到，对此我们可以认为这个队列基本属于一个无界队列（也又认为是有界 队列）也是按照先进先出原则对元素进行排序的。它的线程安全性由 ReentrantLock 来实现的。

3、PriorityBlockingQueue: 支持线程优先级排序的无界阻塞队列。默认自然序进行排序，也可以自定义实现compareTo()方法来指定元素排序规则，不能保证同优先级元素的顺序。

4、DelayQueue: 实现PriorityBlockingQueue优先级排序的延迟阻塞队列，在创建元素时，可以指定多久才能从队列中获取当前元素。只有延时期满后才能从队列中获取元素。

5、SynchronousQueue: 不存储元素的阻塞队列，每一个put操作必须等待take操作，否则不能添加元素。支持公平锁和非公平锁。

6、LinkedBlockingDeque： 一个由链表结构组成的双向阻塞队列。队列头部和尾部都可以添加和移除元素，多线程并发时，可以将锁的竞争最多降到一半。

这些阻塞队列的实现类是都是实现了BlockingQueue接口