020 线性表、栈、队列和优先队列

本文为《Java 语言程序设计》第十版 章节笔记

20.1 引言

数据结构（data structure）是以某种形式将数据组织在一起的合集（collection）。数据结构不仅储存数据，还支持访问和处理数据的操作。

在面向对象思想里，一个数据结构也被认为是一个容器（container）或者容器对象（container object），它是一个能存储其他对象的对象，这里的其他对象称为数据或者元素。

定义一种数据结构从本质上讲就是定义一个类。数据结构类应该使用数据域存储数据，并提供方法支持查找、插入和删除等操作。
因此，创建一个数据结构就是创建这个类的一个实例。然后，可以使用这个实例上的方法了操作这个数据结构，例如，向该数据结构中插入一个元素，或者从这个数据结构中删除一个元素。

Java 中的数据结构通常统称称为 Java 合集框架（Java Collections Framework）。

20.2 合集

Java 合集框架支持的两种类型的容器

• 一种是为了存储一个元素合集，简称为 合集（collection）。
• 另一种是为了存储 键/值 对，称为 映射表（map）。

映射表是一个使用一个键（key）快速搜索一个元素的高效数据结构。

Collection 接口为 线性表、集合、栈、向量、队列、优先队列定义了共同的操作。

合集的一些数据结构

• 线性表 List：存储一个有序元素合集
• 集合 Set：存储一组不重复的元素
• 栈 Stack ：存储采用后进先出方式处理的对象
• 队列 Queue： 存储采用先进先出方式处理的对象
• 优先队列 Priority Queue ：存储按照优先级顺序处理的对象

在 Java 合集框架中定义的所有接口和类都分组在 java.util 包中。

合集框架的通用特性：

<interface>java.util.Collection<E>
+add(o: E): boolean
+addAll(c: Collection<? extends E>): boolean
+clear(): void
+contains(o: Object): boolean
+containsAll(c: Collection<?>): boolean
+equals(o: Object): boolean
+hashCode(): int
+isEmpty(): boolean
+remove(o: Object): boolean
+removeAll(c: Collection<?>): boolean
+retainAll(c: Collection<?>): boolean
+size(): int
+toArray(): Object[]

除开 java.tuil.PriorityQueue 没有实现 Cloneable 接口外，Java 合集框架中的其他具体类都实现了 java.lang.Cloneable 和 java.io.Serializable 接口。

20.3 迭代器

每种合集都是可迭代的（Iterable）（包括 map）。

<interface>java.lang.Iterable<E>
+iterator(): Iterator<E>

<interface>java.util.Iterator<E>
+hasNext(): boolean
+next(): E
+remove(): void

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class TestIterator {
    public static void main(String[] args){
        Collection<String> collection = new ArrayList<>();
        collection.add("New York");
        collection.add("Atlanta");
        collection.add("Dallas");
        collection.add("Madison");

        Iterator<String> iterator = collection.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next().toUpperCase() + " ");
        }

        System.out.println("------------------------");
        for (String element:collection) {
            System.out.println(element.toUpperCase() + " ");
        }
    }
}

Collection 接口继承自 Iterable 接口。Iterable 接口中定义了 iterator 方法，该方法会返回一个迭代器。

20.4 线性表

List 接口继承自 Colletion 接口，定义了一个用于 顺序存储 元素的合集，其中元素 允许重复。有两个具体类 ArrayList、LinkedList。

20.4.1 List 接口中的通用方法

List 接口增加了面向位置的操作，和一个能够双向遍历线性表的新线性表迭代器。

+add(index: int, element: Object): boolean
+addAll(index: int, c: Collection<? extends E>): boolean
+get(index: int): E
+indexOf(element: Object): int
+lastIndexOf(element: Object): int
+listIterator(): ListIterator<E>
+listIterator(startIndex: int): ListIterator<E>
+remove(index: int): E
+set(index: int, element: Object): Object
+subList(fromIndex: int, toIndex: int): List<E>

ListIterator 接口继承了 Iterator 接口，以增加对线性表的双向遍历能力。ListIterator 接口中的方法：（还不怎么理解这里的方法）

<interface>java.util.ListIterator<E>
+add(element: E): void
+hasPrevious(): boolean

+nextIndex(): int
+previous(): E
+previousIndex(): int
+set(element: E): void

20.4.2 数组线性表类 ArrayList 和 链表类 LinkedList

• ArrayList 用数组存储元素，这个数组是动态创建的。
• LinkedList 在一个链表（linked list）中存储元素。

一般只查询线性表里的元素，使用 ArryaList 实现，如果需要在起始位置插入或删除元素，使用 LinkedList 实现。

ArrayList 使用数组实现 List：

java.util.ArrayList<E>
+ArrayList()
+ArrayList(c: Collection<? extends E)

+ArrayList(initialCapacity: int)
+trimToSize(): void

LinkedList 提供从线性表两端插入、提取和删除的方法：

+LinkedList()
+LinkedList(c: Collection<? extends E)

+addFirst(element: E): void
+addLast(element: E): void
+getFirst(): E
+getLast(): E
+removeFirst(): E
+removeLast(): E

20.5 Comparator 接口

Comparator 可以用于比较没有实现 Comparable 的类的对象。

20.6 线性表和合集的静态方法

java.util.Collections
+sort(list: List): void
+sort(list: List, c: Comparator): void

+binarySearch(list: List, key: Object): int
+binarySearch(list: List, key: Object, c: Comparator): int

+reverse(list: List): void
+reverseOrder(): Comparator

+shuffle(list: List): void
+shuffle(list: List, rmd: Random): void

+copy(des: List, src: List): void
+nCopies(n: int, o: Object): List

+fill(list: List, o: Object): List

+max(c: Collection): Object
+max(c: Collection, c: Comparator): Object

+min(c: Collection): Object
+min(c: Collection, c: Comparator): Object

+disjoint(c1: Collection, c2: Collections): boolean

+frequency(c: Collection, o: Object): int

20.8 向量类和栈类

在 Java API 中，Vector 类是 AbstractList 的子类，Stack 类是 Vector 的子类。

Java 合集框架是在 Java 2 中引入的。Java 2 之前的版本也支持一些数据结构，其中就有向量类 Vector 与栈类 Stack。

除了包含用于访问和修饰向量的同步方法之外，Vector 类 与 ArrayList 是一样的。对于许多不需要同步的应用程序来说，使用 ArrayList 比使用 Vector 效率更高。

Vetor 类被广泛应用于 Java 的遗留代码中，因为在 Java 2 之前，它可以实现 Java 可变大小的数组。

java.util.Stack<E>
+Stack()
+empty(): boolean
+peek(): E
+pop(): E
+push(o: E): E
+search(o: Object): int

20.9 队列和优先队列

队列（queue）是一种先进先出的数据结构。元素被追加到末尾，然后从队列头删除。
在优先队列（priority queue）中，元素被赋予优先级。当访问元素时，拥有最高优先级的元素首先被删除。

20.9.1 Queue 接口

<interface>java.util.Queue
+offer(element: E): boolean
+poll(): E
+remove(): E
+peek(): E
+element(): E

20.9.2 双端队列 Deque 和链表 LinkedList

LinkedList 类实现了 Deque 接口，Deque 又继承自 Queue 接口。可使用 LinkedList 创建一个队列。

默认情况下，优先队列使用 Comparable 以元素的自然顺序进行排序。拥有最小数值的元素被赋予最高优先级，因此最先从队列中删除。如果有几个元素拥有相同的优先级，则任意选择一个。也可以使用构造方法 PriorityQueue(initialCapacity, comparator) 中的 Comparator 来指定一个顺序。

java.util.PriorityQueue<E>
+PriorityQueue()
+PriorityQueue(initialCapacity: int)
+PriorityQueue(c: Collection<? extends E>)
+PriorityQueue(initialCapacity: int, comparator: Comparator<? super E>)

END