算法

Algs4笔记（二） --- 背包、队列与栈

课程第二周的内容介绍了三种基础数据类型，分别是背包(bag)、队列(queue)、栈(stack)，这三种集合数据类型应用广泛，是开发后续算法的基石。

API

背包是一种不支持从中删除元素的集合数据类型，作用就是收集所有元素，与数组相比初始化时可以不用知道元素的数量。队列是基于先进先出(FIFO)策略的集合数据类型，而栈是基于后进先出(LIFO)策略的集合类型。队列和栈支持删除操作，而背包只支持添加操作，可见，背包并不强调元素的顺序。队列用enqueue()方法添加元素，dequeue()方法删除最早添加的元素；栈用push()方法添加元素，用pop()方法删除最近添加的元素。

数组实现

数组是Java直接支持的数据结构，维护私有数组和指针变量就可以很好地实现API，不过前提需要知道元素的数量，但实际用例的很多情况下却无法事先预计，所以我们需要动态地调整数组。调整数组动态控制内存使用，在数组快溢出时将其加倍，数组太大时将其长度减半。

1
2
3
4
5
6
private void resize(int max) {
    Item[] temp = (Item[]) new Object[max];
    for (int i = 0; i < N; i++)
    	temp[i] = a[i];
    a = temp;
}

需要注意的是，实现删除操作时应在元素数量小于数组的四分之一时将其减半，如此一来可以避免多次调整数组。调整数组的实现，咋一看每次改变时都需对新数组初始化，所需成本很高，但每次调整都是2的次幂，均摊后每次操作的成本还是挺廉价的，可以保障方法的性能。

链表实现

链表是一种递归数据结构，由系列结点构成，每个结点包含一个元素和指向另一条链表的引用，scheme中的序对便是链表。

1
2
3
4
private class Node {
    Item item;
    Node next;
}

从Node类的实现代码中可以看出链表是递归数据结构，使用时就像递归程序一样，简洁优雅。值得注意的是，内部Node类并不是抽象数据类型。在Node类中，我们没有定义任何方法，没有构造函数也没有选择函数，使用时我们直接引用其实例变量，意在强调我们只使用了Node类。
有了链表，实现API就很容易了，链表实现的队列和栈可以处理任意数据类型，所需的空间和集合的大小成正比，每个操作的时间总是和集合的大小无关，我们达到了最优设计目标。

API的两种实现都可以很好地保证性能，链表实现可以保证即便是最坏情况下每个操作仍可在常数时间内完成，但需额外时间和内存处理链接，相比数组实现使用更少的空间，代价是每个操作只能在均摊成本下得到保证。
在队列和栈的数组实现和链表实现中删除与删除元素相关的代码就是背包API的实现，当然，在需要背包的地方，我们也可以使用队列或栈。