Abstract Data Types (ADTS)

ADTS 是由其行为属性定义的抽象类型, 跟如何实现无关.

堆栈 Stacks 和队列 Queues 是两种类似的线性集合。堆栈是后进先出的ADT：元素总是从数据结构的一端添加或删除。队列是先进先出的ADT. 二者都支持以下操作: push(): 加入 peek(): 返回下一个 poll(): 返回下一个并删除

Java的Deque(double ended queue, “deck”) 接口融合了堆栈和队列, 支持两端的元素插入和移除. ArrayDeque和LinkedListDeque都是实现deque这个接口，deque只是罗列了一些 methods，也即是一种合约，保证会实现的行为。而这些方法的具体实现则是由ArrayDeque和LinkedListDeque完成。从概念上讲，deque就是一种抽象的数据类型，只说会有什么行为，但不体现这些行为的具体实现方式，所以是抽象的。

优先级队列 priority queue 的每个元素都有一个与之关联的优先级，以决定从队列中元素操作的顺序。

三种方式实现Stack的push(Item x):

  1. 继承模式：extends LinkedList<Item>以使用其方法:
public class ExtensionStack<Item> extends LinkedList<Item> {
    public void push(Item x) {
        add(x);
    }
}
  1. 委托模式Delegation， 生成Linked List并调用其方法来达到目的
public class DelegationStack<Item> {
    private LinkedList<Item> L = new LinkedList<Item>();
    public void push(Item x) {
        L.add(x);
    }
}
  1. 类似委托模式, 只是这里可以利用任何实现了List接口的类, 如Linked List, ArrayList, 等等
public class StackAdapter<Item> {
    private List L;
    public StackAdapter(List<Item> worker) {
        L = worker;
    }

    public void push(Item x) {
        L.add(x);
    }
}

Delegation vs Extension: Extension 一般是基于对父类有比较清楚的了解认知下才会使用。此外，扩展基本上等于在说明正在扩展的类与被扩展类是相似的。如果两个类无法看做是同属的, 那么就用委托模式。

Views: 通过视图进行的更改会影响底层对象。

/** Create an ArrayList. */
List<String> L = new ArrayList<>();
/** Add some items. */
L.add(“at”); L.add(“ax”); …
List<String> SL = l.subList(1, 4);
/** Mutate that thing. */
SL.set(0, “jug”);

API’s

An API(Application Programming Interface) of an ADT is the list of constructors and methods and a short description of each.

API 包括语法规范和语义规范

  • 编译器确认语法符合要求
  • 测试以帮助确认语义描述是否正确

Java Libraries

Java有一些内置的抽象数据类型，打包在Java库中。 三个最重要的ADTs来自java.util库：

  • List 列表：一个有序的元素集合，如ArrayList
  • Set 集合：元素严格唯一（不重复）的(无序)集合，如HashSet
  • Map 映射：A collection of Key - value 映射, key是唯一的。通过key访问value，如HashMap。
/** takes in a String inputFileName
and puts every word from the input file into a list*/
public static List<String> getWords(String inputFileName) {
    List<String> lst = new ArrayList<String>();
    In in = new In();
    while (!in.isEmpty()) {
        lst.add(in.readString());
    }
    return lst;
}

/** takes in a List<String> and counts how many unique words there are in the file.*/
public static int countUniqueWords(List<String> words) {
    Set<String> ss = new HashSet<>();
    for (String s : words) {
           ss.add(s);
    }
    return ss.size();
}

/** takes in a List<String> targets and a List<String> words,
and finds the number of times each target word appears in the word list.*/
public static Map<String, Integer> collectWordCount(List<String> words) {
    Map<String, Integer> counts = new HashMap<String, Integer>();
    for (String t: target) {
        counts.put(s, 0);
    }
    for (String s: words) {
        if (counts.containsKey(s)) {
            counts.put(word, counts.get(s)+1);
        }
    }
    return counts;
}

通过设置环境变量（如CLASSPATH = ）让Java编译器/解释器知道去哪里找 libraries。

CLASSPATH：Linux or MacOS, paths are separated by :. In Windows, paths are separated by ;.

  • /home/--/--/javalib/*, 在.class和.jar文件内查找依赖包，用于指定绝对路径。有同名时，会根据环境变量的先后顺序去排序靠前的。
  • ./指当前目录，../指上一层目录，用于指定相对路径。
  • 也可以指定classpath, 这样系统的CLASSPATH会被忽略: javac -cp ./:/home/stuff/:../ Foo.java, 当有重名时, 选择顺序就是指明的路径顺序（当前目录-stuff目录-上一层目录）

IntelliJ会忽略CLASSPATH，它会自动调用-cp, 变量是基于当前项目指定的 libraries.

/** 查看 IntelliJ 使用的 classpath*/
import java.net.URL;
import java.net.URLClassLoader;

public static void main(String[] args) {
    ClassLoader cl = ClassLoader.getSystemClassLoader();

    URL[] urls = ((URLClassLoader)cl).getURLs();

    for(URL url: urls){
        System.out.println(url.getFile());
    }
}

Build Systems：可以简单地将文件放入适当的位置，然后通过 Maven, Ant 和 Gradle 等工具使用 Build Systems 来自动设置项目, 省去了手动加载一长串 libraries.