[数据结构与算法]表、栈、队列

作为三种最基本的数据结构，掌握它们必不可少。本次介绍的重点如下：

• 介绍抽象数据类型（ADT）的概念
• 阐述如何有效地执行对表的操作
• 介绍ADT及其在实现递归方面的应用
• 介绍队列ADT及其在操作系统和算法设计中的应用

1.1 抽象数据类型（Abstract Data Type)

ADT是带有一组操作的一些对象的集合，就想我们所知的insert、add、remove等数据操作。抽象数据类型是数学的抽象，这点也体现出数学的魅力之大。
可以类比整数、实数和布尔数各自都有与之相关的操作，而抽象数据类型也是如此，只不过数据类型更加复杂一些。
现有操作汇总：add/remove/size/contains/union/find
对于union（并）和find（查找），在这两种操作又在这个集合上定义了另一种不同的ADT。
此外，三种基本的数据结构可以以多种方式进行实现。

对于每种ADT并不存在什么法则来告诉我们必须要有哪些操作，这是一个设计决策。

3.2 表ADT

表（list）形如A₀，A₁，A₂，…，A_N-1，这个list的大小为N，我们将大小为0的特殊的表称为空表（empty list）。
对于除了空表外的任何表，我们说A_i后继A_i-1（或继A_i-1之后，i<N）并称A_i-1前驱A_i（i>0)。
表中的第一个元素为A₀，最后一个元素为A_N-1。我们不定义A₀的前驱元，也不定义A_N-1的后继元。A_i在表中的位置为i。
对list ADT的相关操作，printList、makeEmpty是常用的操作。find是返回某一项首次出现的位置；insert及remove一般是从表的某个位置插入和删除某个元素，参数为位置及被操作数的值；而findKth是返回（作为参数指定的）某个位置上的元素。

3.2.1 表的简单数组实现

对于数组的本身结构来看（比作电影院固定的座位），其需要一段连续的内存空间存储数据，并且空间大小固定，这样很有可能面临值泄露的问题；按索引查找速度快，但是插入删除操作慢；其次就是索引值是否为正整数的问题。

3.2.2 简单链表