Programming Challenges 第二章 常用数据结构总结

这章对一些最基本的数据结构进行了大致的描述。对很多人来说，这应该算是一个复习吧。但是，很多时候，我们并不需要自己来实现这些数据结构，更重要的是要熟悉你所使用编程语言所提供给你的标准库。

• Stack。 最主要的特征：last-in, first-out。提供的操作应该有：Push(x, s), Pop(s), Initialize(s), Full(s), Empty(s)。实现Stack的最简单的方式是使用数组。另外一种方式是使用链表。对于一个元素集合，如果我们并不关心对这些元素的处理次序的话，Stack将是一种很简单的存储这些元素的方式。另外，Stack常常用来处理嵌套的结构，比如：parenthesized formulas(push on a "(", pop on ")"), recursive program calls (push on a procedure entry, pop on a procedure exit), and depth-first traversals of graphs (push on discovering a vertex, pop on leaving it for the last time)。
• Queue。最主要的特征：first-in, first-out。常用操作：Enqueue(x, q), Dequeue(q), Initialize(q), Full(q), Empty(q)。实现此数据结构的最简单的方式是使用arrays。
• Dictionaries。Stack和Queue是基于位置的检索，而Dictionaries可以基于内容进行检索。提供的操作一般有：Insert(x, d), Delete(x, d), Search(k, d)。有很多方式可以用来实现这种结构，如：sorted/unsorted linked lists, sorted/unsorted arrays, a forest full of random, splay, AVL, red-black trees, hashing。我们可以将Dictonaries分为三类：Static Dictionaries，Semi-Dynamic Dictionaries和Fully dynamic dics.对于Static Dic来说，这种结构一旦创建就不会在有变化，也就是说不会有增删改操作了，它们只用于检索。对于这种类型的Dic，常用的实现方式是arrays。现在的问题主要是决定是否对这个array进行排序。排序之后的好处是可以使用binary search。但是排序是需要代价的。一般来说，如果对时间没有很严格的限制的话，当元素个数小于100的时候，一般并不需要排序，直接顺序检索就可以了。如果检索不是很频繁的话，对于元素个数为1000的数组，其实也没有必要先排序。对于Semi-dynamic Dics来说，这种结构支持插入和检索，但不支持删除操作。如果我们知道将会插入的元素的上限的话，我们可以使用arrays。否则的话，我们就只有使用Linked list了。如果不支持删除操作的话，最好的方式是使用hash表。如果不支持delete操作的话，可以使用open addressing。否则的话，最好还是使用chaining。实现fully dynamic dics的最好方式当然是使用hashing表加上chaining来解决冲突。
• Priority Queues. 支持的操作有：Insert(x, p), Maximum(p), ExtractMax(p)。这种结构的实现方式一般是使用binary heap。
• Sets。基本操作有：Member(s, S), Union(A, B), Intersection(A, B), Insert(x, S), Delete(x, S)。如果该集合比较大的话，最好的实现方式是使用dictionary来表示集合。使用sorted dictionaries会使得union和intersection操作比较容易实现。对于比较小的集合，我们可以使用bit vectors。

C++提供对这些数据结构的实现

Stack	stack	push, pop, top, empty
Queue	queue	front, back, push, pop, empty
Dictionaries	hash_map	erase, find, insert
Priority Queues	priority_queue	top, push, pop, empty
Sets	set	set_union, set_intersection

Java提供的实现

Stack		Stack	pop, push, empty, peek
Queue	List	ArrayList, LinkedList	add, remove, clear
Dictionaries	Map	HashMap, Hashtable	put, get, contains
Priority Queue	SortedMap	TreeMap	firstKey, lastKey, heapMap
Sets	Set	HashSet	add, remove, contains