内容

• 介绍三种基本的数据结构
• 介绍抽象数据类型(ADT, abstract data type)的概念
• 介绍栈ADT及其在实现递归方面的应用
• 介绍队列ADT及其在操作系统和算法设计中的应用
• 给出vector和list的重要子集的实现

栈

实现

栈是一个表，因此任何实现表的方法都能实现栈。

应用

1. 符号平衡
2. 后缀（逆波兰）表达式计算
3. 中缀到后缀的转换
4. 函数调用
   （代码实现了一个简单的计算器，应保证输入合法）

总结

快慢指针

ex 3.34 提示：判断一个链表是否有环，只使用O(1)的额外空间，使用两个迭代器p,q p每次递增1，q每次递增2，若q到了末尾则没环，否则pq必定在环中间相遇

也可用于快速找出单链表的中间节点