Java集合框架(四)—— Queue、LinkedList、PriorityQueue

  • Queue接口

  Queue用于模拟了队列这种数据结构,队列通常是指“先进先出”(FIFO)的容器。队列的头部保存在队列中时间最长的元素,队列的尾部保存在队列中时间最短的元素。新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。通常,队列不容许随机访问队列中的元素。

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

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

Queue有两个常用的实现类LinkedList和PriorityQueue,下面分别介绍这两个实现类。

  • LinkedList

LinkedList类是一个比较奇怪的类,它即是List接口的实现类,这意味着它是一个List集合,可以根据索引来随机访问集合中的元素。除此之外,LinkedList还实现了Deque接口,Deque接口是Queue接口的子接口,它代表一个双向队列,Deque接口里定义了一些可以双向操作队列的方法:

  1. void addFirst(Object e);     //将指定元素插入该双向队列的开头。
  2. void addLast(Object e);  //将指定元素插入该双向队列的末尾。
  3. Iterator descendingIterator();  //返回以该双向队列对应的迭代器,该迭代器将以逆向顺序来迭代队列中的元素。
  4. Object getFirst();      //获取、但不删除双向队列的第一个元素。
  5. Object getLast();             //获取、但不删除双向队列的最后一个元素。
  6. boolean offerFirst(Object e);//将指定元素插入该双向队列的开头
  7. boolean offerLast(Object e);//将指定元素插入该双向队列的结尾
  8. Object peekFirst();             //获取、但不删除双向队列的第一个元素;如果此双端队列为空,则返回null。
  9. Object peekLast();             //获取、但不删除该双向队列的最后一个元素;如果此双端队列为空,则返回null。
  10. Object pollFirst();              //获取、并删除双向队列的第一个元素;如果此双端队列为空,则返回null。
  11. Object pollLast();              //获取、并删除双向队列的最后一个元素,如果此双端队列为空,则返回null。
  12. Object pop();                    //pop出该双向队列所表示的栈中第一个元素。
  13. void push(Object e);          //将一个元素push进该双向队列所表示的栈中。
  14. Object removeFirst();        //获取、并删除该双向队列的第一个元素。
  15. Object removeFirstOccurrence(Object e);   //删除该双向队列的第一次的出现元素e。
  16. removeLast();                      //获取、并删除该双向队列的最后一个元素。
  17. removeLastOccurrence(Object e);    //删除该双向队列的最后一次的出现元素e

  从以上方法可以看出,LinkedList不仅可以当成双向队列使用,也可以当成“栈”使用,因为该类还包含了pop(出栈)和push(入栈)两个方法。除此之外,LinkedList实现了List接口,所以还被当成List使用。

*建议:

  1. 如果需要遍历List集合元素,对于ArrayList、Vector集合,则应该使用随机访问方法(get)来遍历集合元素,这样性能更好,对于LinkedList集合,则应该采用迭代器(Iterater)来遍历集合元素。
  2. 如果需要经常执行插入、删除操作来改变List集合大小,则应该使用LinkedList集合,而不是ArrayList。使用ArrayList、Vector集合将需要经常重新分配内存数组的大小,其时间开销往往是使用LinkedList时时间开销的几十倍,效果很差。
  3. 如果有多条线程需要同时访问List集合中的元素,可以考虑使用Vector这个同步实现。
  • PriorityQueue实现类

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

public class Test {
    public static void main(String[] args){
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
            pq.offer(3);
            pq.offer(-6);
            pq.offer(9);
            //打印结果为[-6, 3, 9]
            System.out.println(pq);
            //打印结果为-6
            System.out.println(pq.peek());
            //打印结果为-6
            System.out.println(pq.poll());
    }
}

   PriorityQueue不允许插入null元素,它还需要对队列元素进行排序,队列元素有两种排序方式:自然排序、定制排序; 关于使用自然排序和定制排序与前面讲到的TreeSet集合一样,读者可以查看Java集合(二)这章的内容

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏赵俊的Java专栏

合并排序数组 Ⅱ

1584
来自专栏Java成长之路

深入理解String类

String是java中的字符串。String类是不可变的,对String类的任何改变,都是返回一个新的String类对象。String不属于8种基本数据类型,...

672
来自专栏java学习

面试题53(考察求职者对String声明变量在jvm中的存储方法)

(单选题) 1、有如下一段代码,请选择其运行结果() public class StringDemo{ private static final Stri...

2963
来自专栏老马说编程

(89) 正则表达式 (中) / 计算机程序的思维逻辑

上节介绍了正则表达式的语法,本节介绍相关的Java API。 正则表达式相关的类位于包java.util.regex下,有两个主要的类,一个是Pattern,另...

1967
来自专栏三木的博客

Javascript中的数组

数组的定义: var colors = new Array(20); var colors = new Array('red');  // ['red'...

22010
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题22栈的压入、弹出序列

本题的详细分析过程均在代码的注释中: import java.util.Stack; /** * 题目:输入两个整数序列,第一个序列表示栈的压入顺序,请判断...

2977
来自专栏Netkiller

Java 反射,开发框架必备技能

反射一般开发者接触不到,反射主要用户框架的开发。例如我举一个例子你就明白了: http://www.netkiller.cn/news/list/2.html...

2815
来自专栏AILearning

字符串的学习

1> “==”与“equals”的区别 “==”判断的是两个字符串对象在内存中的首地址,就是判断是否是同一个字符串对象; 而equals()判断的是两个字符串对...

1925
来自专栏微信公众号:Java团长

Java正则表达式入门

1.定义:正则表达式是一种可以用于模式匹配和替换的规范,一个正则表达式就是由普通的字符(例如字符a到z)以及特殊字符(元字符)组成的文字模式,它 用以描述在查...

922
来自专栏维C果糖

详述 Java 语言中的 String、StringBuffer 和 StringBuilder 的使用方法及区别

1 简介 在 Java 语言中,共有 8 个基本的数据类型,分别为:byte、short、int、long、float、double、boolean和char,...

2105

扫码关注云+社区

领取腾讯云代金券