数据结构（C语言描述）教学课件马秋菊第3章栈队列.ppt

《数据结构（C语言描述）教学课件马秋菊第3章栈队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.1栈3.2队列3.3栈和队列的典型应用小结第3章栈和队列2021/7/25第页本章学习目标栈的定义、栈的“后进先出”的操作规则；栈的顺序和链式存储结构；队列的定义、队列“先进先出”的操作规则；队列的顺序和链式存储结构;栈和队列的典型应用2021/7/25第页栈与队列是两种特殊的线性结构。从数据结构角度看它们是线性表，从操作的角度看它们是操作受限的线性表。在日常生活中我们会经常遇到栈与队列的实例。例如铁路调度中用到栈，铁路购票中用到了队列。栈和队列还广泛应用于各种软件系统中：（1）计算机对子程序的嵌套、中断的管理都用到了栈；（2）对键盘缓冲区的管理用到了队列。2

2、021/7/25第页3.1栈3.1.1栈的定义及基本运算a1a2an…进栈出栈栈底栈顶栈的插入和删除操作分别称为进栈和出栈。进栈是将一个数据元素存放在栈顶，出栈是将栈顶元素取出。图中a1称为栈底元素，an为栈顶元素。1.定义：栈(stack)是限定仅在表尾的一端进行插入或删除操作的线性表。允许进行插入或删除操作的一端称为栈顶(top)，而另一端称为栈底(bottom)。不含元素的栈称为空栈。2021/7/25第页例：栈中元素按a1，a2，a3的次序进栈，见图1。出(退)栈的第一个元素应为栈顶元素a3。图2是a3出栈的情况。图3是一个空栈，即（top=bottom）

3、。换句话说，栈的操作是按后进先出的原则进行的。因此，栈称为后进先出表（LastInFirstOut,简称LIFO）。a3出栈a1a2图2栈底栈顶出栈进栈栈底栈顶图3进栈栈底图1a1a2a3栈顶2021/7/25第页有关栈的操作主要有以下几种：⑴栈初始化：Init_Stack(S)；构造一个空栈。⑵判栈空：Empty_Stack(S)；若S为空栈，则返回TRUE或1，否则返回FALSE或0。⑶入栈：Push_Stack(S，x)；若栈不满，在栈S的顶部插入一个新元素x，x成为新的栈顶元素。⑷出栈：Pop_Stack(S)；若栈不空，将栈S的栈顶元素从栈中删除，并保存

4、该元素。⑸读栈顶元素：Top_Stack(s)；若栈不空，返回栈顶元素，栈的状态不发生变化。2021/7/25第页3.1.2栈的顺序存储结构及运算实现栈的顺序存储结构（顺序栈）是利用利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素。通常用一维数组来实现栈的顺序存储，数组小下标一端做栈底，设一个栈顶指针top指向栈顶元素，它随着插入和删除而变化。top=-1时为空栈，每进栈一个元素，指针top加1；每出栈一个元素，指针top减1。s.top0123n-1空栈…a1a2非空栈栈底栈顶typedefstruct{ElemTypeelem[MAXSIZE];int

5、top;}SeqStack；2021/7/25第页图(a)是空栈，s.top=-1；图(b)是A入栈，s.top=0，s.elem[0]=A；图(c)是B、C、D、E四个元素依次入栈之后，s.top=4，由于栈已满，若再入栈，则溢出；图(d)是E、D相继出栈，此时栈中还有3个元素，s.top=2，即栈顶指针指向C元素。s.top43210s.top=-1(a)空栈43210s.topAs.top=0(b)进栈s.top43210ABCDEs.top=4(c)栈满s.top43210ABCs.top=2(d)出栈2021/7/25第页(2)进栈：S->top加1（

6、正向增长）。(3)退栈：S->top减1。(4)空栈：S->top=-1。(5)栈满：S->TOP=MAXSIZE-1。(6)上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。(7)下溢：栈空时再做退栈运算将产生溢出，这是一种正常状态（因为栈的初态和终态都是空栈，下溢常用作程序控制转移的条件）。2021/7/25第页栈的主要算法实现1.置空栈（初始化栈）：⑴栈初始化：初始化栈顶指针。voidInit_SeqStack(SeqStack*s){s->top=-1;}intEmpty_SeqStack(SeqStack*s){if(s->top==-1)retur

7、nTRUE;elsereturnFALSE;}2.判空栈操作：s.top01234空栈2021/7/25第页3.进栈操作：intPush_SeqStack(SeqStack*s,ElemTypex){if(s->top==MAXSIZE-1)returnOVERFLOW;else{s->top++;s->elem[s->top]=x;returnOK;}}4.出栈操作：intPop_SeqStack(SeqStack*s,ElemType*y){if(Empty_SeqStack(s))returnOVERFLOW;else{*y=s->elem[s->top];

8、s->to