1、队列的基本概念

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

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

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

队列分为:

1、 单向队列(Queue):只能在一端插入数据,另一端删除数据。

2、 双向队列(Deque):每一端都可以进行插入数据和删除数据操作。

队列的实现

一、基于数组的Queue实现

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

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

 

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

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

 

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

 

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异常。

 

 

java中的双端队列(Deque)

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

典型代表:LinkedList

 

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

java已经废弃了类Stack, 使用Deque定义了LIFO(后进先出)操作

 

阻塞队列(BlockingQueue)

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

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

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

 

常见的阻塞队列成员:

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接口