队列:是一种先进先出的数据结构。
队列的使用
Queue是一个实现Collection接口的接口。JDK自带了很多实现类,比如LinkedList、ConcurrentLinkedQueue、LinkedBlockingQueue等。
Queue接口中比较常用的接口add(e)、offer(e)、poll()、peek()方法,add和offer方法的区别在于add失败时会抛出异常,offer方法失败返回false,有的实现类add方法直接调用offer方法。poll和peek的区别在于poll删除第一个元素并返回,而peek直接返回第一个元素而不删除。
一个简单的例子:
优先队列(PriorityQueue)
PriorityQueue默认通过一个小的顶堆实现优先级队列,也可以指定Comparator的优先级来自定义实现队列。
我们来看一个例子,随机添加10个数字,我们取出的是从小到大的平滑度。
如果指定Comparator,则可以自定义优先级,如下:
优先队列的实现原理
上面简单说了,优先级队列底层通过堆实现优先级,堆底层通过数组Object[]队列实现。默认容量为11,添加数据时如果容量不够,会自动扩容(如果容量小于64,则增加一倍,否则增加50%)。
添加元素时,它们将被放置在数组的末尾,然后浮动到适当的位置。
出队的时候先删除第一个元素,然后拿到最后一个元素,然后通过下沉的方法让最后一个元素找到合适的位置,这样数据结构也可以保持完整的小顶堆或大顶堆。

java

java中queue的用法

java中的队列类是队列数据结构管理类。其中的元素可以按照添加的顺序删除。
队列通常(但不一定)以FIFO(先进先出)的方式对元素进行排序。例外情况是优先级队列,它根据提供的比较器或其自然顺序对元素进行排序,以及LIFO队列(或堆栈),它以LIFO(后进先出)方式对元素进行排序。无论使用哪种排序方法,队列的头部都是通过调用remove()或poll()删除的元素。在FIFO队列中,所有新元素都插入到队列的末尾。其他类型的队列可能使用不同的元素放置规则。每个Queue实现都必须指定其order属性。
offer添加一个元素,如果队列已满则返回true,false
poll移除并返回队列头部的元素。如果队列为空,则返回null
peek返回队列头部的元素,如果队列为空则返回null
如果队列已满,put添加一个元素并阻塞
take移除并返回队列头部的元素,如果队列为空则阻塞
element返回队列头部的元素如果队列为空,则抛出NoSuchElementException
add如果队列已满,添加元素索引,抛出IIIegaISlabEepeplian异常
如果队列为空,remove删除并返回队列头部的元素,抛出一个
NoSuchElementException
注意:poll和peek方法在出错时返回null。因此,在队列中插入空值是不合法的。
还有带有超时的offer和poll方法的重载,例如,下面的调用:
布尔成功=q.offer(x,100,TimeUnit.MILLISECONDS);
尝试在100毫秒内将元素插入队列尾部。如果成功,立即返回true;否则,当达到超时时,返回false。同样,调用:
对象头=q.poll(100,TimeUnit.MILLISECONDS);
如果在100毫秒内成功移除队列头元素,则立即返回头元素;否则,当达到超时时,返回null。
阻塞操作是put和take。put方法在队列满时阻塞,而take方法在队列为空时阻塞。
Queue接口与List和Set处于同一级别,都继承了Collection接口。LinkedList实现了Queue接口。Queue接口缩小了对LinkedList方法的访问权限(即如果方法中的参数类型为Queue,则只能访问Queue接口定义的方法,不能直接访问LinkedList的非Queue方法),以便只能使用适当的方法。BlockingQueue继承了Queue接口。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注