算法4 栈和队列

数组是和链表是编程语言中最基本的数据存储结构了,其他更复杂的数据结构都是基于这两者实现的。而栈和队列则是最基础且被广泛使用的数据结构,我不想过多的赘述如何实现他们,只是提及一些注意事项和一些基本用法。

数组和链表

使用数组实现的大部分情况下性能都要优于链表,这是数组的可以使用索引快速访问元素决定的,且相同长度的数组比链表占用的内存要小很多。

但是数组无法轻易的改变结构,因为他是定长的,扩充长度意味着重新分配内存;数组也高效的从中间节点删除元素,意味着后半部分的元素需要重新拷贝。

而链表的使用可以非常灵活,因为本质上他就是一个节点对象中记录其他节点对象,缺点则是比较明显,随机读写能力差,额外内存占用率高。

数组 链表
随机访问效率高 随机访问效率低
内存占用率相对更低 内存占用率相对更高
灵活性一般 灵活性强

误区:链表比数组更节省内存。

听的比较多的就是这句没头没脑的话,这是相对而言的,实际使用中要根据情况选择使用数组和链表结构,不要片面给他们定下性能优劣的性质。这个观点的唯一依据就是,数组中存在很多没有使用的索引位。

int数组内存占用:对象开销 24byte + 4N;

int单向链表内存占用:32byte * N;如果是内部类,每个节点还要加上8byte的引用字节。

差距多少一目了然,如果不是数组真的有过多未使用的索引位,那么总体来说数组的内存占用率要小得多。

关于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 Chain<Item> {

private Node<Item> head;

public void push(Item item) {
Node<Item> newNode = new Node<>();
newNode.item = item;
newNode.next = head;
head = newNode;
}

// 使用两个指针分别指向上一个节点和当前节点,一个临时指针用来记录下一个节点;
// 循环的反转当前节点和上一个节点,然后右移指针,直到没有更多的节点。
public void reverse() {
Node<Item> prev = null;
while (head != null) {
Node<Item> temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
head = prev;
}

private static class Node<Item> {
private Item item;
private Node<Item> next;
}
}

上述代码中反转过程的演示:

首先新增节点1,2,3,4,5后链表结构如下。因为只有一个head节点用于记录,所以链表的顺序和录入顺序是相反的。

1
2
head
5 → 4 → 3 → 2 → 1

然后新建指针prev指向前一个节点,循环的反转当前节点和上一个节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 初始状态:
p h
null 5 -> 4 -> 3 -> 2 -> 1

// 反转prev和head:
// Node temp = head.next;
// head.next = prev;
// prev = head;
// head = temp;
p h
null <- 5 4 -> 3 -> 2 -> 1

p h
null <- 5 <- 4 3 -> 2 -> 1

p h
null <- 5 <- 4 <- 3 2 -> 1

p h
null <- 5 <- 4 <- 3 <- 2 1

// head为null,跳出循环,并让head = prev
p h
null <- 5 <- 4 <- 3 <- 2 <- 1

链表实现

其实就是上面链表反转的代码,加个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
public class Stack<Item> {

private Node<Item> head;

public void push(Item item) {
Node<Item> newNode = new Node<>();
newNode.item = item;
newNode.next = head;
head = newNode;
}

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

public boolean isEmpty() {
return head == null;
}

private static class Node<Item> {
private Item item;
private Node<Item> next;
}
}

数组实现

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
public class Stack<Item> {

private Item[] es = (Item[]) new Object[1];
private int n;

public void push(Item item) {
es[n++] = item;
// 每当数组满了之后,我们就扩充一倍大小
if (n == es.length) resize(es.length * 2);
}

public Item pop() {
Item item = es[--n];
es[n] = null; // 防止对象游离
// 每当数组元素减少到4分之1时,就将数组缩小一半节约内存。
if (n > 0 && n == es.length / 4)
resize(es.length / 2);
return item;
}

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

public void resize(int capacity) {
Item[] copy = (Item[]) new Object[capacity];
for (int i = 0; i < n; i++) {
copy[i] = es[i];
}
es = copy;
}
}

关于resize对性能的影响

当扩充数组时,需要对当前的元素遍历到新数组,长度为1的数组扩充需要访问两次数组,一次用于访问原数组,一次用于写入新数组。

长度为N的数组,一共需要拷贝数组logN次,数组的总访问次数为2 + 4 + 8 + 16 + ... + N,约等于2N。

N个元素的push操作需要访问N次数组,再加上一共2N的resize消耗,所以push方法一共会访问3N次数组,单次push操作的摊销次数为3


当缩减数组时,长度为N的数组缩减需要访问数组N/2次,N/4次访问原数组和N/4次写入新数组。

长度为N的数组缩减至2时,一共需要拷贝数组 logN-1 次,数组的总访问次数为2 + 4 + 8 + ... + N/2,约等于N。

N个元素的pop操作需要访问N次数组,再加上一共N的resize消耗,所以pop方法一共会访问2N次数组,单次pop操作的摊销次数为2

数组实现vs链表实现

数组实现占用内存相对较低并且存取速度非常快,但是每次操作的时间不是恒定的,在某一时刻因为扩充数组的原因变慢。

链表实现占用的内存要高非常多,并且因为每次存取的花费的时间更长,但是每个操作的时间都是恒定的。

我不知道是否存在需要每个操作的时间恒定的应用,否则数组实现的栈无疑是最好的选择。

dijkstra的双栈算术求值

关于很多和"匹配"相关的面试题,大多数的核心解决方案都是利用栈,例如匹配括号。dijkstra的双栈算术求值也是一段非常有意思的代码,短短的代码实现了包含优先级的判断的算术计算。

利用两个栈分别用于存储值和操作符,遇到左括号忽略,遇到右括号时将值和操作符弹出计算,并将计算结果再次放入存储值的栈,当栈为空时表示计算完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Evaluate {

public static void main(String[] args) {
String[] inputs = args[0].split(" ");
Stack<Double> vals = new Stack<>();
Stack<String> ops = new Stack<>();
for (String s : inputs) {
if (s.equals("(")) ;
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 vals.push(Double.parseDouble(s));
}
System.out.println(vals.pop());
}
}
1
2
$ java-algs4 Evaluate "( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )"
101.0

队列

代码略。原因是因为和栈的代码差距不大,下面Coursera作业中有相关实现。

若使用数组实现Queue时,需要两个指针分别指向数组第一个元素和最后一个元素后面,resize数组时注意指针位置即可。

1
2
3
4
       head  tail
↓ ↓
0 1 2 3 4 5 6 7 index
x x x x 5 6 7 x elements (x means null)

Coursera 作业

下面代码在Coursera作业中的得分为100。

Deque

双端队列或deque(发音为“deck”)是一种具有队列和栈的性质的数据结构,它支持从队列的前面或后面添加和删除项。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class Deque<Item> implements Iterable<Item> {

private Node first;
private Node last;
private int size;

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

public int size() {
return size;
}

public void addFirst(Item item) {
assertNotNull(item);
Node newFirst = new Node();
newFirst.item = item;
newFirst.next = first;
if (first == null) {
first = newFirst;
last = newFirst;
}
else {
first.prev = newFirst;
first = newFirst;
}
size++;
}

public void addLast(Item item) {
assertNotNull(item);
Node newLast = new Node();
newLast.item = item;
newLast.prev = last;
if (last == null) {
first = newLast;
last = newLast;
}
else {
last.next = newLast;
last = newLast;
}
size++;
}

public Item removeFirst() {
assertNotEmpty();
Item item = first.item;
first = first.next;
if (first == null) {
last = null;
} else {
first.prev = null;
}
size--;
return item;
}

public Item removeLast() {
assertNotEmpty();
Item item = last.item;
last = last.prev;
if (last == null) {
first = null;
} else {
last.next = null;
}
size--;
return item;
}

private void assertNotNull(Item item) {
if (item == null) {
throw new IllegalArgumentException();
}
}

private void assertNotEmpty() {
if (isEmpty()) {
throw new NoSuchElementException();
}
}

private class Node {
private Item item;
private Node next;
private Node prev;
}

public Iterator<Item> iterator() {
return new Iterator<Item>() {
private Node current = first;

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

public Item next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
Item item = current.item;
current = current.next;
return item;
}

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

RandomizedQueue

随机化队列,它和普通队列很像,只是移除元素的时候需要随机移除任意一项。

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
public class RandomizedQueue<Item> implements Iterable<Item> {

private Item[] es;
private int tail;

public RandomizedQueue() {
es = (Item[]) new Object[1];
}

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

public int size() {
return tail;
}

public void enqueue(Item item) {
if (item == null) throw new IllegalArgumentException();
if (tail == es.length) resize(es.length * 2);
es[tail++] = item;
}

public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException();
int random = StdRandom.uniform(0, tail);
Item item = es[random];
es[random] = es[--tail];
es[tail] = null;
if (tail > 0 && tail == es.length / 4) resize(es.length / 2);
return item;
}

private void resize(int capacity) {
es = copyArray(capacity);
}

private Item[] copyArray(int capacity) {
Item[] copy = (Item[]) new Object[capacity];
for (int i = 0; i < tail; i++) copy[i] = es[i];
return copy;
}

private Item[] copyArray() {
return copyArray(tail);
}

public Item sample() {
if (isEmpty()) throw new NoSuchElementException();
return es[StdRandom.uniform(0, tail)];
}

public Iterator<Item> iterator() {
Item[] items = copyArray();
StdRandom.shuffle(items, 0, tail);
return new Iterator<Item>() {

private int cursor = 0;

public boolean hasNext() {
return cursor < tail;
}

public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return items[cursor++];
}

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