该文章为Princeton-Algorithms Part I读书笔记，相关视频在此。
1. 三个概念Client，Implementation，Interface
Client : 是一些程序（或应用），它们使用了在接口中定义的那些操作。
Implementation：是一些代码。它们真正对对接口进行实现。
Interface：是一种描述。描述了该接口应该包含的数据以及操作。
2. Stack
2.1 API接口
2.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接口
3.2 LinkedList实现
- 思路
维护两个指针，一个first，另一个last
-
dequeue()
dequeue -
enqueue(e)
enqueue -
完整代码
完整代码
3.3 Resizing-Array 实现
4. Iteration
4.1 Iterator
4.2 Stack Iterator LinkedList 实现
4.3 Stack Iterator Array 实现
4. Bag
Adding items to a collection and iterating (when order doesn't matter).
4.1 API接口
5. 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
-
代码
代码 -
正确性
算法总能够先算出由两个左右括号包围的两个数值运算后的值
正确性
