抽象数据类型(ADT)

抽象数据类型（Abstract Data Type，ADT），是指一个数学模型及定义在该模型上的一组操作。它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。

抽象数据类型的主要作用是数据封装和信息隐藏，让实现与使用相分离。数据及其相关操作的结合称为数据封装。对象可以对其他对象隐藏某些操作细节，从而使这些操作不会受到其他对象的影响，这就是信息隐藏。

为什么需要抽象数据类型？

其实就是先设计后开发（类似于 UML类图）。根据数据结构的特性，抽象出这个结构的一些操作方法，设计完了没问题之后再开发实现。其他人只需要根据定义的参数调用就行，不用管怎么实现的。（有点类似接口文档）只要把这几个字拆分开，就容易理解了：

• 抽象：抽取出事物具有的普遍性的本质
• 数据类型：一组性质相同的值的集合以及定义在此集合上的一次操作的总称

抽象数据类型不是固定不变的，但是会有约定的一些操作，例如栈,那肯定有出栈和入栈的操作。

栈的抽象数据类型

• ADT 栈（Stack）
  • Data
    • 数据对象集合为{a1, a2, a3, ..., an},每个元素类型均为DataType。其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素由且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
  • Operation
    • InitStack(*S): 初始化操作，建立一个空栈 S。
    • DestroyStack(*S): 若栈存在，则销毁它。
    • ClearStack(*S): 清空栈。
    • GetTop(S, *e): 若栈存在且非空，用 e 返回 S 的栈顶元素。
    • push(*S, e): 若栈 S 存在，插入新元素 e 到栈 S 中并成为栈底元素。
    • Pop(*S, *e): 删除栈 S 中栈顶元素，并用 e 返回其值。
    • getLength(S): 返回栈 S 的元素个数。
• endADT

根据上面的 ADT，我们就可以开始进入实现步骤。就是实现一个 Stack 类，这个类里面具有以上特点和操作方法。这样是不是容易理解多啦。

function Stack() { 
    this.dataStore = [];  // 初始化一个空数组来保存 
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
    this.clear = clear;
    this.length = length; 
}
function push(element) { 
    this.dataStore[this.top++] = element; 
}
function peek() { 
    return this.dataStore[this.top-1];
}
function pop() { 
    return this.dataStore[--this.top]; 
}
function clear() {
    this.top = 0; 
}
function length() { 
    return this.top; 
}