栈
一种限制线性表，其本质上是一个线性表，只是其操作被限定为 LIFO（后进先出）。
一个栈的 ADT 需要暴露的操作有：
- stack()：建栈
- push()：元素入栈
- pop()：栈顶出栈
- empty()：检查栈是否为空
底层实现
对于数组实现，只需要预先开好足够大的数组充当栈，并维护一个整型变量用于存储栈当前大小即可。
对于链表实现，只需要维护一个单链表即可，单链表的表头的下一个元素即为栈顶。
队列
一种限制线性表，相对于栈而言，其限制操作为 FIFO（先进先出）
一个队列的 ADT 需要暴露的操作有：
- queue()：建队列
- enqueue()：元素入队
- dequeue()：队首出队
- empty()：检查队列是否为空
底层实现
- 对于数组实现，同样是需要开一个足够大的数组，并需要两个变量记录队首和队尾的下标。
考虑到空间利用率可以使用循环队列的实现方法。
对于链表实现，只需要维护一个单链表（表头指向队首）和一个指向队尾的指针即可。
广义线性表
区别于限制线性表，广义线性表不会限制操作。
其存储的数据单元包括 key 和 value 两部分。表严格按 key 升序排序。
这代表其需要实现一个线性表所能做的所有动作：
- list()：建表
- insert()：插入元素
- delete()：删除元素
- retrieve()：查找元素
- traverse()：顺序遍历表
- empty()：检查表是否为空
底层实现
由于其定义十分接近数组和链表，故这两种实现十分简单，不再赘述。
有一个思路是二叉平衡搜索树实现，在保证操作性能的同时也可以使其对外看起来跟一个线性表无异。
这个思路跟鸭子类型类似，但其底层并不是线性的，故其能否称为广义线性表还有待讨论
二叉树
二叉树的定义是其节点只能有 0 ～ 2 个分支。
二叉树一共有四种遍历方式：
- 前序遍历：先遍历根，再前序遍历左子树，最后前序遍历右子树
- 中序遍历：先中序遍历左子树，再遍历根，最后中序遍历右子树
- 后序遍历：先后序遍历左子树，再后序遍历右子树，最后遍历根
- 层次遍历：BFS 的方式进行遍历，按从上到下从左到右的顺序遍历
二叉搜索树
定义二叉树的每个节点存储一个数（或者其他可以进行大小比较的 ADT），那么当这棵树满足：
左子树的最大节点 < 根 < 右子树的最小节点 左右子树均为二叉搜索树 那么这棵树就是二叉搜索树。
二叉搜索树有一个很重要的性质是其中序遍历的结果是有序的。
如果需要保证其性能则需要进行平衡策略，使其成为二叉平衡搜索树。
图
将树的概念进行再扩展，不需要强制指定这个数据类型需要有根即为图。
图可以定义为点集+边集。