算法(2):基本数据结构

栈(Stacks)在CS中是一种后进先出(Last In First Out,LIFO)形式的线性表,队列(Queue)则是一种先进先出(First In First Out,FIFO)形式的线性表。

在很多的应用中,都需要维护一些包含多个对象(Obeject)的集合,且经常需要对该集合执行插入(Insert)、删除(Remove)、遍历(Iterate)元素及检查集合是否为空等操作。而这些对象组织成集合的过程中所采用的结构,往往关系着它们进行这一系列操作时的效率。

栈和队列,是两种最基本的数据结构:
栈和队列

栈是一种LIFO形式的线性表,向栈中添加元素的过程称为入栈(Push),删除元素的过程称出栈(Pop)。将一个栈中包含的API定义如下:
栈API

上世纪60年代E.W.Dijkstra发明了一种使用两个栈对算术表达式求值的算法,用Java实现的过程如下:

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
public class Evaluate {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>(); // 存放字符
Stack<Double> vals = new Stack<Double>(); // 存放数字

while (!StdIn.isEmpty()) {
String s = StdIn.toString();
if (s.equals("(")) ;
else if (s.euqals("+")) ops.push(s);
else if (s.euqals("-")) ops.push(s);
else if (s.euqals("*")) ops.push(s);
else if (s.euqals("/")) ops.push(s);
else if (s.euqals("sqrt")) ops.push(s);
else if (s.euqals(")")) {
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));
}

StdOut.println(vals.pop());
}
}

这样一种算法,可以对带括号的式子进行基本的四则运算。

用链表实现的一个下压堆栈示意图如下:
链表堆栈

采用链表实现下压堆栈的具体过程为:

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
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 Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}

为了储存多种类型的数据,以上代码中用到了Java中的泛型(Genericity)机制,将数据类型参数化。此外,为使用Java中的foreach语句迭代遍历集合中的所有元素,代码中将Stack类继承(Implements)了一个Java库的迭代器Iterator接口(Interface),并重写(Override)了其中抽象方法(Abstract function)

上面实现的堆栈中,每一种操作即使在极端情况下也能保持常数级别(Constant)的运行时间,而一个包含$N$个字符串(String)类型的元素的堆栈将占用约$40N$字节的内存空间:
内存占用

另一种实现栈的简单方式是使用数组存储站上的元素,要注意Java不允许泛型数组,要用以下方式进行转换:

1
a = (Item[]) new Object[cap];

此外还需要根据元素的数量及时调整数组的大小以防止出现溢出(Overflow)。用数组实现堆栈的过程如下:

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
53
54
55
56
public class ResizingArrayStack<Item> extends Iterable<Item> {
private Item[] a = (Item[]) new Object[1]; // 数组
private int N = 0; // 元素数量

private void resize(int max) { // 调整数组大小
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++)
temp[i] = a[i];
a = temp;
}

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

public int size() {
return N;
}

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 ListIterator() implements ReverseArrayIterator<Item> {
private int i = N;

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

public String next() {
return a[--i];
}

public void remove() {

}
}
}

调整数组大小的方式是:元素入栈时,检测到当前数组已满,则建立一个与当前数组大小翻倍的新数组,之后将所有原数组中的所有元素复制过去;出栈时,在数组只剩$1/4$满时则将数组的大小减半。平均下来,这样做的时间成本约为$3N$,比每次出入栈都去调整数组大小下的$N^2$要好很多,如下图所示:
时间成本

用数组实现的堆栈中,一个包含$N$个字符串的堆栈在将占用大约$8N$(全满)到$32N$($1/4$满)字节大小的内存空间。

队列

队列是一种FIFO形式的线性表,向其中添加元素的过程称为入列(Enqueue),删除元素的过程称出列(Dequeue)。将一个队列中包含的API定义如下:
队列API

用链表实现的一个队列示意图如下:
链表队列

采用链表实现队列的具体过程为:

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
53
54
55
56
57
58
59
public class Queue<Item> implements Iterable<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;
last.next = null;

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;
}

public Iterator<Item> iterator() {
return new ListIterator();
}

private class ListIterator() implements Iterator<Item> {
private Node current = first;

public boolean hasNext() {
return current != null;
}

public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}

编程作业:双端、随机队列

参考资料

  1. Algorithms-Coursera
  2. 程序及资料-GitHub

注:本文涉及的图片及资料均整理翻译自Robert Sedgewick的Algorithms课程以及配套教材《算法(第四版)》,版权归其所有。翻译整理水平有限,如有不妥的地方欢迎指出。


更新历史:

  • 2018.03.30 完成初稿
文章作者: Hugsy
文章链接: http://binweber.top/2018/03/25/algs_2/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Weber
支付宝打赏~
微信打赏~