Java容器队列(一)-queue(队列)

1 如何理解“队列”

队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。

相对于栈只支持两个基本操作：入栈 push()和出栈 pop()，对于也只支持两个操作入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素，因此队列跟栈一样，也是一种操作受限的线性表数据结构

image

队列跟栈一样，也是一种抽象的逻辑存储结构

2 Java中队列“接口”

Java中定义了queue来描述一个队列

public interface Queue<E> extends Collection<E> {

    //将元素插入队列尾部，方法在添加失败（比如队列已满）时会报 一些运行时错误.
    boolean add(E e);
    
    //将元素插入队列尾部，方法在添加失败（比如队列已满）时，不会抛出异常，值会返回false
    boolean offer(E e);
    
    //将队首的元素删除，队列为空则抛出异常
    E remove();
    
    //将队首的元素删除，队列为空则返回null
    E poll();
    
    //获取队首元素，但不移除，队列为空则抛出异常
    E element();
    
    //获取队首元素，但不移除，队列为空则返回null
    E peek();
}

这里添加、删除、查询这些个操作都提供了两种形式。在操作失败时直接抛出异常，而另一种则返回一个特殊的值。

image

2 Queue基类实现。

Java定义一个基类AbstractQueue 来实现 Queue 接口，把一些公共的逻辑放到基类中实现

实现了Queue接口add、remove和element三个方法

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E> {

    public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }
    
    public E remove() {
        E x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
    
    public E element() {
        E x = peek();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }

实现了Collection接口clear与addAll方法

public void clear() {
    while (poll() != null)
        ;
}

public boolean addAll(Collection<? extends E> c) {
    if (c == null)
        throw new NullPointerException();
    if (c == this)
        throw new IllegalArgumentException();
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}