栈的插入和删除操作分别称为进栈和出栈。进栈是将一个数据元素存放在栈顶，出栈是将栈顶元素取出。
栈的操作是按后进先出的原则进行的。因此，栈称为后进先出表（ Last In First Out,简称LIFO）。 栈有两种存储表示方法:顺序存储和链式存储
栈的顺序存储结构（顺序栈 ）是利用利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素。通常用一维数组来实现栈的顺序存储，数组小下标一端做栈底，设一个栈顶指针top指向栈顶元素，它随着插入和删除而变化。
上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。
下溢：栈空时再做退栈运算将产生溢出，这是一种正常状态（因为栈的初态和终态都是空栈，下溢常用作程序控制转移的条件）。
因此，入栈要先判断栈是否满，出栈要先判断栈是否空。
假设有3个元素a，b，c，入栈顺序是a，b，c，则它们的出栈顺序有几种可能？ 解答：1. a b c顺序进栈则出栈顺序为 c b a;
2. a 进栈，a出栈，然后b、c 进栈，再顺序出栈 ，则出栈顺序为a c b； 3. a 进栈， a出栈 ； b进栈， b出栈 ； c进栈， c出栈 ；则出栈顺序为a b
c；
4. a、b进栈，a、b 出栈 然后 c 进栈，再出栈 ，则出栈顺序为b a c； 5. a、b 进栈 , b出栈; c进栈 ，然后出栈。则出栈顺序为b c a；
思考题：出栈顺序有可能出现c a b的情况吗？
2. 队列
队列(Queue)也是一种操作受限制的线性表，它只允许在表的一端进行插入，通常称为入队，而在另一端进行删除，通常称为出队。允许出队的一端称为队头(front)，允许入队的一端称为队尾(rear)。
如果队列按照a1 a2 a3 … an顺序入队，则出队顺序同样为a1 a2 a3 … an ；即先进队列的元素先出队列，后进队列的元素后出队列。队列具有先进先出(First In First Out ,简称FIFO)的特性。
3.数组
数组（Array）是由n(n>1)个相同类型数据元素a0，al，…ai…，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表，而线性子表中的每一个数据元素还可以再分解。
数组中每个元素都是由一个值和一组下标来确定的。同线性表一样，数组中的所有数据元素都必须属于同一数据类型。元素下标的个数被称为数组的维数。 数组与线性表的区别：在数组中不能进行插入、删除数据元素的操作。
【例4-2】选择题。设二维数组M的每个数据元素占6个存储单元，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要(Ⅰ)个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的(Ⅱ)元素的起始地址一致。
(Ⅰ) A.90 B.180 C.240 D.540
(Ⅱ) A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9]
【解】(1)二维数组M共有(8-0+1)×(10-1+1)=90个数据元素，所以共占 90×6=540个字节，即(Ⅰ)选D.
(2)M[8][5]的存储位置为： LOC(M[8][5])= LOC(M[0][1])+504 在(Ⅱ)中只有B.有表达是：
LOC(M[3][10])= LOC(M[0][1])+504,因此(Ⅱ) 选B.
第5章 树
树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。
树的基本术语：
二叉树(Binary Tree)是另一种重要的树型结构。是度为2的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。
二叉树的性质：
二叉树的存储结构：二叉树的存储结构也有顺序和链表两种结构。
二叉树的遍历：指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。 常用的是前三种方式，即NLR（称为前序或先根遍历）、LNR（称为中序或中根遍历）和LRN（称为后序或后根遍历）。
1．前序遍历
前序遍历的递归过程为： 若二叉树为空，遍历结束。否则 （1）访问根结点； （2）前序遍历左子树； （3）前序遍历右子树。
2．中序遍历
中序遍历的递归过程为： 若二叉树为空，遍历结束。否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 3．后序遍历
后序遍历的递归过程为： 若二叉树为空，遍历结束。否则 （1）后序遍历左子树； （2）后序遍历右子树。 （3）访问根结点；
例如
遍历结果:
AB
CE中序: D G B A E C 后序:G D B E C A
DG
哈夫曼（Huffman）树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。
最优二叉树或哈夫曼树
哈夫曼树（或最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树。
结论:
① 当叶子上的权值均相同时，完全二叉树一定是最优二叉树。否则完全二叉树不一定是最优二叉树。
② 在最优二叉树中，权值越大的叶子离根越近。 ③ 最优二叉树的形态不唯一，但WPL最小。 构造哈夫曼树：
例：W＝{3，4，5，8，6}的哈夫曼树的构造过程。为了直观起见，在图中把带权的叶子结点画成方形，其它非叶子结点仍为圆形。其带权路径长度为59。
34586374586326745116(c) 8(a) (b) 157348511651163(d) (e)74158
第6章 图
图G (Graph)是由非空的顶点集合V（G）和描述顶点之间关系的边集合E（G）构成，其形式定义为：G＝(V(G)，E(G))。简写为G＝(V，E)。
图的常用术语：
图示一种结构复杂的数据结构，常用的存储结构有邻接矩阵、邻接表。
V0V1V2V3
图6-6 无向图的邻接矩阵表示
142(a)33
?0??1A??0??1?101??001?001??110??00101001(b)01011000
