1. 介绍

因为已经学过数据结构相关的内容,这部分仅仅记录一些比较重要的。一些基本概念这里不再赘述。

2. 栈实现

实现上可以采用链表(Linked list)实现也可以采用数组(Array)实现

2.1 pop()函数实现时注意点

这里实现pop的时候,让出栈对象的引用指向NULL,方便GC对其回收或者重新分配

2.2 resizing arrays

方法一: push1个数就增加1个大小,pop一个数就减少1个大小。不过这样插入N个数的时间复杂度比较高为O(N^2),因为每次插入都要开辟新堆栈,将旧数据进行拷贝

方法二: 容量直接翻倍,这样不需要重复拷贝
代价为:

收缩栈的策略:
这里尤其注意,在POP的时候,是占用达到25%的时候缩小一半,这样处理,使得不会频繁的进行double和half操作

方法1和方法2都是用数组实现的。方法1的优点是所有堆栈操作是常数时间,但是可能会浪费空间,因为大小固定缺乏灵活性。方法2的优点就是自动收缩很灵活,但是栈操作的时间复杂度为3N。

3. 队列实现、泛型、迭代器

同样实现上可以采用数组实现或者链表实现

之后教程中还提到了泛型和迭代器,由于比较简单,这里就简单略过了。。

4. 栈和队列的应用


这个例子讲明的道理很有意义,即如果不知道这个库提供的API实现,就不要轻易使用。很明显Kenny采用了java.util.LinkedList来初始化一个渗透矩阵,然后去选取site的时候就要花费大量的时间。(链表查找很慢的,亲!)。就像不要过度优化一样,有时候简单的方法往往也是最有效的。

典型应用:中缀表达式


两栈算法,迪杰斯特拉提出的,用于计算中缀表达式
实现代码:

5. 编程作业

作业说明
注意点

提示:根据题目给出的performance requirements我们知道Dequeue采用链表实现而Randomized queue采用数组实现

编程作业源代码