---

1 栈（后进先出）

特点：

  • 插入（insert）–压入（push），新元素总是在最顶层
  • 删除（delete）–弹出（pop），新元素总是第一个删除

图示：
栈操作示意图

2 队列（先进先出）

特点

  • 插入（insert）–入队（ENQUEUE）,新元素总在最末尾
  • 删除（delete）–出队（DEQUEUE）,弹出的元素总是最旧的那个

图示：
队列操作示意图
注明：队列为卷绕型，若tail[Q]=length[Q],则tail[Q]=1；

上溢：对一个满序列插入一个新元素
下溢：对一个空序列删除一个元素

3 链表

双向链表：每一个元素都是一个对象，一个对象包含一个关键字域合两个指针域（next，prev）

图示：
双向链表图示

双向循环链表：带有哨兵，用于简化边界条件的处理

图示：
双向循环链表图示

4 指针和对象

prev,key,next在这里作为指针

1.对象的多数组表示（三个数组prev,key,next）
对象的多数组图示
2.对象的单数组表示
对象的单数组图示
3.对象的分配与释放

  • 将多数组中剩余的对象（free）组成一个单链表，称为自由表

  • 自由表类似于一个栈，可以通过栈操作PUSH和POP来对自由表实现分配（ALLOCATE）和释放（FREE）过程

图示：
对象的分配与释放图示

5 有根树

就是二叉树.结构包括根（root），left（左孩子），right（右孩子）
图示：
有根树图示