Java - [容器]Queue

2020/03/07

Update 2020_0425

本文主要介绍下Java集合中的队列,整体关系图如下:

再来看下Queue接口中的六个方法:

接下来从四个维度分析三种队列:

PriorityQueue

PriorityQueue根据元素的大小进行重新排序,而不是维护了元素插入的原始顺序

@Test
void priorityQueueTest(){
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    /** offer() and add() **/
    pq.offer(5);
    pq.offer(2);
    pq.offer(3);
    pq.offer(1);
    pq.offer(1);
    // pq.offer(null);

    /** peek() and element() **/
    System.out.println("Just peek: " + pq.peek());

    /** poll() and remove() **/
    System.out.println(pq);
    while (!pq.isEmpty()){
        System.out.println("Do   poll: " + pq.poll());
    }
}

// Just peek: 1
// [1, 1, 3, 5, 2]
// Do   poll: 1
// Do   poll: 1
// Do   poll: 2
// Do   poll: 3
// Do   poll: 5

可以得出以下结论:

  • 是否允许添加null
  • 是否允许添加重复元素?
  • 是否维持插入顺序?
  • 是否线程安全?

ArrayDeque

ArrayDeque代表一个双端队列,可同时实现队列

下面来看下三者对应的方法:

再来看下具体代码实现:

@Test
void arrayDequeTest(){
    /** As stack **/
    System.out.println("/** As stack **/");
    ArrayDeque<Integer> adStack = new ArrayDeque<>();
    adStack.push(5); // addFirst()
    adStack.push(2);
    adStack.push(3);
    adStack.push(3);
    // adStack.push(null);
    System.out.println(adStack);

    while (!adStack.isEmpty()){
        System.out.println("Polled element in adStack is " + adStack.poll()); // pollFirst()
    }

    System.out.println("/** As queue **/");
    /** As queue **/

    ArrayDeque<Integer> adQueue = new ArrayDeque<>();
    adQueue.offer(5); // offerLast()
    adQueue.offer(2);
    adQueue.offer(3);
    System.out.println(adQueue);
    while (!adQueue.isEmpty()){
        System.out.println("Polled element in adQueue is " + adQueue.poll()); // pollFirst();
    }
}
// /** As stack **/
// [3, 3, 2, 5]
// Polled element in adStack is 3
// Polled element in adStack is 3
// Polled element in adStack is 2
// Polled element in adStack is 5
// ------------------------------
// /** As queue **/
// [5, 2, 3]
// Polled element in adQueue is 5
// Polled element in adQueue is 2
// Polled element in adQueue is 3

可以得出以下结论:

  • 是否允许添加null
  • 是否允许添加重复元素?
  • 是否维持插入顺序? 否,栈[LIFO: Last In First Out]、队列[FIFO: First In First Out]
  • 是否线程安全?

LinkedList

这个类很厉害,同时实现了ListDeque接口。

有个问题: ArrayQueueLinkedList的区别是什么?

其实看名称就能猜出一二,

前者内部是用的是一个Object[]数组保存集合中的元素,因此随机访问元素时性能更好;

而后者用链表保存集合中的元素,所以插入删除元素时性能更佳。

@Test
void linkedListTest(){
    LinkedList<Integer> ll = new LinkedList<>();
    ll.add(5);
    ll.add(2);
    ll.add(3);
    ll.add(3);
    ll.add(null);
    System.out.println(ll);
    // [5, 2, 3, 3, null]
}
  • 是否允许添加null
  • 是否允许添加重复元素?
  • 是否维持插入顺序?
  • 是否线程安全?

总结:

Reference

  • 《疯狂Java讲义》 - 8.5 Queue集合


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory