中国科学技术大学：《数据结构及其算法》课程PPT教学课件（Data Structure and Algorithm）第4章 栈和队列（主讲：刘东）

第4章栈和队列 4.1栈的基本概念 4.2栈的表示与实现 4.3栈的应用 4.4队列的基本概念 4.5队列表示与实现 4.6队列的应用 4.7递归及其应用 2021/1/29 数据结构及其算法第4章栈和队列

第4章 栈和队列 •4.1 栈的基本概念 •4.2 栈的表示与实现 •4.3 栈的应用 •4.4 队列的基本概念 •4.5 队列表示与实现 •4.6 队列的应用 •4.7 递归及其应用 2021/1/29 数据结构及其算法 第4章 栈和队列 2

4.1栈的基本概念 栈( stack):限定仅在表尾进行插入或删除操作的 线性表 从数据结构角度看,栈也是线性表,或操作受限的 线性表,称为限定性数据结构 Data structure (D,S) ·从抽象数据类型角度看,允许的操作不一样,则数 据类型不同 °ADT=( DSP) 2021/1/29 数据结构及其算法第4章栈和队列

4.1 栈的基本概念 •栈(stack)：限定仅在表尾进行插入或删除操作的 线性表 •从数据结构角度看，栈也是线性表，或操作受限的 线性表，称为限定性数据结构 •Data_Structure = (D,S) •从抽象数据类型角度看，允许的操作不一样，则数 据类型不同 •ADT = (D,S,P) 2021/1/29 数据结构及其算法 第4章 栈和队列 3

设栈=(a1ra2 a a1称为栈底( bottom)元素 a称为栈顶(top)元素 出栈栈 栈顶插入元素-入栈 栈顶删除元素-出栈 栈顶 后进先出(1 ast in first out l工FO a 栈底 a 詹天佑设计的人字形铁路 (北京青龙桥车站附近) 2021/1/29 数据结构及其算法第4章栈和队列

•设栈S = (a1,a2,...,an) • a1称为栈底(bottom)元素 • an称为栈顶(top)元素 •栈顶插入元素 – 入栈 •栈顶删除元素 – 出栈 •后进先出(last in first out, LIFO) 2021/1/29 数据结构及其算法 第4章 栈和队列 4 a1 a2 an … 栈顶 栈底 出栈 入栈 詹天佑设计的人字形铁路 （北京青龙桥车站附近）

42栈的表示与实现 顺序栈:栈的顺序存储结构 类似顺序表 由于总在栈顶插入、删除,保留栈顶位置方便操作 typedef struct i ElemType*elem;//基地址 int stacksize; /当前分配内存大小,单位是 sizeof( ELem Type) int top, /栈顶位置,定义为表长-1 SqStack 2021/1/29 数据结构及其算法第4章栈和队列

4.2 栈的表示与实现 •顺序栈：栈的顺序存储结构 • 类似顺序表 • 由于总在栈顶插入、删除，保留栈顶位置方便操作 2021/1/29 数据结构及其算法 第4章 栈和队列 5 typedef struct { ElemType *elem; // 基地址 int stacksize; // 当前分配内存大小，单位是sizeof(ElemType) int top; // 栈顶位置，定义为表长-1 } SqStack;

顺序栈基本操作的实现(算法4.1~4.3) void Initstack sq( sqstack &S, int size)t Selem= new ElemType[size]; s. stacksize maize s top =-1, void Destroystack sq(Sqstack &s)i delete [selem; s. stacksize =0: S top bool GetTop sq( SqStack S, ElemType &e)i if (s top ==-1) return false; e selem[s top return true 2021/1/29 数据结构及其算法第4章栈和队列

•顺序栈基本操作的实现（算法4.1~4.3） 2021/1/29 数据结构及其算法 第4章 栈和队列 6 void InitStack_sq(SqStack &S, int msize) { S.elem = new ElemType[msize]; S.stacksize = msize; S.top = -1; } void DestroyStack_sq(SqStack &S) { delete []S.elem; S.stacksize = 0; S.top = -1; } bool GetTop_sq(SqStack S, ElemType &e) { if (S.top == -1) return false; e = S.elem[S.top]; return true; }

顺序栈基本操作的实现(算法4.4、4.5) const int SQSTACK INC SIZE = 10; void Increment (SqStack &S, int inc size= SQSTACK_INC_SIZE)[ ElemType *a= new ElemType[s stacksize inc size]; for (int i=0; i<=S top; ++i)alil=selem[i] delete Selem;selem=a; s. stacksize + inc size; void Push sq (SqStack &S, ElemType e)i if (s top== S. stacksize-1)Increment(S); elem[++s top]=ej bool Pop sq(sqstack &S, ElemType &e)t if (stop ==-1)return false; e=selems.top--] return true 2021/1/29 数据结构及其算法第4章栈和队列

•顺序栈基本操作的实现（算法4.4、4.5） 2021/1/29 数据结构及其算法 第4章 栈和队列 7 const int SQSTACK_INC_SIZE = 10; void Increment(SqStack &S, int inc_size = SQSTACK_INC_SIZE) { ElemType *a = new ElemType[S.stacksize + inc_size]; for (int i=0; i<=S.top; ++i) a[i] = S.elem[i]; delete []S.elem; S.elem = a; S.stacksize += inc_size; } void Push_sq(SqStack &S, ElemType e) { if (S.top == S.stacksize-1) Increment(S); S.elem[++S.top] = e; } bool Pop_sq(SqStack &S, ElemType &e) { if (S.top == -1) return false; e = S.elem[S.top--]; return true; }

链栈:栈的链式存储结构 类似链表 由于插入、删除只在栈顶进行,因此将栈顶设为首元结点, 方便操作 typedef LinkList LinkStack 链栈基本操作的实现(算法4.6、4.7) void Initstack L(LinkStack &s)i SE NULL data next 找顶 void DestroyStack L(LinkStack &s)i While(S)i Linkstack p= S;S=S->next; delete p; A栈底 2021/1/29 数据结构及其算法第4章栈和队列

•链栈：栈的链式存储结构 • 类似链表 • 由于插入、删除只在栈顶进行，因此将栈顶设为首元结点， 方便操作 •链栈基本操作的实现（算法4.6、4.7） 2021/1/29 数据结构及其算法 第4章 栈和队列 8 typedef LinkList LinkStack; void InitStack_L(LinkStack &S) { S = NULL; } void DestroyStack_L(LinkStack &S) { while (S) { LinkStack p = S; S = S->next; delete p; } }

链栈基本操作的实现(算法4.8~4.10) bool GetTop L(LinkStack S, Elem Type &e)i if(s return false; s->data; return true; void Push L(LinkStack &S, Elem Type e)i Linkstack p= new LNode p->data =e; p->next =S;s=p; bool Pop L(LinkStack &S, Elem Type &e)i if (s return false; LinkStack p= S:S=S->next p->data; delete p; return true; 思考:顺序栈和链栈何者更优?为什么? 2021/1/29 数据结构及其算法第4章栈和队列

•链栈基本操作的实现（算法4.8~4.10） 2021/1/29 数据结构及其算法 第4章 栈和队列 9 bool GetTop_L(LinkStack S, ElemType &e) { if (!S) return false; e = S->data; return true; } void Push_L(LinkStack &S, ElemType e) { LinkStack p = new LNode; p->data = e; p->next = S; S = p; } bool Pop_L(LinkStack &S, ElemType &e) { if (!S) return false; LinkStack p = S; S = S->next; e = p->data; delete p; return true; } 思考：顺序栈和链栈何者更优？为什么？

4.3栈的应用 例:数制转换问题 基本 N=( n div o)×d+ n mod d 计算过程 算出的余数逆序排列即为输出结果 81348 余数可以利用栈实现 8168 算法4.11 821 void conversion (int N, int d)i if(n<=0 d<=0)ErrorMsg("Input error); 82 Stack S; Initstack(s); ile(N)i Push(S, N%d) N/d;] int e (1348)10=(2504)8 While(Pop(s, e))icout < e; y 止t<<endl 2021/1/29 数据结构及其算法第4章栈和队列

4.3 栈的应用 •例：数制转换问题 •基本等式：N = (N div d) × d + N mod d •计算过程 2021/1/29 数据结构及其算法 第4章 栈和队列 10 8 1348 8 168 8 21 8 2 0 余数 4 0 5 2 (1348)10=(2504)8 算出的余数逆序排列即为输出结果 可以利用栈实现 算法4.11 void conversion(int N, int d) { if (N<=0 || d<=0) ErrorMsg("Input error"); Stack S; InitStack(S); while (N) { Push(S, N%d); N = N/d; } int e; while (Pop(S, e)) { cout << e; } cout << endl; }

例:括号匹配问题 如{[(3+5)×2]-7}÷3是合法的表达式, [(3+5]×2)-7或者(3+5)×2]-7)÷3非法 规则:从左向右,第一个出现的右括号需要和最后 个出现的左括号配对,“后进先出” 算法4.12 初始化栈 从左向右读入表达式中的括号 如果是左括号,进栈 如果是右括号,检查栈顶的左括号是否与它配对,若配对则左括 号出栈,否则错误 读入结束后,栈应该是空的,否则错误 思考:如何对算法进行改进,进一步检查括号的优 先级?即:[]中不能有{},()中不能有[]和{} 2021/1/29 数据结构及其算法第4章栈和队列

•例：括号匹配问题 •如{[(3+5)×2]-7}÷3是合法的表达式， [(3+5]×2)-7或者((3+5)×2]-7)÷3非法 •规则：从左向右，第一个出现的右括号需要和最后 一个出现的左括号配对，“后进先出” •算法4.12 • 初始化栈 • 从左向右读入表达式中的括号 • 如果是左括号，进栈 • 如果是右括号，检查栈顶的左括号是否与它配对，若配对则左括 号出栈，否则错误 • 读入结束后，栈应该是空的，否则错误 •思考：如何对算法进行改进，进一步检查括号的优 先级？即：[]中不能有{}，()中不能有[]和{} 2021/1/29 数据结构及其算法 第4章 栈和队列 11