绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
Java集合源码分析之Queue(一):Queue与Deque
2020-04-29 09:36:02

在日常生活中,排队几乎随处可见,上地铁要排队,买火车票要排队,就连出门吃个大餐,也要排队。。。之前研究的ArrayList就像是一个缺乏管理的排队系统。大家虽然会排队,但一会走个人,大家向前挪一挪,一会插个人,大家向后挪一挪,碰到这样的队伍,一定让人痛苦万分吧?

今天要介绍的Queue就不同了,它是一个严格的排队系统。就像许多火车站排队窗口在两侧加了护栏一样,大家只能从队尾进来,从队首离开,我们称之为FIFO(first in first out),也就是先进来的人先离开。Queue就严格遵循了这个原则,使插队和提早离开变得不可能。

当然Queue也有很多变种,FIFO并不是其可以遵循的唯一规则。比如Stack(栈),就遵循LIFO(last in first out),这就好比我们叠碗一样,后来者居上。还有我们之后要分析的Deque,其允许元素从两端插入或删除,比如排队进站时总有人说,“我能不能插个队,我赶时间?”。

超级接口Queue

队列在软件开发中担任着重要的职责,java函数的调用用到了栈的技术,在处理并发问题时,BlockingQueue很好的解决了数据传输的问题。接下来我们看看Java是如何定义队列的吧。

首先,Queue也继承自Collection,说明它是集合家族的一员。Queue接口主要提供了以下方法:

//将元素插入队列
boolean add(E e);

//将元素插入队列,与add相比,在容量受限时应该使用这个
boolean offer(E e);

//将队首的元素删除,队列为空则抛出异常
remove();

//将队首的元素删除,队列为空则返回null
poll();

//获取队首元素,但不移除,队列为空则抛出异常
element();

//获取队首元素,但不移除,队列为空则返回null
peek();

超级实现类AbstractQueue

Queue的定义很简单,所以其实现类也很简单,用简单的代码做复杂的事情,值得我们学习。

AbstractQueue仅实现了addremoveelement三个方法,并且分别调用了另外一个仅细微区别的方法,我们这里只看其一

//这里我们就明白,对于有容量限制的,直接调用offer肯定会更快
public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

此外,它还实现了clearaddAll方法,重写这些方法可以使其更符合当前场景。

public void clear() {
    while (poll() != null)
        ;
}

public boolean addAll(Collection<? extends E> c) {
    if (c == null)
        throw new NullPointerException();
    if (c == this)
        throw new IllegalArgumentException();
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}


接口Deque

Deque全称为double ended queue,即双向队列,它允许在两侧插入或删除元素,同时也建议我们不要向其中插入null值。除此之外,其余特性则和父级Queue类似。Deque大多数情况下不会限制元素的数量,但这不是必须的。

Deque中定义的方法主要分为四部分,第一部分就如Deque定义所言,提供两侧插入或删除的方法。第二部分是继承自Queue的实现。第三部分表示如果要基于此实现一个Stack,需要实现的方法。最后一部分是继承自Collection的方法。

两侧插入、删除

这里方法和Queue定义方式一致,但却是针对两侧插入删除的。

//在队首添加元素
void addFirst(E e);
//在队首添加元素
boolean offerFirst(E e);

//在队尾添加元素
void addLast(E e);
boolean offerLast(E e);

//删除队首元素
removeFirst();
pollFirst();

//删除队尾元素
removeLast();
pollLast();

//获取队首元素
getFirst();
peekFirst();

//获取队尾元素
getLast();
peekLast();

//删除第一个事件,大多数指的是删除第一个和 o equals的元素
boolean removeFirstOccurrence(Object o);
//删除最后一个事件,大多数指的是删除最后一个和 o equals的元素
boolean removeLastOccurrence(Object o);

与Queue对应的方法

因为Queue遵循FIFO,所以其方法在Deque中对应关系有所改变,结合Deque的定义,我们很容易就想到它们的对应关系:

//与addLast(E e)等价
boolean add(E e);

//与offerLast(E e)等价
boolean offer(E e);

//与removeFirst()等价
remove();

//与pollFirst()等价
poll();

//与getFirst()等价
element();

//与peekFirst()等价
peek();

实现Stack

Stack仅在一侧支持插入删除操作等操作,遵循LIFO原则。

//与addFirst()等价
void push(E e);

//与removeFirst()等价
pop();

继承于Collection的方法

这里主要关注两个方法。

//顺序是从队首到队尾
Iterator<E> iterator();

//顺序是从队尾到队首
Iterator<E> descendingIterator();


Collection三大框架之二就介绍到这里了,接下来我们就可以了解LinkedList的原理了。不过在此之前,我们要先看一个应用不太广泛,但思想很重要的实现类:ArrayDeque,用数组实现的双向队列,你可能没有听过它,但却有必要了解它。


更多文章正在


分享好友

分享这个小栈给你的朋友们,一起进步吧。

飞机酱的IT之旅
创建时间:2020-04-28 18:20:39
飞机酱是一个Android开发攻城狮,除了要攻陷Android外,还会进攻数据结构、算法、网络、计算机系统等方面的知识。关注我,一起学IT吧。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 大大纸飞机
    栈主

小栈成员

查看更多
  • ☀️
  • 小雨滴
  • 人工智能频道
  • 栈栈
戳我,来吐槽~