基本的抽象数据类型涉及若干对象的集合以及在这个集合上定义的一些操作，包括添加、删除和集合中的对象等。下面主要以三种基本类型（Bag Stack Queue）来说明。
- 我们在用不同的方式表现集合中的元素时，通常也会产生不同的操作效率
- 使用泛型和循环可以显著地简化客户端代码
Bag
Bag 是一种收集元素并可以遍历它们的数据结构，元素之间不分先后顺序。Bag 不支持删除元素的功能。
Bag 的 API
- 添加元素
- 判断是否为空
- 返回元素数量（集合大小）
Queue
Queue（队列）是一种基于“先进先出” （FIFO）策略的元素集合，当进行遍历时，元素的遍历顺序与他们被添加到集合时的顺序一致
Queue 的 API
- 元素入队（Enqueue）
- 元素出队（Dequeue）
- 判断是否为空
- 返回元素数量（集合大小）
Stack
Stack（栈）是一种基于“后进先出” （LIFO）策略的元素集合，当进行遍历时，元素的遍历顺序与他们被添加到集合时的顺序刚好相反
Stack 的 API
- 元素入栈（Push）
- 元素出栈（Pop）
- 判断是否为空
- 返回元素数量（集合大小）
集合的具体实现
集合具体实现有两种方式：数组 和 链表
集合实现的目标：
- 每种操作的时间复杂度独立于集合的大小
- 占用空间大小与集合大小必须是常数倍关系
数组
优点：
- 访问指定元素的时间复杂度仅为 O（1）
缺点：
- 长度不可变
- 长度与集合大小的关系模糊
动态调整数组长度弥补数组长度固定的缺点，保证不会发生溢出同时也不会浪费太多的空间，它的原理是：当数组没有空间时，加倍数组的空间大小（即将这个数组复制到一个2倍长的数组中）；当数组中元素个数减少至总空间的 1/4 时，减半数组的长度（即将这个数组复制到一个一半长的数组中）。这样，空间利用率总在 1/4 到 1 之间，且不会发生溢出。然而，这样的实现违背了集合实现目标的第一条。有时候，进行添加和删除元素操作会使数组大小变化，这时就与集合大小有关。
链表
链表的递归定义是：
一个链表：
- 为空（NULL）
或
- 是对一个节点的引用。这个节点包含一个元素和一个对某个链表的引用
算术表达式
算术表达式由算子（operand，即数字），运算符（operator）和括号组成。
完全括号化：每一处都使用括号来表明运算顺序，而不是进行隐形的运算符优先级比较，例如
(1+((2+3)*(4*5)))
对于一个完全括号化的算术表达式，可以使用如下的递归方式去定义：
一个算术表达式是：
- 一个数字
或
- 一个左括号，后面跟着一个算术表达式，一个运算符和另一个算术表达式，然后以一个右括号结尾
中缀表达式： 我们经常使用的表达式写法就是中缀表达式，即运算符在算子中间。运算符间有优先级差别，也有括号的存在。
后缀表达式：运算符在算子之后的表达式，不需要括号，运算符之间无优先级差别，比如 5 1 2 + 4 × + 3 − 。参见Reverse Polish notation
前缀表达式：
后缀表达式：运算符在算子之前的表达式，不需要括号，运算符之间无优先级差别，比如 − × ÷ 15 − 7 + 1 1 3 + 2 + 1 1 。参见Polish notation
计算算术表达式结果的算法
Dijkstra 算法 （Using two stacks)
从左到右一次取出一个元素，然后按照以下原则处理：
_（完全括号化的情况）_
- 如果是算子（数字），则将其压入算子栈
- 如果是运算符，则将其压入运算符栈
- 如果是左括号，则忽略
- 当遇到右括号时，从运算符栈弹出一个运算符，从算子栈弹出这个运算符需要数量的算子，进行运算，将结果压入算子栈
_（一般情况）_
- 如果是算子（数字），则将其压入算子栈
- 如果是运算符O1：
- 如果运算符栈空，则直接入栈
- 与运算符栈栈顶运算符O2进行优先级比较：
- 如果优先级小于等于O2，则弹出O2，从算子栈中弹出O2所需要数量的算子，进行计算，将结果压入算子栈
- 如果优先级大于O2，则入栈
- 如果是左括号，则将其压入运算符栈
- 当遇到右括号时：
- 如果运算符栈顶不是左括号，则从运算符栈中弹出一个运算符，再从算子栈中弹出运算符所需要数量的算子，进行计算，将结果压入算子栈。循环这个过程，直到运算符栈顶是左括号为止
- 如果运算符栈顶是左括号，则弹出左括号
- 当无元素可读取时，如果运算符栈还有元素，则弹出运算符并弹出适量算子进行计算，将结果存入算子栈。循环这个过程直到运算符栈空，然后结束。否则直接结束。
其实，Dijkstra 算法的一般形式相当于将中缀表达式转换成了后缀表达式，很多计算器就是基于这个算法制作的
完整的 Dijkstra 算法要复杂得多，包含了函数、右结合运算符、括号不匹配等多种情况，参见 Shunting Yard Algorithm