【Princeton】算法(2):栈和队列

【Princeton】算法(2):栈和队列

这里介绍一些数据结构相关的基本概念以及两种最基本的数据结构–栈和队列。

数据结构

数据结构(data structure)是指相互之间存在着一种或多种关系的数据元素的集合,它包括数据的逻辑结构存储结构数据的运算这三方面的内容。

逻辑结构指的是数据元素之间的逻辑关系,它独立于计算机,与数据的存储无关。数据的逻辑结构可分为:

  • 线性结构:结构中的数据元素间存在一一对应关系,典型的有线性表
  • 非线性结构:结构中的数据元素间不存在或存在多种对应关系,典型的有集合、树、图

存储结构指的是数据结构在计算机中的表示方式,它依赖于计算机语言,包括数据元素的表示和关系的表示。数据的存储结构主要有:

  • 顺序存储:逻辑上相邻的元素存储的物理位置也相邻,元素间的关系用存储单元的邻接关系来体现,可实现随机存取
  • 链式存储:逻辑上相邻的元素存储的物理位置不一定相邻,而借助元素的存储地址的指针来表示元素间逻辑关系,只能顺序存取
  • 索引存储:存储元素信息的同时,另建立索引表,索引表中存放一般形式为(关键字,地址)的索引项
  • 散列存储:根据元素的关键字计算出其存储地址

数据的运算包括对运算的定义和实现,运算的定义是针对逻辑结构而指出运算的功能,实现则是针对存储结构指出运算的具体步骤。

线性表(linear list)是由相同数据类型的多个数据元素组成的有限序列,可采用顺序或链式方式存储,且它的顺序存储又称为顺序表

下压栈(stack,简称“栈”)是一种后进先出(Last In First Out,LIFO)的线性表,将某个对象添加到该数据结构的过程称为入栈(push),取出的过程则称为出栈(pop)。一个栈好比堆叠起来的一摞文件,将一份文件放在其最顶端的过程也就是所谓的入栈,出栈则是从最顶端取出一份文件的过程,如下图所示:

栈的类比

这里将栈的API设置如下:

栈的API

实现

线性表可以用顺序或链式方式进行存储,先考虑用链表实现的一个下压堆栈,其示意图如下:

链表实现的堆栈

在Java中,我们构建一个内部类Node以实现单链表。入栈对链表而言是表头插入新节点,出栈的则是在表头删除结点,采用链表实现一个泛型可迭代的下压堆栈的具体过程如下:

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
60
61
62
63
64
65
66
67
68
69
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Stack<Item> implements Iterable<Item> {
private Node first; // 栈顶
private int n; // 元素数量

private class Node {
Item item;
Node next;
}

public Stack() {
first = null;
n = 0;
}

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() {
if (isEmpty())
throw new NoSuchElementException("Stack underflow");

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;

public ListIterator() {
current = first;
}

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

public void remove() {
throw new UnsupportedOperationException();
}

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

为了储存多种类型的数据,以上代码中用到了Java中的泛型(genericity)机制,将数据类型参数化。此外,为使该数据结构可以用Java中的foreach语句迭代遍历其中的所有元素,代码中为Stack类实现(implements)了一个Java库的迭代器Iterator接口(interface),并重写(override)了接口中一些方法。

对以上实现的堆栈,其中没有任何循环过程,因而每一种操作即使在极端情况下也能保持常数级别的运行时间。

使用数组实现下压堆栈时,需注意Java不允许泛型数组,要用以下方式进行强制转换:

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

此外还需要根据元素的数量及时调整数组的大小以防止出现溢出(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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.Iterator;
import java.util.NoSuchElementException;

public class ResizingArrayStack<Item> extends Iterable<Item> {
private Item[] a;
private int n;

public ResizingArrayStack() {
a = (Item[]) new Object[1];
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() {
if (isEmpty())
throw new NoSuchElementException("Queue underflow");

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;

public ReverseArrayIterator() {
i = n - 1;
}

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

public String next() {
if (!hasNext())
throw new NoSuchElementException();
return a[--i];
}

public void remove() {
throw new UnsupportedOperationException();
}
}
}

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

时间成本

用链表实现栈时:

  • 在极端情况下,每次操作也能保持常数级别的时间复杂度
  • 需要用到额外的时间、空间来处理指针

而对数组实现的栈:

  • 平均下来每次操作将是常数级别的时间复杂度
  • 不浪费空间

因此需根据实际需求,在两种实现方式间做出选择。

背包

背包(Bag)是一种只允许添加(add)、不支持从中删除元素的集合数据类型,其作用就是帮助用例收集元素并迭代遍历所有收集到的元素,迭代的顺序不确定且与用例无关。

用链表实现背包,只需要将Stack中的push方法改名为add,并删除其中的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
51
52
53
54
55
56
57
58
import java.util.Iterator;

public class Bag<Item> implements Iterable<Item> {
private Node first;
private int n; // 元素数量

public Bag() {
first = null;
n = 0
}

private class Node {
Item item;
Node next;
}

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

public int size() {
return n;
}

public void add(Item item) {
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
n++;
}

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

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

public ListIterator() {
current = first;
}

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

public void remove() {
throw new UnsupportedOperationException();
}

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

应用

上世纪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());
}
}

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

队列

队列(queue)是一种先进先出(First In First Out,FIFO)形式的线性表,向其中添加元素的过程称为入列(enqueue),删除元素的过程则称为出列(dequeue)。日常生活经常遇到的排队等待各种服务的过程,就相对于一个队列的入列、出列过程。

这里将队列包含的API设置如下:

队列API

实现

与栈类似,队列可用链表或数组实现。用链表实现的一个队列如下图所示:

链表实现队列

对链表而言,入队是从表位插入新节点,并将插入的新节点的指针设置为null,出队则和出栈的操作类似,还是从表头删除结点。具体实现过程为:

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
60
61
62
63
64
65
66
67
68
69
public class Queue<Item> implements Iterable<Item> {
private Node first; // 指向最早添加的结点
private Node last; // 指向最近添加的结点
private int n; // 元素数量

private class Node {
Item item;
Node next;
}

public Queue() {
first = null;
last = null;
n = 0;
}

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;

public ListIterator() {
current = first;
}

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

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

用数组实现队列的过程则如下:

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.Iterator;
import java.util.NoSuchElementException;

public class ResizingArrayQueue<Item> implements Iterable<Item> {
private Item[] q;
private int n;
private int first;
private int last;

public ResizingArrayQueue() {
q = (Item[]) new Object[2];
n = 0;
first = 0;
last = 0;
}

private void resize(int cap) {
Item[] temp = (Item[]) new Object[cap];
for (int i = 0; i < n; i ++)
temp[i] = q[(first + i) % q.length];
q = temp;
first = 0;
last = n;
}

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

public int size() {
return n;
}

public void enqueue(Item item) {
if (n == q.length)
resize(2*q.length);
q[last++] = item;

if (last == q.length) // 循环利用空间
last = 0;
n++;
}

public Item dequeue() {
if (isEmpty())
throw new NoSuchElementException("Queue underflow");

Item item = q[first];
q[first] = null;
n--;
first++;

if (first == q.length)
first = 0;

if (n > 0 && n == q.length/4)
resize(q.length/2);

return item;
}

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


private class ArrayIterator implements Iterator<Item> {
private int i;

public ArrayIterator() {
i = 0;
}

public boolean hasNext() {
return i < n;
}

public void remove() {
throw new UnsupportedOperationException();
}

public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = q[(i + first) % q.length];
i++;
return item;
}
}

}

参考资料

  1. Algorithms-Coursera
  2. 算法(第四版)

Tip:本文涉及的图片及资料均整理翻译自普林斯顿大学的Robert Sedgewick教授在Coursera上讲授的的Algorithms课程以及他撰写的配套书籍的《算法(第四版)》,版权归其所有。翻译整理水平有限,如有不妥的地方欢迎指出。


更新历史:

  • 2019.03.22 完成初稿
  • 2019.07.30 调整内容

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×