欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java 中的队列 Queue

程序员文章站 2024-03-18 08:15:22
...

一、队列的定义

队列(Queue)是一种先进先出(FIFO)的数据结构,Java中定义了java.util.Queue接口用来表示队列。Java中的QueueListSet属于同一个级别接口,它们都继承于Collection接口。Java中还定义了一种双端队列java.util.Deque,常用的LinkedList就实现了Deque接口。我们看一下Queue和Dequeue的定义:

Queue:

public interface Queue<E> extends Collection<E> {
    
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

Deque:

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

    void addFirst(E e);

    void addLast(E e);

    boolean offerFirst(E e);

    boolean offerLast(E e);

    E removeFirst();

    E removeLast();

    E pollFirst();

    E pollLast();

    E getFirst();

    E getLast();

    E peekFirst();

    E peekLast();

    boolean removeFirstOccurrence(Object o);

    boolean removeLastOccurrence(Object o);

    // *** Queue methods ***

    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();

    // *** Stack methods ***

    void push(E e);

    E pop();
    
    // *** Collection methods ***
    
    boolean remove(Object o);

    boolean contains(Object o);

    public int size();

    Iterator<E> iterator();

    Iterator<E> descendingIterator();

}

二、队列的实现

Java中对于队列的实现分为非阻塞阻塞两种。

2.1 非阻塞队列

LinkedList

LinkedList是双向链表结构,在添加和删除元素时具有比ArrayList更好的性能,但获取元素性能弱于ArrayList。当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比。

PriorityQueue

PriorityQueue维护了一个有序列表,存储到队列中的元素会按照自然顺序排列(元素实现Comparable接口)。当然,我们也可以给它指定一个实现了 java.util.Comparator 接口的排序类来指定元素排列的顺序。

ConcurrentLinkedQueue

ConcurrentLinkedQueue 是基于链表的并且线程安全的队列。

2.2 阻塞队列

阻塞队列定义在了java.util.concurrent包中,java.util.concurrent.BlockingQueue 继承了Queue接口,它有 5 个实现类,分别是:

ArrayBlockingQueue

一个内部由数组支持的有界队列。初始化时必须指定队列的容量,还可以设置内部的ReentrantLock是否使用公平锁。但是公平性会使你在性能上付出代价,只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队列,此队列按 FIFO(先进先出)原则对元素进行排序。它的思想就是如果BlockQueue是空的,那么从BlockingQueue取东西的操作(take方法)将会被阻断进入等待状态,直到BlockingQueue进了东西才会被唤醒。同样,如果BlockingQueue是满的,任何试图往里存东西的操作(put方法)也会被阻断进入等待状态,直到BlockingQueue里有空间才会被唤醒继续操作。

LinkedBlockingQueue

一个内部由链表支持的可选有界队列。初始化时不需要指定队列的容量,默认是Integer.MAX_VALUE,也可以看成容量无限大。此队列按 FIFO(先进先出)排序元素 。

PriorityBlockingQueue

一个内部由优先级堆支持的*优先级队列。PriorityBlockingQueue是对 PriorityQueue的再次包装,队列中的元素按优先级顺序被移除(元素实现Comparable接口或指定Comparator接口)。

DelayQueue

一个内部由优先级堆支持的、基于时间的调度队列。队列中存放Delayed元素,只有在延迟期满后才能从队列中提取元素。当一个元素的getDelay()方法返回值小于等于0时才能从队列中poll中元素,否则poll()方法会返回null。

SynchronousQueue

一个利用 BlockingQueue 接口的简单聚集(rendezvous)机制。

下面简单介绍一下其中常用的方法:

  • add:增加一个元索 ,如果队列已满,则抛出一个IIIegaISlabEepeplian异常。

  • remove:移除并返回队列头部的元素,如果队列为空,则抛出一个NoSuchElementException异常。 
  • element:返回队列头部的元素,如果队列为空,则抛出一个NoSuchElementException异常。
  • offer:添加一个元素并返回true,如果队列已满,则返回false。   
  • poll:移除并返问队列头部的元素,如果队列为空,则返回null。   
  • peek:返回队列头部的元素,如果队列为空,则返回null。
  • put:添加一个元素,如果队列满,则阻塞。   
  • take:移除并返回队列头部的元素,如果队列为空,则阻塞。

原文地址:https://www.cnblogs.com/yuansc/p/9087044.html