数据结构与算法之ACM Fellow-算法 1.3 背包、队列和栈

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

Dijkstra 的双栈算术表达式求值算法

1. public class Evaluate
2. {
3. public static void main(String[] args)
4. {
5.    Stack<String> ops  = new Stack<String>();
6.    Stack<Double> vals = new Stack<Double>();
7.    while (!StdIn.isEmpty())
8.    {  // 读取字符，如果是运算符则压入栈
9.       String s = StdIn.readString();
10.       if      (s.equals("("))               ;
11.       else if (s.equals("+"))    ops.push(s);
12.       else if (s.equals("-"))    ops.push(s);
13.       else if (s.equals("*"))    ops.push(s);
14.       else if (s.equals("/"))    ops.push(s);
15.       else if (s.equals("sqrt")) ops.push(s);
16.       else if (s.equals(")"))
17.       {  // 如果字符为")"，弹出运算符和操作数，计算结果并压入栈
18.          String op = ops.pop();
19.          double v = vals.pop();
20.          if      (op.equals("+"))    v = vals.pop() + v;
21.          else if (op.equals("-"))    v = vals.pop() - v;
22.          else if (op.equals("*"))    v = vals.pop() * v;
23.          else if (op.equals("/"))    v = vals.pop() / v;
24.          else if (op.equals("sqrt")) v = Math.sqrt(v);
25.          vals.push(v);
26.       }  // 如果字符既非运算符也不是括号，将它作为double 值压入栈
27.       else vals.push(Double.parseDouble(s));
28.    }
29.    StdOut.println(vals.pop());
30. }
31. }

复制代码

这段 Stack 的用例使用了两个栈来计算表达式的值。它展示了一种重要的计算模型：将一个字符串解释为一段程序并执行该程序得到结果。有了泛型，我们只需实现 Stack 一次即可使用 String 值的栈和 Double 值的栈。简单起见，这段代码假设表达式没有省略任何括号，数字和字符均以空白字符相隔。

1. % java Evaluate
2. ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
3. 101.0
5. % java Evaluate
6. ( ( 1 + sqrt ( 5.0 ) ) / 2.0 )
7. 1.618033988749895

复制代码

• 数组中的元素顺序和它们被插入的顺序相同；
  
• 当 N 为 0 时栈为空；
  
• 栈的顶部位于 a[N-1]（如果栈非空）。
  

• 集合数据类型必须实现一个 iterator() 方法并返回一个 Iterator 对象；
  
• Iterator 类必须包含两个方法： hasNext()（返回一个布尔值）和 next()（返回集合中的一个泛型元素）。
  

• 每项操作的用时都与集合大小无关；
  
• 空间需求总是不超过集合大小乘以一个常数。
  

算法 1.1　下压（LIFO）栈（能够动态调整数组大小的实现）

1. import java.util.Iterator;
2. public class ResizingArrayStack<Item> implements Iterable<Item><Item>
3. {
4. private Item[] a = (Item[]) new Object[1];  // 栈元素
5. private int N = 0;                          // 元素数量
6. public boolean isEmpty()  {  return N == 0; }
7. public int size()         {  return N;      }
8. private void resize(int max)
9. {  // 将栈移动到一个大小为max 的新数组
10.    Item[] temp = (Item[]) new Object[max];
11.    for (int i = 0; i < N; i++)
12.       temp[i] = a[i];
13.    a = temp;
14. }
15. public void push(Item item)
16. {  // 将元素添加到栈顶
17.    if (N == a.length) resize(2*a.length);
18.    a[N++] = item;
19. }
20. public Item pop()
21. {  // 从栈顶删除元素
22.    Item item = a[--N];
23.    a[N] = null;  // 避免对象游离（请见1.3.2.4 节）
24.    if (N > 0 && N == a.length/4) resize(a.length/2);
25.    return item;
26. }
27. public Iterator<Item> iterator()
28. {  return new ReverseArrayIterator();  }
29. private class ReverseArrayIterator implements Iterator<Item>
30. {  // 支持后进先出的迭代
31.    private int i = N;
32.    public boolean hasNext() {  return i > 0;   }
33.    public    Item next()    {  return a[--i];  }
34.    public    void remove()  {                  }
35. }
36. }

复制代码

这份泛型的可迭代的 Stack API 的实现是所有集合类抽象数据类型实现的模板。它将所有元素保存在数组中，并动态调整数组的大小以保持数组大小和栈大小之比小于一个常数。

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

• 用长方形表示对象；
  
• 将实例变量的值写在长方形中；
  
• 用指向被引用对象的箭头表示引用关系。
  

• 在表头插入结点；
  
• 从表头删除结点；
  
• 在表尾插入结点。
  

• 删除指定的结点；
  
• 在指定结点前插入一个新结点。
  

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

算法 1.2　下压堆栈（链表实现）

这份泛型的 Stack 实现的基础是链表数据结构。它可以用于创建任意数据类型的栈。要支持迭代，请添加算法1.4中为 Bag 数据类型给出的加粗部分的代码。

1. % more tobe.txt
2. to be or not to - be - - that - - - is
4. % java Stack < tobe.txt
5. to be not that or be (2 left on stack)

复制代码

算法 1.3　先进先出队列

这份泛型的 Queue 实现的基础是链表数据结构。它可以用于创建任意数据类型的队列。要支持迭代，请添加算法 1.4 中为 Bag 数据类型给出的加粗部分的代码。

算法 1.4　背包

1. import java.util.Iterator;public class Bag implements Iterable<Item>{private Node first;  // 链表的首结点private class Node{    Item item;    Node next;}public void add(Item item){  // 和Stack 的push() 方法完全相同   Node oldfirst = first;   first = new Node();   first.item = item;   first.next = oldfirst;}public Iterator iterator(){  return new ListIterator();  }private class ListIterator implements Iterator{    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;    }}}

复制代码

这份 Bag 的实现维护了一条链表，用于保存所有通过 add() 添加的元素。 size() 和 isEmpty() 方法的代码和 Stack 中的完全相同，因此在此处省略。迭代器会遍历链表并将当前结点保存在 current 变量中。我们可以将加粗的代码添加到算法 1.2 和算法 1.3 中使 Stack 和 Queue 变为可迭代的，因为它们背后的数据结构是相同的，只是 Stack 和 Queue 的链表访问顺序分别是后进先出和先进先出而已。

• 定义 API；
  
• 根据特定的应用场景开发用例代码；
  
• 描述一种数据结构（一组值的表示），并在 API 所对应的抽象数据类型的实现中根据它定义类的 实例变量；
  
• 描述算法（实现一组操作的方式），并根据它实现类中的 实例方法；
  
• 分析算法的性能特点。