普林斯顿算法课第二周-泛型，迭代器和双栈算术表达式求值算法
在很多高级程序设计语言中都提供了Stack和Queue的数据结构，但大部分库中的数据结构所提供的API太过宽泛，后台进行的操作也太多，这样做是为了是数据结构能够满足大部分情况，但有些时候，当没有充分了解原声库的性能的时候就直接使用这些库，可能并不能打到期望的性能。所以有些时候，必须自己实现一些数据结构，至少在这个时候数据结构对我们来讲是可控的，算法的性能可以有我们自己来决定。
使用泛型让数据结构支持更多类型
泛型是面向对象程序设计中的多态思想的具体体现，属于比较基础的知识。简单描述起来，泛型就是一个万能类型，在C++和java这样的程序设计语言中泛型（模板）的实现尤为简单，在python等弱类型语言中虽然很少有人提到泛型这个概念，但其实其与生俱来就是支持泛型的。
在java中实现泛型有两种做法：
- 第一种做法是在生命数据类型的时候使用Object基类，但这样做有一个缺点就是需要在每次使用的时候，对每数据结构中的Object元素进行类型转换，这看上去并不是什么好办法。
2.第二种做法是使用java的泛型支持。
泛型的使用方法：使用泛型来创建一个Stack；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| package com.andy.algorithms;
public class Stack<Item> {
private Node first;
public boolean isEmpty(){
return first==null;
}
public Item pop(){
Item item = first.item;
first = first.next;
return item;
}
public void push(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
}
private class Node{
Item item;
Node next;
}
}
|
在实例化时的代码示例，值得注意的是，在java中使用泛型并不支持原声的数据类型，如果需要int 或者
double类型的元素去填充stack，在使用的时候则要使用它们对应的包装类，在这里则是Integer和Double
1
2
| Stack<String> str_stack = new Stack<String>();
Stack<Integer> int_stack = new Stack<Integer>();
|
事实上在C++内使用模板要比java的泛型要简单得多，他并没有太多的注意事项。要了解C++的模板，可以参考我的这篇博客里的代码。
使用iterator让数据结构可遍历
迭代器是高级程序设计语言中的一大利器，大部分时候客户端使用某一集合类型，做的是最多的工作便是迭代。java中提供了Iterator接口，可以帮助我们很快的实现这样的功能。
java的Iterator接口 定义非常简单，仅仅包含了三个需要被实现的方法：
1
2
3
| boolean hasNext()
E next()
void remove()
|
接下来改造一下我们的Stack类，下面的代码是数组实现的Stack，在为其提供了泛型支持之后，还实现了Iterator接口，让其可以使用foreach语法进行迭代。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| import java.util.Iterator;
public class Stack implements Iterator<Item> {
private Item[] s;
private int N = 0;
@Override
public boolean hasNext() {
return N > 0;
}
@Override
public Item next() {
return s[--N];
}
@Override
public void remove() {
}
public void Stack(){
this.s = (Item[]) new Object[1];
}
public boolean isEmpty(){
return N == 0;
}
public void push(Item item){
if(N == s.length) resize(s.length * 2);
s[N++] = item;
}
public Item pop(){
Item item = s[--N];
s[N] = null;
if(N > 0 && N == s.length/4 ) resize(s.length / 2);
return item;
}
private void resize(int target_size){
Item[] copy = (Item[]) new Object[target_size];
for (int i = 0; i < N; i++){
copy[i] = s[i];
}
s = copy;
}
}
|
双栈算术表达式算法的实现
双栈算术表达式算法的作用是计算标准的四则运算算术表达式，如： $((1+3)/3*(4+5))$
顾名思义，双栈算术表达式用到了两个stack，其中一个stack用来存放数字，另一个stack用来存放操作符，算法从头开始读取表达式，遇到（的时候略过，遇到数字则存放在数字stack，遇到操作符则放在操作符stack里，遇到）的时候，则使用数字stack最顶端的两个数字执行操作符stack最顶端的操作。
实现双栈算术运算的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static void main(String[] args){
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while(!StdIn.isEmpty()){
String s = StdIn.readString();
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(")")){
String op = ops.pop();
if (op.equals("+")) vals.push(vals.pop() + vals.pop());
else if (op.equals("-")) vals.push(vals.pop() - vals.pop());
else if (op.equals("*")) vals.push(vals.pop() * vals.pop());
else if (op.equals("/")) vals.push(vals.pop() / vals.pop());
}
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
|
写在最后
stack和queue是在编程中经常用到的数据结构，虽然大多数时间我们并不需要自己去实现它，但是像开头说的那样，有些时候我们并不充分了解其他库的性能，或者其他库为了实现一些我们在这个问题中用不到的功能而牺牲了整体性能，这个时候，我们可以果断的自己实现自己的数据结构和算法。
