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

迭代器/范型、queueAndStack

summary_2018/07 algorithm designIdea todo(code)


1、日常工作


2、技术学习

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

  1. # Queue: linked-list
  2. Maintain pointer to first and last nodes in a linked list;
  3. insert/remove from opposite ends
  4. # Queue: resizing array implementation
  5. Array implementation of a queue.
  6. Use array q[] to store items in queue.
  7. enqueue(): add new item at q[tail].
  8. dequeue(): remove item from q[head].
  9. Update head and tail modulo the capacity.
  10. Add resizing array.
  11. //这里比较复杂的是,如何去updat容量,因为最后剩下的在前面
  1. # 我们需要在stack(queue)API中,放入不同类型的东西,如何解决??
  2. 1attempt1:每个类型一个stack,肯定是不行,代码的冗余度太高,维护难度太大
  3. 2attempt2:使用类型强制转换,但需要出和入的时候都进行类型转换,如果那一方没有进行类型转换就会出现问题(优秀的代码尽量避免使用强制转换)
  4. 3attempt3:范型 //例如java的范型
  5. //泛型提供了编译时类型安全检测机制,该机制允许程序员在编译时检测到非法的类型。
  6. Avoid casting in client.
  7. Discover type mismatch errors at compile-time instead of run-time.
  8. 比如:Generic data types: autoboxing,自动装箱机制,原始类和包装类实现通用数据类型
  9. # Generic stack: array implementation
  10. # Generic stack: linked-list implementation
  1. # Stack iterator: linked-list implementation
  2. # Stack iterator: array implementation
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注