算法第四版第一章背包队列栈-柚子小站

为了继续提高自己的水平, 是时候开始接触算法了. 看了很多算法的推荐, 这本算法第四版是很好的入门教材. 在Coursera上找到了这门课程的第一部分和第二部分, 还有书的配套网站材料备齐就开始吧, 由于没有完整的接触过算法, 第一次还是要细细品味. 经过两天的编写练习, 把书第一章前两个小节的练习都做了. 前边的练习部分基本上是熟悉Java语言, 现在要正式开始学习算法和数据结构了. 第三节就正式开始介绍一些数据结构, 首先就是背包, 队列和栈. 这三个数据结构都是集合, 而且都支持访问集合中的对象, 而三者的区别就是访问的顺序不同以及删除对象的顺序不同. 为了三者的实现, 还需要学习一种经典的数据结构, 就是链表.

三个数据结构概述
栈实现
链表
队列实现
背包实现
使用ADT解决问题的步骤

概述

背包就像现实中的一个背包一样, 不支持从其中删除元素. 是一个集合数据类型, 目的就是帮助程序收集元素并迭代遍历所有收集到的元素. 迭代的顺序不是确定的, 而且必须要与程序无关. 对于一个背包来说, 一般要实现的功能为迭代器, 即让用例可以不重复的从背包中取出元素来操作. 背包数据结构的API:

public class Bag<Item> implements Iterable<Item>

         Bag()          //构造器, 创建空的背包
    void add(Item item) //像背包中放入一个元素
 boolean isEmpty()      //判断背包是不是空
     int size()         //背包内装入的元素数量

一般把先进先出队列简称为队列, 这是一种对现实中情况的模拟. 这个集合与背包的区别在于是有序的. 删除元素的顺序必须是最先加入队列的元素最先被删除(或者说被提取出去). 而新增元素一定是排在队列的末尾. 队列保存了元素加入队列的相对顺序, 迭代其中的元素的时候, 也是按照这个顺序, 这个背包无序也是不同的. 要实现的队列的API如下:

public class Queue<Item> implements Iterable<Item>
         Queue()            //构造器, 创建空的队列
    void enqueue(Item item) //队列中添加一个元素
    Item dequeue()          //删除最早添加的元素
 boolean isEmpty()          //是否为空
     int size()             //返回队列长度

一般说的栈, 就是指下压栈, 也就是后进先出的队列. 狄克斯特拉的双栈算术表达式可以用于用括号括起来的表达式求值, 使用两个栈. 由于栈的后进先出特点, 有很多玩意都可以借助栈的性质. 要实现栈的API如下:

public class Stack<Item> implements Iterable<Item>
         Stack()            //构造器, 创建空的栈
    void push(Item item)    //将一个元素压入栈中
    Item pop()              //弹出栈末尾的元素
 boolean isEmpty()          //栈是否为空
     int size()             //返回栈深度

栈实现

栈实现的步骤可以分为几步, 首先来做一个容量固定的栈看看, 在此基础上引入泛型, 然后动态调整数组大小, 以及要学习一个关键的数据结构: 链表这里其实也给出了做一个ADT的递进的方法. 第一步就是做一个固定容量的栈, 而且为了简单, 也没有引入泛型, 挑选String作为其中存放的类型.

public class FixedCapaticyStackOfStrings {
    private String[] stack;
    private int N;

    public FixedCapaticyStackOfStrings(int cap) {
        stack = new String[cap];
    }

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

    public int size() {
        return N;
    }

    public void push(String item) {
        stack[N++] = item;
    }

    public String pop() {
        return stack[--N];
    }
}

这个定长栈比较简单, 通过构造器传入指定长度, 然后创建一个字符串数组. 内置一个N当做索引和当前栈长度, 使用N++ 和 --N 的技巧来控制栈和返回长度. 但是这个栈有几个问题:

只能处理String 元素, 没有泛型
栈长度固定, 不够灵活
弹出栈之后, 元素的引用仍然存在于数组中, 会造成依然引用那个对象
迭代的具体顺序是什么, 需要重现编写迭代器接口的方法

需要一个一个来解决这些问题, 用一个定长栈逐步过渡到变长栈, 最后解决性能问题, 用链表继续修改成一个栈实现. 首先需要处理泛型问题, 算法书这里是介绍了泛型, 不过对于知道泛型的我们, 可以直接将其修改为泛型类:

public class FixedCapaticyStackOfStrings<T> {
    private T[] stack;
    private int N;

    public FixedCapaticyStackOfStrings(int cap) {
        stack = (T[]) (new Object[cap]);
    }

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

    public int size() {
        return N;
    }

    public void push(T item) {
        stack[N++] = item;
    }

    public T pop() {
        return stack[--N];
    }
}

这中间主要注意强制类型转换的那部分代码, 反正Java 里对象数组是指针数组, 这里就是强转个指针类型. 因为不能直接创建泛型数组, 所以不能够写成 new T[cap], 不过使用强制转换没有问题, 很多Java标准库也是这种做法. 接下来的问题是数组的大小, 如果每次使用空间很小, 则空间浪费太大, 如果用例过大, 则可能溢出. 因此必须动态调整栈的长度. 我们采取的一个策略是在push()方法的时候进行检查, 如果栈满了, 使用一个当前2倍长度的数组, 将内容复制到新数组. 为此可以添加一个新方法resize(int max), 用于将当前的栈移动到长度为max 的新栈中, 当然max要大于现在的栈长度:

    public void resize(int max) {
        T[] temp = (T[]) (new Object[max]);
        for (int i = 0; i < temp.length; i++) {
            temp[i] = stack[i];
        }
        stack = temp;
    }

这个函数创建一个长度为max的新数组, 然后将原来的内部数组元素复制到新数组中, 然后将对象的数组引用设置为新数组. 之后就可以修改push函数了:

    public void push(T item) {
        if (N == stack.length) {
            resize(stack.length * 2);
        }
        stack[N++] = item;
    }

现在的 push 函数加入了判断, 如果此时N 已经等于数组的长度, 就不继续添加 ,而是先扩容, 再添加元素这个时候如果以为事情都做完了, 想法就太简单了. 当栈弹出了很多内容之后, 没有必要保留太长的栈, 所以对 pop() 也需要改进一下, 当弹出一个元素之后, 栈的长度已经到达数组长度的1/4, 就可以将整个数组长度减半:

    public T pop() {
        T item = stack[--N];

        //这里注意, 设置成null, 释放内存
        stack[N] = null;
        if (N>0 && N == stack.length / 4) {
            resize(stack.length / 2);
        }
        return item;
    }

在这里同时解决了弹栈时候的释放内存的问题. 最后是迭代问题. 如果是完全自己编写的栈, 涉及到设计模式中的迭代器模式, 需要为栈的ADT编写迭代器. 好在Java已经实现了一个迭代器接口 Iterable<T>. 要使用这个接口, 看过设计模式的都知道, 被迭代的类需要继承这个接口, 然后接口的抽象方法返回迭代器, 迭代器需要实现 Iterator<T> 接口, 然后编写 hasNext 和 next 方法. 在类声明中加上 implements Iterable<T>, 由于实现了接口, 必须编写接口的方法, 这个接口的抽象方法有一个 Iterator<T> iterator().

public class FixedCapaticyStackOfStrings<T> implements Iterable<T> {
    ......
    @Override
    public Iterator<T> iterator() {
        return new ReverseArrayIterator();
    }
}

这里把自己的迭代器类命名为ReverseArrayIterator, 因为这个迭代器从栈的最后一个元素按逆序迭代到第一个元素. 由于这个迭代器没有必要让FixedCapaticyStackOfStrings对象以外的对象访问, 将其设置为一个private权限的内部类:

import java.util.Iterator;

public class FixedCapaticyStackOfStrings<T> implements Iterable<T> {
    ......

    //作为内部类实现
    private class ReverseArrayIterator implements Iterator<T> {
        private int i = N;

        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public T next() {
            return stack[--i];
        }
    }
}

注意这里匿名内部类不需要带泛型, 因为实现接口已经带了泛型. 这里的关键是.hasNext方法, 用于判断是不是还有下一个元素. 这里就返回N, 只要N 不是0, 就说明还有下一个元素. .next()则会在.hasNext()方法判断通过后调用, 返回一个元素, 这里就反向取元素. 有了迭代器接口的加持, 写出适合ADT的迭代器就方便很多了, 同时就让ADT支持了增强for循环. 这样外部对于ADT内部的实际数据结构是什么就无须了解了. 这样就采用渐进的方式实现了一个完整的栈数据结构, 完整代码如下:

import java.util.Iterator;

public class ResizingArrayStack<T> implements Iterable<T> {
    private T[] stack;
    private int N;

    public ResizingArrayStack(int cap) {
        stack = (T[]) (new Object[cap]);
    }

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

    public int size() {
        return N;
    }

    public void push(T item) {
        if (N == stack.length) {
            resize(stack.length * 2);
        }
        stack[N++] = item;
    }

    public T pop() {
        T item = stack[--N];

        //这里注意, 设置成null, 释放内存
        stack[N] = null;
        if (N>0 && N == stack.length / 4) {
            resize(stack.length / 2);
        }
        return item;
    }

    public void resize(int max) {
        T[] temp = (T[]) (new Object[max]);
        for (int i = 0; i < temp.length; i++) {
            temp[i] = stack[i];
        }
        stack = temp;
    }

    @Override
    public Iterator<T> iterator() {
        return new ReverseArrayIterator();
    }

    //作为内部类实现
    private class ReverseArrayIterator implements Iterator<T> {
        private int i = N;

        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public T next() {
            return stack[--i];
        }
    }
}

这个代码可以作为很多集合类抽象数据的模板, 调整之后可以实现很多其他功能. 但是这里还有一个明显的缺陷, 就是每次调整数组的时候, 都需要遍历数组, 耗时和栈的大小成正比, 除了同样也需要遍历数组的迭代之外, 其他栈操作, 都在栈的尾部反向操作, 时间花费很小. 如果能有一种方法让栈调整空间的耗时也减少, 栈就更好了. 为此需要学习经典数据结构:链表.

链表

最简单的链表就是先要定义一个类, 类里包含泛型的元素和指向这个类的引用:

private class Node {
    T item;
    Node next;
}

由于这次的链表是供 ResizingArrayStack 内部使用的, 所以也使用private权限的内部类来编写, 其实我们只是编写了一个节点, 让 ResizingArrayStack 来操作节点以获得链表. 链表的几个操作如下:

在表头插入节点, 只需要先获得对原来链表的引用, 然后创建新节点, 将新节点的next指向原来的链表
删除表头节点, 只需要将链表引用指向首节点的下一个节点即可
在表尾插入节点, 需要获取指向表尾节点的链接, 然后创建新节点, 让表尾节点的next指向新节点
从表尾删除节点, 需要获取指向表尾节点上一个节点的链接, 然后将其next指向null
在链表的中间插入节点, 本质上就是需要获取要插入位置的当前节点和上一个节点, 然后创建新节点, 上一个节点的next指向新节点, 新节点的next指向插入前的当前节点

在实现栈的时候, 需要用到的是在表头插入和删除节点, 这样操作时间和链表的长度就无关了. 完整的栈实现如下:

public class Stack<T> implements Iterable<T> {
    /**
     * first: 指向最后一个压入栈的节点
     * N: 为了方便操作, 还是保存一个N做为元素数量
     */
    private Node first;
    private int N;

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

    public int size() {
        return N;
    }

    /**
     * 从链表头部插入节点
     * @param item 元素
     */
    public void push(T item) {
        Node oldfirst = first;
        Node newNode = new Node();
        newNode.item = item;
        newNode.next = oldfirst;
        first = newNode;
        N++;
    }

    /**
     * 从链表头部删除节点, 只要将first指向首节点的next节点即可.
     * @return 删掉的节点的数据
     */

    public T pop() {
        if (this.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        T item = first.item;
        first = first.next;
        N--;
        return item;
    }


    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }

    //迭代器的实现需要内部引用一下链表头部位置和当前元素数量, 然后移动当前位置, 用元素数量来控制 hasNext(), 然后来遍历链表
    private class LinkedListIterator implements Iterator<T> {
        private int i = N;
        private Node current = first;
        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public T next() {
            i--;
            T item = current.item;
            current = current.next;
            return item;
        }
    }

    private class Node {
        T item;
        Node next;
    }
}

迭代器这里还没讲, 自己先写出来了, 就是从头部根据N来遍历尾部, 其中每次需要控制遍历的位置, 就必须在内部维护一个位置变量current指向下一个要返回的节点. 有了栈的数据结构, 可以轻松做很多事情了. 之后来看队列的实现.

队列实现

有了链表的支持以后, 显然我们的队列也需要用链表来实现. 考虑到队列是一头进一头出, 因此可以维护两个节点的引用, 一个指向头节点, 一个指向尾节点. 另外还需要考虑队列从哪头进哪头出. 对于我们现在的简单链表, 很显然从尾节点删除元素比较困难, 因为还需要将指向尾节点的引用反向移动一次. 因此考虑元素进入队列可以放在末尾, 而删除元素可以从头部删除, 这样两个操作都方便很多. 根据上述分析, 可以实现队列 Queue 如下:

import java.util.Iterator;

public class Queue<T> implements Iterable<T> {

    private Node first;
    private Node last;
    private int N;

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

    public int size() {
        return N;
    }

    /**
     * 入列将元素插入到链表的最后, 如果本来N=0 即链表为空, 则将头尾节点都指向newNode
     * 如果不为空, 仅操作 last 即可
     * @param item 元素
     */
    public void enqueue(T item) {
        Node newNode = new Node();
        newNode.item = item;
        newNode.next = null;
        if (this.isEmpty()) {
            first = newNode;
            last = newNode;
        } else {
            last.next = newNode;
            last = newNode;
        }
        N++;
    }

    /**
     * 从链表头部删除节点, 只要将first指向首节点的next节点即可.
     * 注意如果此时没有节点了, 要把last也更新为null
     * @return 删掉的节点的数据
     */

    public T dequeue() {
        if (this.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        T item = first.item;
        first = first.next;
        N--;
        if (this.isEmpty()) {
            last = null;
        }
        return item;
    }


    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }

    /**
     * 迭代器依然还是从头部迭代到尾部, 恰好也是队列的FIFO的顺序.
     */
    private class LinkedListIterator implements Iterator<T> {
        private int i = N;
        private Node current = first;
        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public T next() {
            T item = current.item;
            current = current.next;
            i--;
            return item;
        }
    }

    private class Node {
        T item;
        Node next;
    }
}

这里有一点要注意的是, 原书使用的判断队列为空的方法是first==null, 所以才能在dequeue方法中, 在N--之前就可以判断 isEmpty() 了. 如果像我这样使用 N==0 再判断, 则必须在更新N的值之后进行判断, 否则会出错, 因为此时N还不为0, 所以不会正确的设置尾节点. 通过栈和队列的实现可以发现, 在结构化保存数据的时候, 链表是数组的一个重要的替代工具.

背包实现

在实现了栈和链表之后来看背包, 会发现背包实际上只是一个抽象的概念, 用栈还是链表来实现, 其实都是可以的, 虽然两种的迭代方式返回的数据顺序因为两种数据类型的意义不同而不同, 但对于不需要顺序的背包来说, 其实无所谓. 由于内部数据结构使用了链表, 因此迭代器还可以写的更简单一些, 无需去获取i了, 只需要使用一个current位置即可. 这里我们来使用栈修改成的背包类, 迭代器也采用更优化的版本:

import java.util.Iterator;

/**
 * 用栈修改而来的背包
 * @param <T> 泛型类型
 *
 */
public class Bag<T> implements Iterable<T> {
    /**
     * first: 指向最后一个压入栈的节点
     * N: 为了方便操作, 还是保存一个N做为元素数量
     */
    private Node first;
    private int N;

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

    public int size() {
        return N;
    }

    /**
     * 从链表头部插入节点
     * @param item 元素
     */
    public void add(T item) {
        Node oldfirst = first;
        Node newNode = new Node();
        newNode.item = item;
        newNode.next = oldfirst;
        first = newNode;
        N++;
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }

    //作为内部类实现
    private class LinkedListIterator implements Iterator<T> {
        private Node current = first;
        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public T next() {
            T item = current.item;
            current = current.next;
            return item;
        }
    }

    private class Node {
        T item;
        Node next;
    }
}

编写完了背包, 栈和队列, 这三个数据结构构成了很多复杂算法的基础.

使用ADT解决问题的步骤

在这一部分实际上就是使用ADT解决问题, 其一般的步骤是:

定义API
根据特定的应用场景开发用例代码
描述一种数据结构, 在API对应的抽象数据类型的实例中定义这个数据结构的变量
描述算法, 实现类中的实例方法, 也就是API
分析算法的性能特点

听着有些抽象, 其实就是刚才开发的例子, 以栈为例:

定义出了API
写出了一些用例和期望达到的效果
确定栈内部采用何种数据结构来存放元素. 一开始使用的是数组, 就定义了一个实例变量指向一个新创建的数组, 后来改成链表, 则定义了一个指向Node节点的引用变量.
描述了操作数据的方法, 即如何操作数组或者链表, 据此编写出了各个实例方法也就是API
分析了算法的性能特点, 发现数组的性能不高, 就改用了链表. 因为改用了链表, 所以又要把第三步开始的步骤再做一遍.