数据结构Stack

​ 在很多应用中，我们需要维护多个对象的集合，这种操作非常简单。我们可能想要向集合中 加入某个元素，去掉某个元素，以及遍历 集合中的元素并对他们执行某种操作，当然还有 检查集合是否为空。对于大多数操作来说，目的都很明确 关键是当需要去掉一个元素时，去掉哪一个元素呢？处理这类问题 有两个经典基础数据结构，栈和队列。

​ 它们的区别就在于 去除元素的选择方式。在栈中，我们取出 最近加入的元素。插入元素对应的术语是入栈（push） 去掉最近加入的元素叫做出栈（pop）。这也叫做后进先出原则 ( LIFO )。在队列中，我们关注最先加入队列的元素 为了和栈的操作区分，队列加入元素的操作叫做入队（enqueue） 去除元素的操作叫做出队（dequeue）。这也叫做先入先出原则 (FIFO)

​ 如何实现这些操作 ,我们今天隐含的主题是模块式编程。这也将是我们需要特别遵守的原则,这一原则主要思想是将接口与实现完全分离,比如我们精确定义了一些如栈、队列等数据结构的时候和数据类型，我们想要的是实现的细节与客户端的 完全分离。客户端可以选择不同的实现 但是客户端代码只能执行基本操作 另一方面，实现部分无法知道客户端需求的细节 它所要做的只是实现这些操作 这样，很多客户端能够共用同一个实现 这使得我们能够用模块式可复用的算法与数据结构库 来构建更复杂的算法和数据结构。在 Java 这门语言中就是使用接口俩统一 API，我们的所有实现必须遵从我们先前的 API。

​ 现在，我们来看实现栈的代码 我们要看的第一个实现使用链表。

package Stack;

public class StacksLink {

    private class Node{
        String item;
        Node next;
    }

    private Node first = null;

    public boolean isEmpty(){
        return first == null;
    }

    public void push(String item) {
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
    }

    public String pop(){
        Node temp = first;
        first = first.next;
        return temp.item;
    }
}

​ 好，我们来看代码 这门课中所有的链式数据结构中 我们使用Java中内部类来实现，这只是 描述我们要操作的节点对象的一种方法 节点对象由一个字符串和指向另一个节点的引用组成。

​ 所以，链表的 出栈操作非常容易实现。首先，我们需要 返回链表中第一个元素，所以先将它存在变量item中 然后，要去掉第一个节点，我们只需要将 链表指向第一个元素的指针指向下一个元素 然后第一个节点就等着被垃圾回收处理 最后，返回保存的元素。

​ 入栈操作呢？ 我们要在链表头加入新的节点 首先，将指向链表头的指针存起来，oldfirst = first 然后创建新节点，这是我们要插入链表头 的新节点。first = new Node() 这是个实例变量，它的元素就是我们想要插入链表头 的字符串，这个例子中是“not”，它的next指针指向链表oldfirst元素 现在成了链表第二个元素。在这个操作之后 first指向链表头处的元素，链表中的元素依照 入栈时间降序排列。实现入栈操作 只需要四行代码。

​ 这个类中构造函数不做任何操作 也就不用写构造函数。内部类用来构成链表中的元素 将它写成了内部类，这样我们能够直接访问这些实例变量 栈唯一的实例变量是 链表中第一个节点的引用。

​ 现在，我们分析实现的性能 这样我们就能提供给客户算法数据结构的 性能信息。这个例子中，很容易就能看出每个操作 最坏情况下只需要常数时间。每个操作没有循环，这显然是我们很想要的特性。那么空间需求呢？这和机器具体 实现有关。这是个典型Java实现，每个对象会有16字节的 额外空间，因为有内部类，所以还有8字节的额外空间 在类Node中有两个引用 一个指向字符串，另一个指向Node类 各需要8字节，每个栈节点需要40字节，如果栈大小为N 需要大约40N字节。

​ 另一种实现栈的自然的方式是使用数组来储存栈上的元素。

package Stack;

public class StackArray {
    private int top;
    private int[] arr;

    public StackArray(int size) {
        arr = new int[size];
    }

    public boolean isEmpty() {
        return top == 0;
    }

    public void push(int num) {
        arr[top++] = num;
    }

    public int pop(){
        return arr[--top];
    }
}

​

使用数组 我们将栈中N个元素保存在数组中，索引为N的 数组位置对应栈顶的位置，即下一个元素加入的地方。好，要入栈 我们只需要将心元素加入s[N]，要出栈则移除s[N-1]处的元素 并将N减1。那么能看到使用数组一个根本性的缺点 必须事先声明数组的大小。将元素入栈，我们将元素放在N索引的位置 并将N增加1。这是现在很多编程语言表示使用索引N 并增加1的简洁表示。将元素出栈，我们将索引N减1并用它 返回数组中的元素。每个操作都只需要一行代码。有一个问题 客户端是否能向数据结构中插入空元素。这种情况中，我们 确实允许客户端插入空元素，但在Java中我们需要操心一个问题 叫做对象游离（loitering）,即在栈的数组 实现中有对象的引用，而我们并没有真正使用它 所以当减小N时，在数组中仍然有我们已经出栈 的对象的指针。尽管我们知道我们不再使用它了，但是Java系统 不知道。所以为了避免这个问题，最有效地使用内存 最好将去除的元素对应的项设为null，这样就不会剩下 旧元素的引用。因为不存在引用了接下来垃圾回收器会收回那些内存。这个问题比较细节，但是很重要 我们必须在实现中要确保充分利用内存。

​ 那么，栈的基本数组实现具有需要 客户端事先提供栈的最大容量的缺点。我们没有 严格按照API的要求。API就是要求我们能够建立一个栈 并且能够增长或者缩小到任意大小。首先会想到的也许是当客户端入栈新元素时 将栈的大小增加1，当出栈时 将栈的大小减小1。代码实现不难，但是不值得这么做，因为这么做 开销太大了。因为你必须创建大小大一个元素的 新的数组，然后把所有的元素复制到新的数组中。所以如果栈大小为N-1 插入N个元素需要的时间和N成正比 如果栈大小为N-2，需要正比于N-1的时间。所以前N个元素需要的时间就是对 前N个整数求和，我们知道这大约是N^2 / 2。往栈里插入N个元素 需要平方时间，我们已经看到过很多次，这样的性能对于 巨大的问题是不可接受的。

​ 那么，调整大小是个挑战 但要通过某种方式确保它并不会经常发生。处理这个问题 有个著名的方法叫反复倍增，当数组填满时 建立一个大小翻倍的新数组，然后将所有元素复制过去，我们就不会 那么频繁地创建新数组。这就是那个方法的实现。从大小为1的 数组开始。如果我们检测到N即栈中元素的个数与数组 长度相等，则栈满了，那么我们就在插入元素之前 将数组长度调整为两倍。我们如何调整为更大的数组呢？ 我们创建具有目标容量的新的数组，然后把 当前栈复制到新数组的前一半，然后返回 重新设置实例变量，我们的栈就有了更大的数组 这样做导致如果你向一个具有这种 数组表示的栈中插入N个元素，时间复杂度 与N而不是N^2成正比。因为你只有在数组大小翻倍时 才创建新的数组。而当数组翻倍时，你已经往栈里插入了 那么多的元素。所以平均下来就像每次插入只需要一个操作 所以，如果我们计算一下开销，插入前N个元素 你不需要花费从1到N之和的时间，而是 对二的幂从1到N求和 这样，总的开销大约是3N。所以，push 时先要访问数组一次，对于复制 要访问两次。所以，要插入元素，大约需要访问数组三次 这个图标是观察时间开销的另一种方式，表示出了实现 入栈操作需要访问数组的次数。每次遇到2的幂，需要进行那么多次 数组访问，但是从宏观上来看你是将那些元素放在栈上花去了那么多时间 这叫做平摊分析。考虑开销时 将总的开销平均给所有的操作。

​ 这是一个很好而且 有用的平摊分析的例子，我们分析出了栈实现的效率 出栈呢？我们需要考虑如何缩小数组 我们也许这么考虑，当数组满了的时候将容量翻倍，那么当它 只有一半满的时候，将容量缩减一半。我们不想这样做，这个办法并不如我们所愿解决问题。因为有一种现象叫做 抖动（thrashing）。如果客户端刚好反复交替入栈出栈入栈出栈 当数组满了就会反复翻倍减半翻倍减半，并且 每个操作都会新建数组，都要花掉正比与N的时间 这样就会导致平方时间，我们不想这样 有效的解决方案是直到数组变为1/4满的时候才将容量减半 实现起来也很容易，我们只要测试数组是否为 1/4满，如果是，则调整大小使其为半满。

​ 这是两种 API相同的不同的实现，客户端可以互换使用。哪个更好呢？ 很多情形中，我们会有同一API的多种实现 你需要根据客户端的性质选择 合适的实现。对于链表，每个操作最坏情况下 需要常数时间，这是有保障的。但是为了处理链接 我们需要一些额外的时间和空间。所以链表实现会慢一些 可调大小的数组实现有很好的分摊时间，所以整个过程 总的平均效率不错，浪费更少的空间，对于每个操作 也许有更快的实现，所以对于一些客户端，也许会有区别 以下这样的情形你不会想用可调大小数组实现 你有一架飞机进场等待降落 你不想系统突然间不能高效运转 或者互联网上的一个路由器，数据包以很高的速度涌进来 你不想因为某个操作突然变得很慢而丢失 一些数据。客户端就可以权衡，如果想要 获得保证每个操作能够很快完成，就使用 链表实现，如果不需要，只是关心总的时间 可能就是用可调大小数组实现，因为总的 时间会小得多，单个操作非常快。