第3章堆栈和队列案例分析.ppt

第3章 堆栈和队列 3.1 堆栈 3.2 堆栈的应用举例 3.3 队列 3.4 队列的应用举例 3.1 堆栈 3.1.1 堆栈的基本概念 3.1.2 顺序栈及其操作 3.1.3 链栈及其操作 3.1.1 堆栈的基本概念 1. 堆栈的定义 2. 堆栈与线性表的区别与联系 3. 堆栈的特征 4. 堆栈的抽象数据类型 1. 堆栈的定义 堆栈（stack）是一种特殊的线性表，这种表只能在固定的一端进行插入与删除操作。 通常称固定插入与删除的一端为栈顶(top)，而另一端称为栈底(bottom)，位于栈顶和栈底的元素分别称为顶元和底元，当表中无元素时，称为空栈。 2. 堆栈与线性表的区别与联系 ⑴栈是特殊的线性表。 ⑵栈的插入与删除运算只能在栈顶进行，而线性表的插入和删除运算可在线性表中的任意位置进行。 3. 堆栈的特征 根据堆栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素。这样，最后入栈的数据元素总是最先退出堆栈，因此，堆栈也称为后进先出表(LIFO) ，见图3.1。 堆栈的操作过程演示 图3.1 4. 堆栈的抽象数据类型 ADT Stack{ Data： 堆栈中的数据元素具有相同类型及先进后出特性，相邻元素具有前驱和后继的关系。 Operation： InitStack(S, maxsize, incresize) 操作结果：构造一个容量为maxsize的空栈S。 ClearStack(S) 初始条件：栈S已存在。 操作结果：将栈S清为空栈。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回S的元素个数，即栈的长度。 Push(S，e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop(S，e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素并用e返回其值。 GetTop(S，e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 StackTraverse(S) 初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次输出S中的各个数据元素。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回true；否则返回false。 DestroyStack(S) 初始条件：栈S已存在。 操作结果：栈S被撤销。 }ADT Stack 3.1.2 顺序栈及其操作 1. 顺序栈的定义 2. 上溢与下溢 3. 判空与判满 4. 顺序栈的结构描述 5. 顺序栈的基本操作 6. 多栈共享邻接空间 1. 顺序栈的定义 顺序栈：即栈的顺序存储结构，它是利用一组地址连续的存储单元依次存放自栈底到栈顶之间的数据元素，同时附设指针top指标栈顶元素在顺序栈中的位置。如图3.2所示。 注意： 由于顺序栈都是在栈顶的位置上进行相关操作，因而栈顶指针top的当前位置是非常重要的。在对顺序栈进行初始化时，top的初值决定了堆栈的状态及对其操作的语句顺序，一般top的初值可以置0或-1，图3.2中top的初值为-1（堆栈中有一个元素）。 图3.2 2. 上溢与下溢 设存储栈元素的数组长度为stacksize ，top的初值为-1，则： ⑴当top= stacksize-1 时，表示系统作为栈用的存储空间已满，如图3.3(b)。如果还有元素要求进栈，则栈要溢出，即上溢，这时需要进行栈满处理。 ⑵当top=-1时，表示系统作为栈用的存贮区已空，栈中无任何元素，如图3.3(a)。这时若还要做出栈运算，则发生下溢。通常用栈空来作为控制转移的条件，表明数据已处理完毕。 图3.3 3. 判空与判满 一般来说，在对顺序栈进行插入元素之前，要判断栈是否“栈满”，而对顺序栈进行删除元素之前要判栈是否“栈空”。 栈满： top= stacksize-1 栈空： top=-1 4. 顺序栈的结构描述 # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 typedef struct { ElemType *stack; int top;