《《数据结构（C语言描述）》-马秋菊-电子教案 第3章栈队列》由会员分享，可在线阅读，更多相关《《数据结构（C语言描述）》-马秋菊-电子教案 第3章栈队列（47页珍藏版）》请在金锄头文库上搜索。
1、2019年5月24日星期五,第1页,3.1 栈,3.2 队列,3.3 栈和队列的典型应用,小结,第3章 栈和队列,2019年5月24日星期五,第2页,本章学习目标,栈的定义、栈的“后进先出”的操作规则； 栈的顺序和链式存储结构； 队列的定义、队列“先进先出”的操作规则； 队列的顺序和链式存储结构; 栈和队列的典型应用,2019年5月24日星期五,第3页,栈与队列是两种特殊的线性结构。从数据结构角度看它们是线性表，从操作的角度看它们是操作受限的线性表。在日常生活中我们会经常遇到栈与队列的实例。例如铁路调度中用到栈，铁路购票中用到了队列。,栈和队列还广泛应用于各种软件系统中：（1）计算机对子程序的
2、嵌套、中断的管理都用到了栈； （2）对键盘缓冲区的管理用到了队列。,2019年5月24日星期五,第4页,3.1 栈 3.1.1 栈的定义及基本运算,1.定义：栈(stack)是限定仅在表尾的一端进行插入或删除操作的线性表。允许进行插入或删除操作的一端称为栈顶(top)，而另一端称为栈底(bottom)。不含元素的栈称为空栈。,2019年5月24日星期五,第5页,例：栈中元素按a1，a2，a3的次序进栈，见图1。出(退)栈的第一个元素应为栈顶元素a3 。图2是a3出栈的情况。图3是一个空栈，即（top=bottom）。换句话说，栈的操作是按后进先出的原则进行的。因此，栈称为后进先出表（ Last
3、 In First Out,简称LIFO）。,2019年5月24日星期五,第6页,有关栈的操作主要有以下几种： 栈初始化：Init_Stack(S) ；构造一个空栈。 判栈空：Empty_Stack(S)；若S为空栈，则返回TRUE或1，否则返回FALSE或0。 入栈：Push_Stack(S，x)；若栈不满，在栈S的顶部插入一个新元素x，x成为新的栈顶元素。 出栈：Pop_Stack(S)；若栈不空，将栈S的栈顶元素从栈中删除，并保存该元素。 读栈顶元素：Top_Stack(s)；若栈不空，返回栈顶元素，栈的状态不发生变化。,2019年5月24日星期五,第7页,3.1.2 栈的顺序存储结构及
4、运算实现,栈的顺序存储结构（顺序栈 ）是利用利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素。通常用一维数组来实现栈的顺序存储，数组小下标一端做栈底，设一个栈顶指针top指向栈顶元素，它随着插入和删除而变化。,top=-1时为空栈， 每进栈一个元素，指针top加1；每出栈一个元素，指针top减1。,typedef struct ElemType elemMAXSIZE; int top; SeqStack；,2019年5月24日星期五,第8页,图(a)是空栈，s.top= -1； 图(b)是A入栈，s.top=0，s.elem 0= A； 图(c) 是B、C、D、E四个元素依次入栈之后
5、，s.top=4，由于栈已满，若再入栈，则溢出； 图(d)是E、D相继出栈，此时栈中还有3个元素，s.top=2，即栈顶指针指向C元素。,2019年5月24日星期五,第9页,(2)进栈：S- top加1（正向增长）。 (3)退栈：S- top减1。 (4)空栈：S-top=-1。 (5)栈满：S-TOP=MAXSIZE-1。 (6)上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。 (7)下溢：栈空时再做退栈运算将产生溢出，这是一种正常状态（因为栈的初态和终态都是空栈，下溢常用作程序控制转移的条件）。,2019年5月24日星期五,第10页,栈的主要算法实现,1.置空栈（初始化栈）： 栈初始
6、化：初始化栈顶指针。 void Init_SeqStack(SeqStack *s) s-top=-1; ,int Empty_SeqStack(SeqStack *s) if (s-top=-1) return TRUE; else return FALSE; ,2.判空栈操作：,2019年5月24日星期五,第11页,3.进栈操作： int Push_SeqStack (SeqStack *s, ElemType x) if (s-top=MAXSIZE-1) return OVERFLOW ; else s-top+ ; s-elems-top=x ; return OK; ,4.出栈操作
7、： int Pop_SeqStack(SeqStack *s, ElemType *y) if (Empty_SeqStack ( s ) ) return OVERFLOW; else *y=s-elems-top; s-top-; return OK ,”90”出栈,2019年5月24日星期五,第12页,5.取栈顶元素 ElemType Top_SeqStack (SeqStack *s) if ( Empty_SeqStack ( s ) ) return OVERFLOW ; else return (s-elems-top ) ; ,*关于顺序栈的约定和主要运算的思考： 如果约定顺序
8、栈栈空为：s-top=0，则顺序栈下述的几种运算如何描述？ 置空栈、判栈空、进栈、退栈、取栈顶元素。,2019年5月24日星期五,第13页,例题：假设有3个元素a，b，c，入栈顺序是a，b，c，则它们的出栈顺序有几种可能？,1. a b c顺序进栈则出栈顺序为 c b a; 2. a 进栈，a出栈，然后b、c 进栈，再顺序出栈 ，则出栈顺序为a c b； 3. a 进栈， a出栈 ； b进栈， b出栈 ； c进栈， c出栈 ；则出栈顺序为a b c； 4. a、b进栈，a、b 出栈 然后 c 进栈，再出栈 ，则出栈顺序为b a c； 5. a、b 进栈 , b出栈; c进栈 ，然后出栈。则出栈
9、顺序为b c a；,思考题：出栈顺序有可能出现c a b的情况吗？,2019年5月24日星期五,第14页,问题：当程序中同时使用几个栈时，如何防止栈的上溢？,方法一：将栈的容量加到足够大，但这种方法由于事先难以估计容量，有可能浪费空间。,方法二：使用两个（或多个）栈共享存储空间办法。两栈的栈底分别设在给定存储空间的两端，然后各自向中间伸延，当两栈的栈顶相遇时才可能发生溢出。,2019年5月24日星期五,第15页,3.1.3 栈的链式存储结构及运算实现,栈也可以用单链表作为存储结构。一个链栈由它的栈顶指针唯一确定 。假设 top 是StackNode * 类型的变量，则 top 指向栈顶结点，t
10、op=NULL时，链栈为空。,2019年5月24日星期五,第16页, 置空栈 void Init_LS（StackNode *top） top = NULL; ,时间复杂度O(1), 判栈空 int Empty_LS（StackNode *top ） return top=NULL; , 入栈 StackNode *Push_LS（StackNode *top , ElemType x） StackNode *p=(StackNode*)malloc（sizeof（StackNode）; p-data=x; p-next=top; top=p ; return top; ,2019年5月24日
11、星期五,第17页, 出栈 int Pop_LS(StackNode *top , ElemType *y) StackNode *p; if （Empty_LS（top） printf (“Stack Underflow.“) ; /* 下溢 */ return OVERFLOW; else *y=top-data ; p=top ; top=top-next ; free (p) ; return OK ; ,2019年5月24日星期五,第18页, 取栈顶元素 int GetTop(StackNode *top, ElemType *y) if ( Empty_LS(top) ) print
12、f (“Stack underflow.”) ; /* 下溢 */ return OVERFLOW; else *y=top-data ; return OK ; ,2019年5月24日星期五,第19页,3.2 队列,3.2.1 队列的定义及基本运算 队列(Queue)也是一种操作受限制的线性表，它只允许在表的一端进行插入，通常称为入队，而在另一端进行删除，通常称为出队。允许出队的一端称为队头(front)，允许入队的一端称为队尾(rear)。,如果队列按照a1 a2 a3 an顺序入队，则出队顺序同样为a1 a2 a3 an ；即先进队列的元素先出队列，后进队列的元素后出队列。队列具有先进先
13、出(First In First Out ,简称FIFO)的特性。,2019年5月24日星期五,第20页,队列的例子：（1）如等待购物的顾客总是按先来后到的次序排成队，先得到服务的顾客是站在队头的先来者，而后到的人总是排在队的末尾。 （2）操作系统中的作业队列也是先进先出结构。,在队列上进行的基本操作有： 队列初始化：Init_Queue(Q)；构造了一个空队列。 判队空操作：Empty_Queue(Q)；若Q为空队列，则返回TRUE或1，否则返回FALSE或0。 入队操作：In_Queue(Q,x)；在队列Q的尾部插入一个新元素。 出队操作：Out_Queue(Q,*y)；删除队列Q的头元素
14、，并保存到*y中。 读队头元素：Front_Queue(Q,x)；读队头元素，并返回其值，队列的状态不变。,2019年5月24日星期五,第21页,3.2.2 队列的顺序存储结构及运算实现,队列的顺序存储结构和顺序栈类似。由于队列的操作是在两端进行的，采用以下的顺序存储结构： typedef struct ElemType elemMAXSIZE ; int rear, front; /* 队头、队尾指针 */ SeQueue;,设sq是SeQueue类型的变量，则队列的数据区为：sq.elem0sq.elemMAXSIZE-1，队头指针为：sq.front，队尾指针为：sq.rear，在队列初
15、始化时sq.front=sq.rear=0。,2019年5月24日星期五,第22页,插入一个元素时，先存入值：sq.elemsq.rear=x; 然后队尾指针增1：sq.rear+; 删除一个元素时，先将队头指针指向的数据取出送y：y=sq.elemsq.front；然后队头指针增1：sq.front+;,2019年5月24日星期五,第23页,问题引入：当队列处于“队满”状况时，队列的实际可用空间并没有占满。,把Sq.elem0接在Sq.elem5之后，头尾指针变化也是一个环，如图(1)。,显然Sq. front= Sq. rear不是判队满的条件。 Sq. front= Sq. rear不能判队空。,sq.front,2019年5月24日星期五,第24页,判断队列是空还是满，有两种处理方法： 1）另设一个标志位以区分队列是空还是满。,入队时Sq . rear时要加1，实现方法：,2）约定队空条件仍是Sq. front= Sq. rear ，而队满条件为队尾指针加1等于队头指针。损失一个元素空间。,Sq.Rear =(Sq.rear +1)% MAXSIZE，出队时Sq.front也同理。,循环队列的类型定义及基本运算 :, 置空队 void Init_SeQueue(CirSeQueue *sq) sq-front=sq-rear=0 ; ,2019年5月
