Java容器框架源码阅读笔记（二）Queue、Stack

| |

java.util.Queue和java.util.Stack框架：

Queue&&Stack

Queue

1
public interface Queue<E> extends Collection<E>

介绍

  • Queue是一个队列接口，继承自Collection。定义了关于FIFO队列的相关操作。
  • Queue的子接口Deque扩展了Queue。Deque除了继承了FIFO队列的相关操作，Deque还定义了关于双端队列、栈的相关操作。
  • LinkedList、ArrayDeque通过实现Deque间接实现了Queue。
  • 在 Queue中定义了三类方法，关于每类方法(增删查)都定义了两种，区别在于出现错误后(比如删除元素/获取队头元素队列已经空了)是抛异常还是返回错误值。对于返回错误值的方法应用场景是队列长度有限制的实现类。

    Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation). The latter form of the insert operation is designed specificallyfor use with capacity-restricted Queue implementations; in most implementations, insert operations cannot fail.

operation Throws exception Returns special value
Insert add(e) offer(e)
Remove remove() poll()
Examine element() peek()

队列操作部分源码分析

主要翻译ArrayDeque中关于队列操作的具体实现。
ArrayDeque是通过数组实现了一个循环队列。队列长度可变，当数组元素满了以后，就进行2倍扩容。变量head、tail分别表示队头和队尾。head指向队头的元素位置，tail指向队尾元素的下一个位置，也就是下一个要插入的元素应该在的位置。

public boolean add(E e)

添加元素到队尾，通过(tail + 1) & (elements.length - 1)) == head判断队列是否已满(因为队列的长度是2的幂，所以可以通过位运算&来代替%)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean add(E e) {
    addLast(e);
    return true;
}

public void addLast(E e) {
	// 不允许添加null
	if (e == null)
        throw new NullPointerException();
    // 将元素插入到队尾元素的后面
    elements[tail] = e;
    // 判断队列是否已经满了，将队列长度设置为2的幂，可以用位运算代替取模运算
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
    	// 满了以后进行2倍扩容，所以判断队列满和队列空 用head == tail不冲突，因为队列不会满，一旦由于添加元素导致head == tail时，就会进行二倍扩容，保证tail不会因为添加元素【最终】指向head
        doubleCapacity();
}

public E element()

获取队头元素，没有通过head == tail判断队列是否为空，而是通过取得head指针指向的元素是否为空来判断队列是否为空。

如果队列为空，element()会抛异常。对应的peek()会返回null。

1
2
3
4
5
6
7
8
9
10
11
12
13
public E element() {
    return getFirst();
}

public E getFirst() {
    @SuppressWarnings("unchecked")
    // 获取头指针head指向的队头元素
    E result = (E) elements[head];
    // 如果获取的元素是null，直接抛出异常。
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

public E remove()

删除队头元素，没有通过head == tail判断队列是否为空，而是通过取得head指针指向的元素是否为空来判断队列是否为空。

如果队列为空，remove()会抛异常。对应的poll()会返回null。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public E remove() {
    return removeFirst();
}

public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

public E pollFirst() {
	// 获取head指针
    int h = head;
    @SuppressWarnings("unchecked")
    // 获取队头元素
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    // 将队头变量置空(删除)
    elements[h] = null;     // Must null out slot
    // 修改head指针
    head = (h + 1) & (elements.length - 1);
    return result;
}

Stack

1
public class Stack<E> extends Vector<E>

介绍

Stack继承自Vector，是一个LIFO的线性数据结构，只能在栈顶进行操作。通过Vector实现了关于栈的基本操作，当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque。

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque<Integer> stack = new ArrayDeque<Integer>();

个人观点:

  • 原生的Stack是继承是Vector，而Vevtor中的每个方法是加了锁的，所以在效率上可能会降低。不过在JDK6已经对synchronized做了优化，没对比过。
  • 栈和队列都是在一端或两端操作，不会直接对中间元素操作(删除，添加)，所以可以避免数组操作中间元素产生较大的时间开销，再就是数组占用的内存在物理上是连续的，所以能更好的用到局部性原理吧。

栈操作部分源码分析

主要翻译ArrayDeque中关于栈操作的具体实现。

public void push(E e)

入栈 

1
2
3
4
5
6
7
8
9
10
11
12
13
public void push(E e) {
    addFirst(e);
}

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    // 放在head指向的元素之前，然后栈顶指针往 "前" 循环走
    elements[head = (head - 1) & (elements.length - 1)] = e;
    // 当head和tail相遇，说明栈满，需要扩容。
    if (head == tail)
        doubleCapacity();
}

public E pop()

出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public E pop() {
    return removeFirst();
}

public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // 如果栈是空的，最终获取的元素就是null
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    // 栈顶指针往 "后" 循环走
    head = (h + 1) & (elements.length - 1);
    return result;
}

Q&A

FIFO队列和栈的区别？

  • 队列是一个先进先出(First In First Out)的线性数据结构。可以在队头和队尾进行操作。
  • 栈是一个后进先出(First In Last Out)的线性数据结构。只能在栈顶进行操作。
Related Posts