该文章为Princeton-Algorithms Part I读书笔记,相关视频在此。
1. 三个概念Client,Implementation,Interface
Client, Implementation & InterfaceClient : 是一些程序(或应用),它们使用了在接口中定义的那些操作。
Implementation:是一些代码。它们真正对对接口进行实现。
Interface:是一种描述。描述了该接口应该包含的数据以及操作。
2. Stack
2.1 API接口
Stack API2.2 LinkedList实现
- 思想
维持一个始终指向first node的指针
- pop()
- push(e)
- 性能:各个操作的用时是O(1)
2.3 Array实现
- 思想
在array的最后push,也在array的最后pop
- 实现
-
缺陷
stack的array实现的缺陷
underflow & overflow:array的IndexOutOfBound
->解决办法:resize array
Loitering: 当pop一个对象时,实际上我们只是将指针N前移,而对象并没有正真地在array中"被pop掉",还被array的指针所指。
->解决办法: 将array的对应指针设为null,因此那个无用的对象可以被garbage collector回收。
-
Resizing
-
递增扩容
效率低,耗时O(N^2),单次O(N)
递增扩容 -
加倍扩容 Doubling Resize
效率高,耗时O(N),平均单次耗时仅为O(1)
加倍扩容 -
减半减容 Halfling Resize
- 方法1:当one-half full时减半。效率低,平均单次耗时O(N)。
- 方法2:当one-quarter full时才减半。更有效率,平均单次O(1)。
-
-
Stack的array实现的性能 ->平均O(1)
Stack的array实现的性能
2.4 LinkedList实现与Array实现对比
对比LinkedList:每次操作的最坏O(1)。但是也要花额外的时间和空间维护LinkedList。
Resizing-Array:操作平均下来才O(1)。但是对一系列的操作来说,总体的耗时确可以更低。
3. Queue
3.1 API接口
queue API3.2 LinkedList实现
- 思路
维护两个指针,一个first,另一个last
-
dequeue()
dequeue -
enqueue(e)
enqueue -
完整代码
完整代码
3.3 Resizing-Array 实现
resizing array实现4. Iteration
4.1 Iterator
Iterator4.2 Stack Iterator LinkedList 实现
Stack Iterator LinkedList 实现4.3 Stack Iterator Array 实现
Stack Iterator Array 实现4. Bag
Adding items to a collection and iterating (when order doesn't matter).
4.1 API接口
Bag API5. Stack 和 Queue的应用
5.1 算术表达式评估Arithmetic expression evaluation
-
算法:Dijkstra's two-stack algorithm
-
思路:
- 维持两个stack,一个value,一个operator
- 遇到左括号:忽略
-
遇到右括号:pop出两个values以及一个operator,再将结果push进value stack
Dijkstra's two-stack algorithm
-
代码
代码 -
正确性
算法总能够先算出由两个左右括号包围的两个数值运算后的值
正确性
网友评论