厦门大学：《数据结构》课程教学课件（PPT讲稿）第三章 栈和队列

数据结构

数据结构

第三章 栈和队列 3.1栈 3.1.1抽象数据类型栈的定义 3.1.2栈的表示和实现 3.2栈的应用举例 3.2.1数制转换 3.2.2括号匹配的检验 3.2.3行编辑程序 3.2.4迷宫求解 3.2.5 表达式求值

第三章 栈和队列 3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序 3.2.4 迷宫求解 3.2.5 表达式求值

3.3栈与递归的实现 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列—队列的链式表示和实现 3.4.3循环队列—队列的顺序表示和实现 3.5离散事件模拟

3.3 栈与递归的实现 3.4 队列 3.4.1 抽象数据类型队列的定义 3.4.2 链队列——队列的链式表示和实现 3.4.3 循环队列——队列的顺序表示和实现 3.5 离散事件模拟

3.1.1栈 3.1.1栈的定义及基本运算 栈Stack)是限制在表的一端进行插入和删除 运算的线性表，通常称插入、删除的这一端 为栈顶(Top),另一端为栈底Bottom)。当表 中没有元素时称为空栈。 假设栈S=(a1,a2,a3,.a),则a称为栈底 元素，an为栈顶元素。栈中元素按a1,a2, a,a,的次序进栈，退栈的第一个元素应为 栈顶元素。换句话说，栈的修改是按后进先 出的原则进行的。因此，栈称为后进先出表 (LIFO

3.1.1 栈 3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除 运算的线性表，通常称插入、删除的这一端 为栈顶(Top)，另一端为栈底(Bottom)。当表 中没有元素时称为空栈。 假设栈S=(a1，a2，a3，.an )，则a1称为栈底 元素，an为栈顶元素。栈中元素按a1，a2， a3，.an的次序进栈，退栈的第一个元素应为 栈顶元素。换句话说，栈的修改是按后进先 出的原则进行的。因此，栈称为后进先出表 （LIFO）

3.1.2 顺序栈 由于栈是运算受限的线性表，」 因此线性 表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是 运算受限的线性表。因此，可用数组来实 现顺序栈。因为栈底位置是固定不变的 所以可以将栈底位置设置在数组的两端的 任何一个端点；栈顶位置是随着进栈和退 栈操作而变化的，故需用一个整型变量op 来表示

3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性 表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是 运算受限的线性表。因此，可用数组来实 现顺序栈。因为栈底位置是固定不变的， 所以可以将栈底位置设置在数组的两端的 任何一个端点；栈顶位置是随着进栈和退 栈操作而变化的，故需用一个整型变量top 来表示

例、一叠书或一叠盘子。 栈的抽象数据类型的定义如下：P45 栈顶 an an-1 a2 栈底 a1

例、一叠书或一叠盘子。 栈的抽象数据类型的定义如下：P45 a n a n-1 a2 a1 . 栈顶 栈底

7 6 5 4 3 21 top

top 7654321- 1

top E D top top B B top base base A base base

top用来指示当前栈顶的位置，通常称top为栈顶 指针。顺序栈的类型定义如下： #define STACK INIT SIZE #define STACKINCREMENT typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack;

top用来指示当前栈顶的位置，通常称top为栈顶 指针。顺序栈的类型定义如下： #define STACK_INIT_SIZE #define STACKINCREMENT typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack;

设S是SqStack类型的指针变量。若栈底 位置在向量的低端，即s->base是栈底元 素，那么栈顶指针s->top是正向增加的 即进栈时需将s->top加1，退栈时需将s >top减1。s->top==s->base表示空栈，s- >top-s->base==stacksize表示栈满。当栈满 时再做进栈运算必定产生空间溢出，简称 “上溢”；当栈空时再做退栈运算也将产生 溢出，简称“下溢”。上溢是一种出错状 态，应该设法避免之；下溢则可能是正常 现象，因为栈在程序中使用时，其初态或 终态都是空栈，所以下溢常常用来作为程 序控制转移的条件

设S是SqStack类型的指针变量。若栈底 位置在向量的低端，即s–>base是栈底元 素，那么栈顶指针s–>top是正向增加的， 即进栈时需将s–>top加1，退栈时需将s– >top 减1。s–>top==s->base表示空栈，s– >top-s->base ==stacksize表示栈满。当栈满 时再做进栈运算必定产生空间溢出，简称 “上溢” ;当栈空时再做退栈运算也将产生 溢出，简称“下溢”。上溢是一种出错状 态，应该设法避免之；下溢则可能是正常 现象，因为栈在程序中使用时，其初态或 终态都是空栈，所以下溢常常用来作为程 序控制转移的条件