【算法】1.3. 背包、队列和栈

桩白墨
算法笔记
2018-04-13
176热度
0评论

导航

正文

许多基础数据类型都和对象的集合有关。具体来说，数据类型的值就是一组对象的集合，所有操作都是关于添加、删除或是访问集合中的对象。在本节中，我们将学习三种这样的数据类型，分别是背包（Bag）、队列（Queue）和栈（Stack）。它们的不同之处在于删除或者访问对象的顺序不同。

本节目标：

说明我们对集合中的对象的表示方式将直接影响各种操作的效率。对于集合来说，我们将会设计适于表示一组对象的数据结构并高效地实现所需的方法。
介绍泛型和迭代。有了它们我们能够写出更加清晰、简洁和优美的用例（以及算法的实现）代码。
介绍和并说明链式数据结构的重要性，特别是经典数据结构链表，有了它我们才能高效地实现背包、队列和栈。理解链表是学习各种算法和数据结构中最关键的第一步。

1.3.1 API

每份API都含有一个无参数的构造函数、一个向集合中添加单个元素的方法、一个测试集合是否为空的方法和一个返回集合大小的方法。Stack 和 Queue 都含有一个能够删除集合中的特定元素的方法。

背包
public class Bag<Item> implements Iterable<Item>
	Bag()	创建一个空背包
void	add(Item item)	添加一个元素
boolean	isEmpty()	背包是否为空
int	size()	背包中的元素数量
先进先出（FIFO）队列
public class Queue<Item> implements Iterable<Item>
	Queue()	创建空队列
void	enqueue(Item item)	添加一个元素
Item	dequeue()	删除最早添加的元素
boolean	isEmpty()	队列是否为空
int	size()	队列中的元素数量
下压（后进先出，LIFO）栈
public class Stack<Item> implements Iterable<Item>
	Stack()	创建一个空栈
void	push(Item item)	添加一个元素
Item	pop()	删除最近添加的元素
boolean	isEmpty()	栈是否为空
int	size()	栈中的元素数量

1.3.1.1 泛型

集合类的抽象数据类型的一个关键特性是我们应该可以用它们存储任意类型的数据。如果没有泛型，我们必须为需要收集的每种数据类型定义（并实现）不同的 API。有了泛型，我们只需要一份 API（和一次实现）就能够处理所有类型的数据，甚至是在未来定义的数据类型。

1.3.1.2 自动装箱

类型参数必须被实例化为引用类型，因此 Java 有一种特殊机制来使泛型代码能够处理原始数据类型。在处理赋值语句、方法的参数和算术或逻辑表达式时，Java 会自动在引用类型和对应的原始数据类型之间进行转换。例如：

Stack<Integer> stack = new Stack<Integer>();
stack.push(17);  // 自动装箱（int -> Integer）
int i = stack.pop();  // 自动拆箱（Integer -> int）

1.3.1.4 背包

背包是一种不支持从中删除元素的集合数据结构——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者获取背包中元素的数量）。迭代的顺序不确定且与用例无关。

1.3.1.5 先进先出队列

先进先出队列（简称队列）是一种基于先进先出（FIFO）策略的集合类型。使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序：使它们入列顺序和出列顺序相同。

1.3.1.6 下压栈

下压栈（简称栈）是一种基于后进先出（LIFO）策略的集合类型。当你的邮件在桌上放成一叠时，使用的就是栈。新邮件来到时你将它们放在最上面，当你有空时你会一封一封地从上到下阅读它们。计算机上的许多常用程序遵循相同的组织原则。例如，许多人用栈的方式存放电子邮件——在收信时将邮件压入（push）最顶端，在取信时从最顶端将它们弹出（pop），且第一封一定是最新的邮件（后进，先出）。这种策略的好处是我们能够及时看到感兴趣的邮件，坏处是如果你不把栈清空，某些较早的邮件可能永远也不会被阅读。你再网上冲浪时，点击一个超链接，浏览器会显示一个新的页面（并将它压入一个栈）。你可以不断点击超链接并访问新页面，但总是可以通过点击“回退”按钮重新访问以前的页面（从栈中弹出）。

使用栈迭代器的一个典型原因是在用集合保存元素的同时颠倒它们的相对顺序。例如，用例 Reverse 将会把标准输入中的所有整数逆序排列，无需预先知道整数的多少。在计算机领域，栈具有基础而深远的影响。

public class Reverse {
    public static void main(String[] args) {
        Stack<Integer> stack;
        stack = new Stack<Integer>();
        while (!StdIn.isEmpty())
            stack.push(StdIn.readInt());

        for (int i : stack)
            StdOut.println(i);
    }
}

1.3.1.7 算术表达式求值

递归定义：“算术表达式”可能是一个数，或者是由一个左括号、一个算术表达式、一个运算符、另一个算术表达式和一个右括号组成的表达式。（为了突出重点，我们不省略括号，支持最常见的二元运算符 *、+、- 和 /，以及只接受一个参数的平方根运算符 sqrt）

如何才能够得到一个（由字符串表示的）算术表达式的值呢？E.W.Dijkstra 在 20 世纪 60 年代发明了一个非常简单的算法，用两个栈（一个用于保存运算符，一个用于保存操作数）完成了这个任务。实现过程如下。

表达式由括号、运算符和操作数（数字）组成。我们根据以下 4 种情况从左到右逐个将这些实体送入栈处理：

将操作数压入操作数栈；
将运算符压入运算符栈；
忽略左括号；
在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。

在处理完最后一个右括号后，操作数栈上只会有一个值，它就是表达式的值。

/**
 * Dijkstra 的双栈算术表达式求值算法
 * Created by plough on 2018/4/7.
 */
public class Evaluate {
    public static void main(String[] args) {
        Stack<String> ops = new Stack<>();
        Stack<Double> vals = new Stack<>();
        String input = "( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )";
        for (String s : input.split(" ")) {
            if (s.equals("("));
            else if (s.equals("+")) ops.push(s);
            else if (s.equals("-")) ops.push(s);
            else if (s.equals("*")) ops.push(s);
            else if (s.equals("/")) ops.push(s);
            else if (s.equals("sqrt")) ops.push(s);
            else if (s.equals(")")) {
                String op = ops.pop();
                double v = vals.pop();
                if (op.equals("+")) v = vals.pop() + v;
                else if (op.equals("-")) v = vals.pop() - v;
                else if (op.equals("*")) v = vals.pop() * v;
                else if (op.equals("/")) v = vals.pop() / v;
                else if (op.equals("sqrt")) v = Math.sqrt(v);
                vals.push(v);
            }
            else vals.push(Double.parseDouble(s));
        }
        // 输出 101.0
        System.out.println(vals.pop());
    }
}

它展示了一种重要的计算模型：将一个字符串解释为一段程序并执行该程序得到结果。

1.3.2 集合类数据类型的实现

import java.util.Iterator;

/**
 * 下压（LIFO）栈（能够动态调整数组大小的实现）
 * Created by plough on 2018/4/13.
 */
public class ResizingArrayStack<Item> implements Iterable<Item> {
    private Item[] a = (Item[]) new Object[1];  // 栈元素
    private int N = 0;  // 元素数量
    public boolean isEmpty() {
        return N == 0;
    }
    public int size() {
        return N;
    }
    private void resize(int max) {
        // 将栈移动到一个大小为 max 的新数组
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }
    public void push(Item item) {
        // 将元素添加到栈顶
        if (N == a.length) {
            resize(2*a.length);
        }
        a[N++] = item;
    }
    public Item pop() {
        // 从栈顶删除元素
        Item item = a[--N];
        a[N] = null;  // 避免对象游离
        if (N > 0 && N == a.length / 4) {
            resize(a.length/2);
        }
        return item;
    }
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }
    private class ReverseArrayIterator implements Iterator<Item> {
        // 支持后进先出的迭代
        private int i = N;
        public boolean hasNext() {
            return i > 0;
        }
        public Item next() {
            return a[--i];
        }
        public void remove() {
        }
    }
}

注意点：

使用泛型。Java 中不允许创建泛型数组，所以需要使用类型转换：a = (Item[]) new Object[cap];
动态调整数组大小。在这个实现中，栈永远不会溢出，使用率也永远不会低于四分之一；
避免对象游离。在 pop 操作中，需要将被弹出的数组元素的值设为 null；
实现了迭代器，在 foreach 循环中会反向迭代。

这份泛型的可迭代的 Stack API 的实现是所有集合类抽象数据类型实现的模板。ResizingArrayStack 的缺点在于某些 push() 和 pop() 操作会调整数组的大小：这项操作的耗时和栈大小成正比。

1.3.3 链表

定义：链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。

常用操作：

在表头插入结点。过程略。运行时间和链表长度无关。
从表头删除结点。过程略。运行时间和链表长度无关。
在表尾插入结点。需要一个指向链表最后一个结点的链接。
其他位置的插入和删除操作，例如“删除指定的结点”、“在指定结点前插入一个新结点”。在缺少其他信息的情况下，唯一的解决办法就是遍历整条链表。

1.3.3.8 栈的实现

用链表来实现栈可以达到最优设计目标：

它可以处理任意类型的数据；
所需的空间总是和集合的大小成正比；
操作所需的时间总是和集合的大小无关。

import java.util.Iterator;

/**
 * 下压堆栈（链表实现）
 * Created by plough on 2018/4/13.
 */
public class Stack<Item> implements Iterable<Item> {
    private Node first;  // 栈顶（最近添加的元素）
    private int N;  // 元素数量
    private class Node {  // 定义了结点的嵌套类
        Item item;
        Node next;
    }
    public boolean isEmpty() {
        return first == null;
    }
    public int size() {
        return N;
    }
    public void push(Item item) {
        // 向栈顶添加元素
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    public Item pop() {
        // 从栈顶删除元素
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext() {
            return current != null;
        }
        public void remove() {}
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

1.3.3.9 队列的实现

将队列表示为一条从最早插入的元素到最近插入的元素的链表，实例变量 first 指向队列的开头，实例变量 last 指向队列的结尾。这样，要将一个元素入列，我们就将它添加到表尾；要将一个元素出列，我们就删除表头的结点。

/**
 * 先进先出队列
 * Created by plough on 2018/4/13.
 */
public class Queue<Item> {
    private Node first;
    private Node last;
    private int N;
    private class Node {
        Item item;
        Node next;
    }
    public boolean isEmpty() {
        return first == null;
    }
    public int size() {
        return N;
    }
    public void enqueue(Item item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        if (isEmpty()) {
            first = last;
        } else {
            oldlast.next = last;
        }
        N++;
    }
    public Item dequeue() {
        Item item = first.item;
        first = first.next;
        if (isEmpty()) {
            last = null;
        }
        N--;
        return item;
    }
    // iterator() 的与栈中的一样，略
}

在结构化存储数据集时，链表是数组的一种重要的替代方式。这种替代方案已经有数十年的历史。链表也是 LISP 语言组织程序和数据的主要结构。

1.3.3.10 背包的实现

只需要将 Stack 中的 push() 改名为 add()，并去掉 pop() 的实现即可。

/**
 * 背包
 * Created by plough on 2018/4/13.
 */
public class Bag<Item>{
    private Node first;  // 栈顶（最近添加的元素）
    private int N;  // 元素数量
    private class Node {  // 定义了结点的嵌套类
        Item item;
        Node next;
    }
    public boolean isEmpty() {
        return first == null;
    }
    public int size() {
        return N;
    }
    public void add(Item item) {
        // 向栈顶添加元素
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    // iterator() 的与栈中的一样，略
}

1.3.4 综述

在本节中，我们所学习的支持泛型和迭代的背包、队列和栈的实现所提供的抽象使我们能够编写简洁的用例程序来操作对象的集合。深入理解这些抽象数据类型非常重要，这是我们研究算法和数据结构的开始。原因有三：

我们将以这些数据类型为基石构造本书中的其他更高级的数据结构；
它们展示了数据结构和算法的关系以及同时满足多个有可能相互冲突的性能目标时所要面对的挑战；
我们将要学习的若干算法的实现重点就是需要其中的抽象数据类型能够支持对对象集合的强大操作，这些实现正是我们的起点。

数据结构

我们现在有两种表示对象集合的方式，即数组和链表。两者都非常基础，常常被称为“顺序存储”和“链式存储”。可以扩展为其他数据结构：

各种含有多个链接的数据结构。例如二叉树，由含有两个链接的结点组成
复合型的数据结构：我们可以使用背包存储栈，用队列存储数组，等等。例如图，可以用数组的背包表示。用这种方式很容易定义任意复杂的数据结构。

答疑

为什么 Java 不允许泛型数组？专家们仍然在争论这一点。对于初学者，请先了解“共变数组”（covariant array）和“类型擦除”（type erasure）。
如何才能创建一个字符串栈的数组？使用类型转换，如：Stack<String>[] a = (Stack<String>[]) new Stack[N];
既然有了链表，为什么还要学习如何调整数组的大小？我们还将会学习若干抽象数据类型的示例实现，它们需要使用数组来实现一些链表难以实现的操作。ResizingArrayStack 是控制它们的内存使用的样板。
为什么不实现一个单独的 Collection 数据类型并实现添加元素、删除最近插入的元素、删除最早插入的元素、删除随机元素、迭代、返回集合元素数量和其他我们可能需要的方法？这样我们就能在一个类中实现所有这些方法并可以应用于各种用例。（答：）再次强调一遍，这又是一个“宽接口”的例子。Java 在它的 java.util.ArrayList 和 java.util.LinkedList 类的实现中犯过这样的错误。避免使用它们的一个原因是这样无法保证高效实现所有这些方法。坚持“窄接口”的另一个原因是它们能够限制用例的行为，这将使用例代码更加易懂。