迭代器/范型、queueAndStack

summary_2018/07 algorithm designIdea todo(code)

1、日常工作

• coursera:queue and stack

2、技术学习

• coursera:queue and stack
  
  • stack

# stack : resizing-array implementation
Problem. Requiring client to provide capacity does not implement API!(创建一个可伸缩容量的API)
Q. How to grow and shrink array?
First try.
・push(): increase size of array s[] by 1.
・pop(): decrease size of array s[] by 1.
Too expensive.
・Need to copy all items to a new array.
・Inserting first N items takes time proportional to 1 + 2 + … + N ~ N 2 / 2（花销为平方）
Stack: amortized cost of adding to a stack (改进：分摊花销)
Q. How to grow array?
A. If array is full, create a new array of twice the size, and copy items.（大小呈倍数增大，减小呈倍数减小）
But：抖动现象：多一个增大数组，少一个减小数组之间循环
Too expensive in worst case.
・Consider push-pop-push-pop-… sequence when array is full.
・Each operation takes time proportional to N.
Efficient solution.
・push(): double size of array s[] when array is full.
・pop(): halve size of array s[] when array is one-quarter full.（1/4时再减小）
Tips：这个解决方案的思想和hashmap和hashtabled的思想有点类似，不过还可以加上它们的预分配策略
there is a worst case, that is, at the point when the stack doubles, it takes time proportional to N. （针对这一步操作而言）
Stack resizing-array implementation: memory usage
Proposition. Uses between ~ 8 N and ~ 32 N bytes to represent a stack
with N items.
・~ 8 N when full.
・~ 32 N when one-quarter full.
Stack implementations: resizing array vs. linked list
Linked-list implementation.
・Every operation takes constant time in the worst case.（恒定常数）
・Uses extra time and space to deal with the links.
Resizing-array implementation.
・Every operation takes constant amortized time.（总体常数）
・Less wasted space.

• queue

# Queue: linked-list
Maintain pointer to first and last nodes in a linked list;
insert/remove from opposite ends
# Queue: resizing array implementation
Array implementation of a queue.
・Use array q[] to store items in queue.
・enqueue(): add new item at q[tail].
・dequeue(): remove item from q[head].
・Update head and tail modulo the capacity.
・Add resizing array.
//这里比较复杂的是，如何去updat容量，因为最后剩下的在前面

• generics

# 我们需要在stack(queue)API中，放入不同类型的东西，如何解决？？
1、attempt1：每个类型一个stack，肯定是不行，代码的冗余度太高,维护难度太大
2、attempt2：使用类型强制转换，但需要出和入的时候都进行类型转换，如果那一方没有进行类型转换就会出现问题（优秀的代码尽量避免使用强制转换）
3、attempt3：范型  //例如java的范型
//泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。
・Avoid casting in client.
・Discover type mismatch errors at compile-time instead of run-time.
比如：Generic data types: autoboxing，自动装箱机制，原始类和包装类实现通用数据类型
# Generic stack: array implementation
# Generic stack: linked-list implementation

• Iteration（迭代器的实现）
  
  • 大多数客户端只是想遍历集合中的元素，并不需要知道内部的具体实现，用数组或者链表实现，比如java/c++都实现了自己的迭代器
  • 简单迭代器的组成：haveNext()/next()

# Stack iterator: linked-list implementation
# Stack iterator: array implementation