专栏首页三分恶的专栏Java Review (二十八、集合----- Queue 集合)

Java Review (二十八、集合----- Queue 集合)

队列(Queue)是一种经常使用的集合。Queue实际上是实现了一个先进先出(FIFO:First In First Out)的有序表。它和List的区别在于,List可以在任意位置添加和删除元素,而Queue只有两个操作:

  • 把元素添加到队列末尾;
  • 从队列头部取出元素。

超市的收银台就是一个队列:

Queue 用于模拟队列这种数据结构。

 Queue 接口中定义了如下几个方法 。

  • void add(Object e): 将指定元素加入此队列 的 尾部。
  • Object element() : 获取队列头部的元素 , 但是不删除该元素 。
  • boolean offer(Object e) : 将指定元素加入此队列的尾部。当使用有容量限制的队列时, 此方法通常比add(Object e)方法更好 。
  • Object peek(): 获取队列头部的元素 , 但是不删除该元素 。 如果此队列为空,则返回 null 。
  • Object poll() : 获取队列头部的元素 , 并删除该元素。如果此队列为空 , 则返回 null 。
  • Object remove() : 获取队列头部的元素 , 并删除该元素 。

API:java.util.Queue

PriorityQueue 实现类

PriorityQueue 是 一个比较标准的队列实现类。之所以说它是比较标准的队列实现 , 而不是绝对标准的队列实现 , 是因为 PriorityQueue 保存队列元的顺序并不是按加入队列的顺序,而是按队列元素的大小进行重新排序 。 因此当调用 peek()方法或者 poll()方法取出队列中的元素时,并不是取出最先进入队列的元素 , 而是取出队列中最小 的元素。从这个意义上来看 , PriorityQueue 己经违反了队列的最基本规则: 先进先出 ( FIFO ) 。

 下面程序示范了 PriorityQueue 队列的用法:

PriorityQueueTest.java

public class PriorityQueueTest
{
	public static void main(String[] args)
	{
		PriorityQueue pq = new PriorityQueue();
		// 下面代码依次向pq中加入四个元素
		pq.offer(6);
		pq.offer(-3);
		pq.offer(20);
		pq.offer(18);
		// 输出pq队列,并不是按元素的加入顺序排列
		System.out.println(pq); // 输出[-3, 6, 20, 18]
		// 访问队列第一个元素,其实就是队列中最小的元素:-3
		System.out.println(pq.poll());
	}
}

Prio rityQueue 不允许插入 null 元素,它还需要对队列元素进行排序 , PriorityQueue 的元素有两种排序方式 :

  • 自然排序 : 采用自然顺序的 PriorityQueue 集合中的元素必须实现Comparable 接口,而且应该是同 一个类的多个实例 , 否则可能导致 ClassCastException 异常 。
  • 定制排序 : 创建 PriorityQueue 队列 时, 传入一个 Comparator 对象 , 该对象负责对队列中的所有元素进行排序 。 采用定制排序时不要求队列元素实现Comparable 接口 。

PriortyQueue 队列对元素的要求与 TreeSet 对元素的要求基本一致。

API:java.util.PriorityQueue

Deque 接口与 ArrayDeque 实现类

Deque 接口是 Queue 接口的子接口 , 它代表一个双端队列, Deque 接口里定义了 一些双端队列的方法,这些方法允许从两端来操作队列的元素。

  • void addFirst(Object e): 将指定元素插入该双端队列的开头 。
  • void addLast(Object e): 将指定元素插入该双端队列的末尾 。
  • Iterator descendingIterator(): 返回该双端队列对应的迭代器,该法代器将以逆向顺序来法代队列 中的元素 。
  • Object getFirst(): 获取但不删除双端队列的第 一个元素 。
  • Object getLast(): 获取但不删除双端队列的最后 一个元素 。
  • boolean offerFirst(Object e): 将指定元素插入该双端队列的开头 。
  • boolean offerLast(Object e): 将指定元素插入该双端队列的末尾 。
  • Object peekFirst(): 获取但不删除该双端队列的第 一个元素:如果此双端队列为 空 ,则返回 null 。
  • Object peekLast(): 获取但不删除该双端队列的最后 一个元素:如果此双端队列为空,则返回 null 。
  • Object pollFirst(): 获取并删除该双端队列的第 一个元素;如果此双端队列为空,则返回 null 。
  • Object pollLast() : 获取并删除该双端队列的最后 一个元素;如果此双端队列为空,则返回 null 。
  • Object pop() (栈方法) : pop 出该双端队列所表示的校的技顶元素 。 相当于 removeFirstO 。
  • void push(Object e) (栈方法) : 将 一 个元素 push 进该双端队列所表示的拢的技顶 。 相当于addFirst(e) 。
  • Object removeFirst(): 获取并删除该双端队列的第一个元素 。
  • Object removeFirstOccurrence(Object o): 删除该双端队列的第一次出现的元素 。
  • Object removeLast(): 获取并删除该双端队列的最后一个元素 。
  • boolean removeLastOccurrence(Object o): 删除该双端队列的最后一次出现的元素。

Deque 不仅可以 当成双端队列使用,而且可以被当成栈来使用,因为该类 里还包含了 pop ( 出栈)、 push (入栈)两个方法 。

Deque 的方法与 Queue 的方法对照表

Deque 的方法与 Stack 的方法对照表

API:java.util.Deque

Deque 接口提供了 一个典型的实现类: ArrayDeque ,从该名称就可以看出 , 它是一个基于数组实现的双端队列,创建 Deque 时同样可指定一个 numElements 参数 , 该参数用于指定 Object[]数组的长度 :如果不指定 numElements 参数, Deque 底层数组的长度为 16 。

ArrayList 和 ArrayDeque 两个集合类的实现机制基本相似,它们的底层都采用一个动态的、可重分配的 Object[]数纽来存储集合元素,当集合元素超出了该数组的容量时,系统会在底层重新分配一个 Object[]数组来存储集合元素 。

 下面程序示范了把 ArrayDeque 当成"栈"来使用 :

ArrayDequeStack.java

public class ArrayDequeStack
{
	public static void main(String[] args)
	{
		ArrayDeque stack = new ArrayDeque();
		// 依次将三个元素push入"栈"
		stack.push("疯狂Java讲义");
		stack.push("轻量级Java EE企业应用实战");
		stack.push("疯狂Android讲义");
		// 输出:[疯狂Android讲义, 轻量级Java EE企业应用实战, 疯狂Java讲义]
		System.out.println(stack);
		// 访问第一个元素,但并不将其pop出"栈",输出:疯狂Android讲义
		System.out.println(stack.peek());
		// 依然输出:[疯狂Android讲义, 疯狂Java讲义, 轻量级Java EE企业应用实战]
		System.out.println(stack);
		// pop出第一个元素,输出:疯狂Android讲义
		System.out.println(stack.pop());
		// 输出:[轻量级Java EE企业应用实战, 疯狂Java讲义]
		System.out.println(stack);
	}
}

 ArrayDeque也可以当成队列使用,此处 AπayDeque 将按"先进先出"的方式操作集合元素。例如如下程序 :

ArrayDequeQueue.java

public class ArrayDequeQueue
{
	public static void main(String[] args)
	{
		ArrayDeque queue = new ArrayDeque();
		// 依次将三个元素加入队列
		queue.offer("疯狂Java讲义");
		queue.offer("轻量级Java EE企业应用实战");
		queue.offer("疯狂Android讲义");
		// 输出:[疯狂Java讲义, 轻量级Java EE企业应用实战, 疯狂Android讲义]
		System.out.println(queue);
		// 访问队列头部的元素,但并不将其poll出队列"栈",输出:疯狂Java讲义
		System.out.println(queue.peek());
		// 依然输出:[疯狂Java讲义, 轻量级Java EE企业应用实战, 疯狂Android讲义]
		System.out.println(queue);
		// poll出第一个元素,输出:疯狂Java讲义
		System.out.println(queue.poll());
		// 输出:[轻量级Java EE企业应用实战, 疯狂Android讲义]
		System.out.println(queue);
	}
}

LinkedList 也实现了 Deque 接口,可以被当成双端队列来使用,因此既可以被当成"栈"来使用 ,也可以当成队列使用 。

API:java.util.ArrayDeque

各种线性表的性能分析

Java 提供的 List 就是一个线性表接口,而ArrayList、LinkedList 又是线性表的两种典型实现 : 基于数组的线性表和基于链的线性表。 Queue 代表了队列, Deque 代表了双端队列(既可作为队列使用, 也可作为栈使用) 。

一般来说,

  • 由于数组以一块连续内存区来保存所有的数组元素,所以数组在随机访问时性能最好,所有的内部以数组作为底层实现的集合在随机访问时性能都比较好;
  • 而内部以链表作为底层实现的集合在执行插入、删除操作时有较好的性能 。

但总体来说, ArrayList 的性能比 LinkedList 的性能要好 , 因此大部分时候都应该考虑使用ArrayList。

 关于使用 List 集合有如下建议:

  • 如果需要遍历 List 集合元素,对于 ArrayList 、 Vector 集合,应该使用随机访问方法 (get) 来遍历集合元素,这样性能更好;对于 LinkedList 集合 ,则应该采用法代器 (Iterator ) 来遍历集合元素。
  • 如果 需要经常执行插入、删除操作来改变包含大量数据的 List 集合的大小,可考虑使用LinkedList 集合 。 使用 ArrayList 、 Vector 集合可能需要经常重新分配内部数组的大小, 效果可能较差 。
  • 如果有多个线程需要同时访 问 List 集合中的元素,开发者可考虑使用 Collections 将集合包装成线程安全的集合 。

参考: 【1】:《疯狂Java讲义》 【2】:廖雪峰的官方网站:使用Queue 【3】:廖雪峰的官方网站:使用PriorityQueue 【4】:廖雪峰的官方网站:使用Deque

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java Review (二十五、集合----- Iterator接口)

    Iterator接口 也是 Java 集合框架的成员 , 但它与 Collection 系列 、 Map 系列 的集合不 一样 : Collection系列集合...

    三分恶
  • 重学数据结构(三、队列)

    和上一篇的栈相反,队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。

    三分恶
  • CopyOnWriteArrayList源码阅读笔记

    ArrayList是开发中使用比较多的集合,它不是线程安全的,CopyOnWriteArrayList就是线程安全版本的ArrayList。CopyOnWrit...

    三分恶
  • Java集合框架(四)—— Queue、LinkedList、PriorityQueue

    Queue接口   Queue用于模拟了队列这种数据结构,队列通常是指“先进先出”(FIFO)的容器。队列的头部保存在队列中时间最长的元素,队列的尾部保存...

    郭耀华
  • Java集合--Queue(Java中实现2)

    贾博岩
  • 简单介绍python的双向队列

      大家都知道利用 .append 和 .pop 方法,我们可以把列表当作栈或者队列来用(比如,把 append 和 pop(0) 合起来用,就能模拟栈的“先进...

    用户1217611
  • 数据结构 | Java 队列 —— Queue 详细分析

    摘要: 原创出处 https://www.cnblogs.com/lemon-flm/p/7877898.html 「低调人生」欢迎转载,保留摘要,谢谢!

    芋道源码
  • DB 从算法理解 DB 原理 --- 比较重组问题

    最近数据库学习中,体会到数据库中大大小小的数据处理,都离不开数据算法,有效的开始理解一些算法会对某些数据库设计中的理念会更深入的理解。

    AustinDatabases
  • python算法与数据结构-队列(44)

      队列的定义:队列是一种特殊的线性表,只允许在表的头部(front处)进行删除操作,在表的尾部(rear处)进行插入操作的线性数据结构,这种结构就叫做队列。进...

    Se7eN_HOU
  • DevOps如何解决技术债务挑战?

    许多组织在迁移到云期间发现了大量的技术债务。但是什么是技术债务呢?DevOps如何帮助我们去解决技术债务呢?在这篇文章中,我们将讨论使用DevOps将您的技术债...

    泽阳

扫码关注云+社区

领取腾讯云代金券