《数据结构与算法》第3章 栈和队列

第3章栈和队列 3.1栈 32栈的应用举例 33栈与递归的实现 34队列 第3章 2021/2/25

第3章 2021/2/25 1 第3章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列

31栈( Stack 1定y:限定只在表的一端(表尾进行 插入和删除操作的线性表 特点:后进先出(L∥FO)(弹出 进栈 (压入) 允许插入和删除 的一端称为栈顶 op -1 ←表尾 (top),另一端称 为栈底( bottom) a1 bottom→ Co ←表头 2021/2/25 第3章

2021/2/25 第3章 2 3.1 栈 ( Stack ) 1.定义：限定只在表的一端(表尾)进行 插入和删除操作的线性表 特点:后进先出(LIFO) 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 表尾 表头

2.栈的表示和实现 1)顺序栈—栈的顺序存储结构 2)链栈——栈的链式存储结构 3)静态分配整型指针 3 第3章 2021/2/25

第3章 2021/2/25 3 2. 栈的表示和实现 1）顺序栈——栈的顺序存储结构 2）链栈——栈的链式存储结构 3）静态分配整型指针

1)顺序栈—栈的顺序存储结构 限定在表尾进行插入和删除操作的顺序表 类型定义:p46 typedef struct i SElem Type * base SElem lype top int stacksize SqStack Sqstack S; (顺序栈有三个域:栈顶和栈底指针,栈的最大容量) 第3章 2021/2/25

第3章 2021/2/25 4 1）顺序栈——栈的顺序存储结构 限定在表尾进行插入和删除操作的顺序表 类型定义： p46 typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; SqStack s; （顺序栈有三个域：栈顶和栈底指针，栈的最大容量）

说明: base称为栈底指针,始终指向栈底; 当base=NULL时,表明栈结构不存在 op为栈顶指针 a.top的初始值指向栈底,即top=base b.空栈:当top-base时为栈空的标记 C.当栈非空时,top的位置:指向当前栈 顶元素的下一个位置 stacksize—当前栈可使用的最大容量 5 第3章 2021/2/25

第3章 2021/2/25 5 说明： ▪ base称为栈底指针，始终指向栈底； 当base = NULL时，表明栈结构不存在。 ▪ top为栈顶指针 a. top的初始值指向栈底，即top=base b. 空栈：当top=base时为栈空的标记 c. 当栈非空时，top的位置：指向当前栈 顶元素的下一个位置 ▪ stacksize ——当前栈可使用的最大容量

进栈示例 tacksize e edc top C ba base base→ ase- 空栈 a进栈 b进栈 进栈进栈溢出 6 第3章 2021/2/25

第3章 2021/2/25 6 进栈示例 base base base base base stacksize

退栈示例 e top-e d|top→d [a tse → k退栈 e退栈 d退栈 a退栈 空栈 第3章 2021/2/25

第3章 2021/2/25 7 退栈示例 base base base base base

几点说明: 栈空条件:s.top=s.base此时不能出栈 栈满条件:s.top-s.base>=s. stacksize 进栈操作:*stop++=e;或*stop=e;stop++; 退栈操作:c=*-stop;或stop-;c=*stop; 当栈满时再做进栈运算必定产生空间溢出, 简称“上溢”; 当栈空时再做退栈运算也将产生溢出,简 称“下溢 8 第3章 2021/2/25

第3章 2021/2/25 8 几点说明： ⚫ 栈空条件：s. top =s. base 此时不能出栈 ⚫ 栈满条件：s.top-s.base>=s.stacksize ⚫ 进栈操作：*s.top++=e; 或*s.top=e; s.top++; ⚫ 退栈操作：e=*--s.top； 或s.top--； e=*s.top； ⚫ 当栈满时再做进栈运算必定产生空间溢出， 简称“上溢”; ⚫ 当栈空时再做退栈运算也将产生溢出，简 称“下溢

基本操作的实现 栈的初始化操作p47 Status InitStack(SqStack &S) 取栈顶元素p4 Status GetTop(Sqstack s, sElem Type &e) 进栈操作p47 Status Push(sqStack &s, selem Type e) 退栈操作p47 Status Pop(sqstack &s, selem Type &e) 第3章 2021/2/25

第3章 2021/2/25 9 基本操作的实现 ⚫ 栈的初始化操作 p47 Status InitStack(SqStack &S) ⚫ 取栈顶元素 p47 Status GetTop(SqStack S, SElemType &e) ⚫ 进栈操作 p47 Status Push(SqStack &S, SElemType e) ⚫ 退栈操作 p47 Status Pop(SqStack &S, SElemType &e)

栈的初始化操作p47 Status InitStack(SqStack &s)i S base=(sElem Type )malloc(STACK INIT size x sizeof(elem Type)); if(S base)return(OVERFLOW) S top S base S. stacksize= STACK INIT SIZE return OK 第3章 2021/2/25

第3章 2021/2/25 10 栈的初始化操作 p47 Status InitStack (SqStack &S) { S.base = (SElemType )malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!S.base) return (OVERFLOW); S.top=S.base; S.stacksize = STACK_INIT_SIZE; return OK; }