算法导论-基础数据结构

Introduction to Algorithms 3rd Edition

Part III - Data Structures

Chapter 10: Elementary Data Structures

在算法中，栈、队列、链表和树是几种最基础的数据结构，几乎所有高级数据结构都是对基础数据结构的扩充和变种。栈的特性是后进先出，栈在操作系统和编译器领域都是极其重要的，堆和栈是操作系统内存分配中最重要的结构，至于编译领域，函数调用都是基于栈的方式，所以所有递归的程序都可以用栈改写成非递归的形式。数组是链表的一种形式，链表的应用范围非常广泛，几乎无所不在，比如排序，内存分配、垃圾回收等。树几乎是所有高级数据结构的基础，前面介绍的堆排序用到了树结构，很多语言的标准库中的集合、哈希表的实现都是基于树，红黑树，B树，文件系统，树的应用也无所不在，这主要是因为树在查找、插入和删除等操作上的时间复杂度比较均衡，因而在很多领域是首选的数据结构。

所有基础数据结构都要熟练掌握，如果算法是内功的话，这几种数据结构就是内功的基础，基础不牢，所有高级的内功都不能消化。

Exercises:

10.1-2

两个栈向数组中间增长，直至相遇才overflow

10.1-5

用head和tail变量记录deque的头和尾

10.1-6

不妨设两个栈为S1和S2，每次ENQUEUE时PUSH到S1中，每次DEQUEUE时POP S2，如果S2为空，那么将S1中的所有元素POP到S2中。最坏情况下的时间复杂度是O(n)，平均期望时间复杂度是O(1)

10.1-7

不妨设两个队列是Q1和Q2，每次PUSH时检测Q1和Q2哪个为空，假设Q1为空，就ENQUEUE Q1，然后将Q2的所有元素DEQUEUE并ENQUEUE到Q1中。POP时将不为空的队列DEQUEUE即可。

10.2-1

DELETE需要扫描链表找到需要删除的元素。

10.2-2

PUSH时INSERT到最前面，POP时删除第一个元素。

10.2-3

增加尾指针，ENQUEUE时添加到最后，DEQUEUE时删除第一个元素

10.2-4

给L.nil.key赋值成k

10.2-6

用链表即可，将一个链表连接到另一个链表最后。

10.2-7

从前往后扫描，反转