队列/Queue

概述

队列也是一种操作受限的线性结构。它与栈相反是先进先出（FIFO—first in first out），只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作，与我们生活中排队一样。

public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

单向队列（Queue)

只能在一端插入数据，另一端删除数据。

import java.util.ArrayList;
public class ArrayQueue<E> implements Queue<E> {
    private ArrayList<E> list;
    public ArrayQueue() {
        list = new ArrayList<>();
    }
    @Override
    public int getSize() {
        return list.size();
    }
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
    @Override
    public void enqueue(E e) {
        list.add(e);
    }
    @Override
    public E dequeue() {
        if (!isEmpty()) {
            return list.remove(list.size() - 1);
        }
        return null;
    }
    @Override
    public E getFront() {
        if (!isEmpty()) {
            return list.get(0);
        }
        return null;
    }
    @Override
    public String toString() {
        return list.toString();
    }
}

循环队列

Java队列API

Queue的插入操作

/**
* 相同点:
* 插入为null的元素,会报空指针
* 插入与执行泛型不符的类型会报类型转换异常
* 插入某些不允许插入的元素,会阻止其插入,IDE会提示非法参数
*
* 不同点:
* 在满队列状态下:
* 使用add()方法会报IllegalStateException异常,提示队列已满.
* 使用offer()方法在此情况下不会报异常而返回false.
*/
   boolean add(E e);
   boolean offer(E e);

上述两种方法都是插入操作，当插入元素成功时，会返回true.注意 : 队列中不允许插入为null的元素,否则会报空指针.在进行插入操作时,一般情况推荐使用offer()来插入元素.

Queue的取出操作

/**
* 相同点:
* 都是Queue的取出操作,返回值为队列容器头部元素.
*
* 不同点:
* 当处于空队列状态时,remove()方法会抛出队列为空,没有匹配元素的的异常
* 而poll()方法则会返回null值,不会报异常.
*/
E remove();
E poll();

在进行删除操作时,一般情况推荐使用poll()来取出元素

Queue的检索操作

/**
* 相同点:
* 都是Queue的检索操作,返回值为队列容器头部元素,但是不会删除元素.
*
* 不同点:
* 当处于空队列状态时,element()方法会抛出队列为空,没有匹配元素的的异常
* 而peek()方法则会返回null值,不会报异常.
*/
E element();
E peek();

在进行检索操作时,一般情况推荐使用peek()来取出元素

双向队列/double ended queue

Deque是一种具有队列和栈的性质的数据结构.双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行.
通过开始的类图可以发现，Deque继承了Queue（队列）的接口，它的直接实现有ArrayDeque、LinkedList等。
Deque的容量有两种模式，一种是固定长度，另一种是容量无限。
同Queue一样,Deque也定义了两套操作访问元素的方法，比如在头部和尾部进行插入、删除、检索元素、同样的，一种是在满队列或者空队列的操作元素时，会报异常，而另一种则会return null或者return false。
LinkedList 大小可变的链表双端队列，允许元素为 null
ArrayDeque 大下可变的数组双端队列，不允许 null
注意：LinkedList 和ArrayDeque是线程不安全的容器。
在并发场景下，推荐使用LinkedBlockingDeque：因为LinkedBlockingDeque在队列为空的情况下，获取操作将会阻塞，直到有元素添加。