@JunQiu 2018-09-18T12:54:16.000000Z 字数 2364 阅读 491

### 迭代器/范型、queueAndStack

summary_2018/07 algorithm designIdea todo(code)

1、日常工作

• coursera:queue and stack

2、技术学习

# stack : resizing-array implementationProblem. 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 usageProposition. Uses between ~ 8 N and ~ 32 N bytes to represent a stackwith N items.・~ 8 N when full.・~ 32 N when one-quarter full.Stack implementations: resizing array vs. linked listLinked-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-listMaintain pointer to first and last nodes in a linked list;insert/remove from opposite ends# Queue: resizing array implementationArray 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

• 私有
• 公开
• 删除