栈和队列课件

1、2022-1-21栈和队列1第三章第三章栈和队列栈和队列两种特殊的线性表两种特殊的线性表2022-1-21栈和队列2栈和队列栈和队列3.1 栈栈3.2 栈的应用举例栈的应用举例3.3 栈与递归栈与递归3.4 队列队列2022-1-21栈和队列33.1 栈栈 栈栈是仅限定在表的一端操作是仅限定在表的一端操作的线性表。它的插入和删除都只的线性表。它的插入和删除都只能在表的一端进行。能在表的一端进行。定义定义2022-1-21栈和队列4 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2

2、,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT Stack3.1.1 栈的类型定义栈的类型定义2022-1-21栈和队列5InitStack(&S) / 构造一个空栈构造一个空栈 S基本操作：基本操作：DestroyStack(&S) / 销毁栈销毁栈 S GetTop(S, &e) / 弹出弹出 S 栈顶元素。栈顶元素。Push(&S, e) /向栈内推入元素向栈内推入元素 e2022-1-21栈和队列6栈的表示和实现栈的表示和实现 顺序存储顺序存储 链表存储链表存储栈的存储方式栈的存储方式栈的性质栈的性质后进先出后进先出2022

3、-1-21栈和队列7栈的顺序存储栈的顺序存储typedef struct char ST101 int top; stack;stack S;d4c3b2a1栈顶栈顶Top栈底栈底stop2022-1-21栈和队列8栈的顺序存储栈的顺序存储# define Maxsize 100+1typedef struct elemtype STMaxsize int top; stack;stack S;d4c3b2a1栈顶栈顶top栈底栈底tops2022-1-21栈和队列9栈的顺序存储栈的顺序存储1.栈空的条件：栈空的条件： S.top = 04321栈顶栈顶Top2022-1-21栈和队列10Pu

4、sh(&S, e) /栈栈 S 已存在，压入元素已存在，压入元素 e if (s.top= Maxsize -1) printf(栈满溢出栈满溢出); else S.top+; S.STtop=e; return OK;4321Top2022-1-21栈和队列112. 2. 栈的压入操作栈的压入操作Push(&S, e) /栈栈 S 已存在，压入元素已存在，压入元素 e if (s.top= Maxsize -1) printf(栈满溢出栈满溢出); else S.top+; S.STs.top=e; return OK;4321Top2350Top2022-1-21栈和队列1

5、23. 3. 栈的弹出操作栈的弹出操作pop (&S, e) /栈栈 S 已存在，压入元素已存在，压入元素 e if (s.top= 0) printf(栈空下溢栈空下溢); else e =S.STs.top; S.top - -; return OK;43212350TopTopTop2022-1-21栈和队列13例题例题一个栈的入栈序列是一个栈的入栈序列是12345，则栈的不可能，则栈的不可能的出栈序列是什么？的出栈序列是什么？判断一个顺序栈判断一个顺序栈st(最多元素为最多元素为maxsize)为为栈空栈空he栈满的条件分别是栈满的条件分别是 和和 A) st-top !=0

6、B) st-top=0 C) st-top != maxsize -1 D) st-top = maxsize -1 BD2022-1-21栈和队列14栈的链式存储栈的链式存储head211830754256 进栈进栈 出栈出栈 读栈顶元素读栈顶元素2022-1-21栈和队列153.2 栈的应用举例栈的应用举例ClearStack(S) 重置重置S为空栈为空栈empty (s) 判断栈空判断栈空push(s，ch) 将一个元素将一个元素e推入栈推入栈spop(s) 将栈顶元素弹出，且返回其元素将栈顶元素弹出，且返回其元素gettop(s,e) 取栈顶元素取栈顶元素2022-1-21栈和队列16

7、 例例1 1 行编辑程序问题行编辑程序问题 假设假设“#”为退格符，表示前一个字为退格符，表示前一个字 符无效；符无效；“”为退行符，表示当前行无效；为退行符，表示当前行无效； 设立一个设立一个栈栈（输入缓冲区），用以（输入缓冲区），用以接受用户输入的一行字符，然后逐行接受用户输入的一行字符，然后逐行存入用户数据区。存入用户数据区。2022-1-21栈和队列17假设从终端接受了这样两行字符：假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行： while (*s) putchar(*s+);2022-1-21栈和队

8、列18假设从终端接受了这样两行字符：假设从终端接受了这样两行字符： whli#ilr#eilhw当当 # : Pop(S,e) /弹出当当 : ClearStack(S)/清栈否则否则 入栈入栈2022-1-21栈和队列19假设从终端接受了这样两行字符：假设从终端接受了这样两行字符： whli#ilr#eilhw当当 # : Pop(S,e) /弹出当当 : ClearStack(S)/清栈否则否则 入栈入栈2022-1-21栈和队列20假设从终端接受了这样两行字符：假设从终端接受了这样两行字符： whli#ilr#eilhw当当 # : Pop(S,e) /弹出当当 : ClearStack

9、(S)/清栈否则否则 入栈入栈2022-1-21栈和队列21 while (ch != EOF & ch != n) switch (ch) case # : Pop(S,e); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符 ClearStack(S); / 重置S为空栈if (ch != EOF) ch = getchar();while (ch != EOF) /EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；

10、ilhw2022-1-21栈和队列22表达式表达式 := (操作数操作数 1) + (运算符运算符op) + (操作数操作数 2) 操作数操作数 := 简单变量简单变量 | 表达式表达式 简单变量简单变量 : = 标识符标识符 | 无符号整数无符号整数例例2 2 表达式求值表达式求值-利用算符优先级法则利用算符优先级法则2022-1-21栈和队列23算符间的优先级关系算符间的优先级关系 1 2+*/（）#+ * / （ =） # =2022-1-21栈和队列24例如例如: Exp = a b + (c d / e) f中缀式: #a b + c d / e f#使用两个栈：使用两个栈： 栈栈O

11、PTR寄存运算符寄存运算符OP （包括（）和#） 栈栈OPND寄存操作数寄存操作数 2022-1-21栈和队列25例如例如: #4+ 2 3 10 / 5 #OPTROPND#4+2022-1-21栈和队列26算符间的优先级关系算符间的优先级关系 1 2+*/（）#+ * / （ =） # =2022-1-21栈和队列27例如例如: #4+ 2 3 10 / 5 #OPTROPND#4+2+ + 2022-1-21栈和队列28算符间的优先级关系算符间的优先级关系 1 2+*/（）#+ * / （ =） # =2022-1-21栈和队列29例如例如: #4+ 2 3 10 / 5 #OPTROP

12、ND#4+2 32022-1-21栈和队列30算符间的优先级关系算符间的优先级关系 1 2+*/（）#+ * / （ =） # =2022-1-21栈和队列31例如例如: #4+ 2 3 10 / 5 #OPTROPND#4+2 3退栈退栈 322 3=66进栈进栈10/2022-1-21栈和队列323.3 栈与递归的实现栈与递归的实现 求求n! Hanoi塔问题塔问题2022-1-21栈和队列33 例例1 求求n! (用递归调用用递归调用) 1 n=0fac= n (n-1)! n0int fac ( int n ) int f; if ( n=0) fac=1; else f= fac(n

13、-1) * n; return( f );main ( ) int n=3; p= fac (n); printf(%d,p); 2022-1-21栈和队列34 求求n! (用递归调用用递归调用) 1 n=0fac= n (n-1)! n0int fac ( int n ) int f; if ( n=0) fac=1; else f= fac(n-1) * n; return( f );main ( ) int n=3; p= fac (n); printf(%d,p); 将所有的将所有的实参实参、返回地址返回地址等信息传递给等信息传递给被调用函数被调用函数保存保存；为被调用函数的局部变量为

14、被调用函数的局部变量分配存储区分配存储区；将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。2022-1-21栈和队列35 求求n! (用递归调用用递归调用) 1 n=0,1fac= n (n-1)! n0int fac ( int n ) int f; if ( n=0) fac=1; else f= fac(n-1) * n; return( f );main ( ) int n=3; p= fac (n); printf(%d,p); 保存保存被调函数的被调函数的计算结果计算结果；释放释放被调函数的被调函数的数据区数据区；依照被调函数保存的返回地址将依照被调函数保存的返回地址将

15、控制转移控制转移到调用函数。到调用函数。2022-1-21栈和队列36递归的要点：递归的要点： 由系统提供一个信息栈，保留函数调用时由系统提供一个信息栈，保留函数调用时的相关信息（调用时的信息、返回地址、的相关信息（调用时的信息、返回地址、局部变量）；局部变量）； 每执行递归调用语句时，将有关信息送入每执行递归调用语句时，将有关信息送入栈，转入函数入口；栈，转入函数入口； 每当执行到返回语句时，保存每当执行到返回语句时，保存计算结果计算结果，释放被调函数的数据区，弹出释放被调函数的数据区，弹出返回地址返回地址返返回。回。2022-1-21栈和队列37多个函数嵌套调用的规则是：此时的内存管理实行

16、“栈式管理栈式管理”后调用先返回后调用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区 2022-1-21栈和队列38n=3;p= fac (n); printf(p); main ( )f= fac(n-1) *3; return( f );fac (3 )f= fac(n-1) *2; return( f );fac (2 )f= fac(n-1) *1; return( f );fac (1 )f= 1; return( f );fac (0 )2022-1-2

17、1栈和队列39n=3;p= fac (n); main ( )f= fac(n-1) *3; fac (3 )f= fac(n-1) *2; fac (2 )f= fac(n-1) *1; fac (1 )f= 1; return( f );fac (0 )fac(3)fac(2)fac(1)fac(0)RETn 地址地址3 L3 L3 L3 L3 L3 L3 Ln 地址地址3 L13 L13 L13 L13 L1n 地址地址2 L22 L22 L2n 地址地址1 L32022-1-21栈和队列40例例2 Hanoi 塔问题塔问题abc2022-1-21栈和队列41例例2 Hanoi 塔问题塔

18、问题abc2022-1-21栈和队列42例例2 Hanoi 塔问题塔问题abc2022-1-21栈和队列43例例2 Hanoi 塔问题塔问题abc2022-1-21栈和队列44void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if (n=1)2 move(x, 1, z); / 将编号为的圆盘从x移到z3 else 4 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔5 move(x, n, z); / 将

19、编号为n的圆盘从x移到z6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔7 8 2022-1-21栈和队列45void hanoi (int n, char x, char y, char z)12 if (n=1)3 move(x, 1, z); 4 else 5 hanoi(n-1, x, z, y); 6 move(x, n, z); 7 hanoi(n-1, y, x, z); 8 9 0 3 a b c返址 n x y z6 2 a c b6 1 a b c8 1 c a b 2022-1-21栈和队列463.4 队列队列2022-

20、1-21栈和队列473.4.1 抽象数据类型队列的定义抽象数据类型队列的定义队列：是一种队列：是一种先进先出先进先出的线性表，它的操的线性表，它的操作只能在表的两端进行。作只能在表的两端进行。队队尾尾队队首首a1 a2 a3 an-1 an2022-1-21栈和队列48 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头队列头， an 端为队列尾队列尾基本操作：基本操作： ADT Queue 队列的抽象数据类型队列的抽象数据类型2022-1-21

21、栈和队列49队列的基本操作：队列的基本操作：1、InitQueue(&Q) /创建空队列创建空队列Q2、DestroyQueue(&Q) /销毁队列销毁队列Q7、QueueLength(Q) /求队列长度求队列长度5、GetHead(Q, &e) /取队首元素取队首元素6、ClearQueue(&Q) /队列置空队列置空3、DelQueue(&Q, &e) /出队出队4、EnQueue(&Q, e) /入队入队2022-1-21栈和队列50QueueEmpty(Q)初始条件：队列队列Q已存在。已存在。 操作结果：若若Q为空队列，则返回为空

22、队列，则返回TRUE，否则返回，否则返回FALSE。2022-1-21栈和队列51QueueLength(Q) 初始条件：队列队列Q已存在。已存在。 操作结果：返回返回Q的元素个数，即队的元素个数，即队列的长度。列的长度。2022-1-21栈和队列52 GetHead(Q, &e) 初始条件：Q为非空队列。为非空队列。 操作结果：用用e返回返回Q的队头元素。的队头元素。a1a2an 2022-1-21栈和队列53 ClearQueue(&Q)初始条件：队列队列Q已存在。已存在。操作结果：将将Q清为空队列。清为空队列。2022-1-21栈和队列54 EnQueue(&Q,

23、 e) 初始条件：队列队列Q已存在。已存在。 操作结果：插入元素插入元素e为为Q的新的的新的队尾元素。队尾元素。a1a2ane 2022-1-21栈和队列55 DeQueue(&Q, &e) 初始条件：Q为非空队列。为非空队列。 操作结果：删除删除Q的队头元素，并的队头元素，并用用e返回其值。返回其值。a1a2an 2022-1-21栈和队列56队列的表示队列的表示 链式表示链式表示链队列链队列 顺序表示顺序表示循环队列循环队列2022-1-21栈和队列573.4.2 链队的表示和实现链队的表示和实现链队链队用链表表示的存储结构的队列用链表表示的存储结构的队列rearfront

24、frontrear链队列2022-1-21栈和队列58 typedef struct QNode / 结点类型结点类型 QElemType data; struct QNode *next; QNode, *QPtr;链队链队de结点结构结点结构2022-1-21栈和队列59 QPtr front; / 队头指针队头指针 QPtr rear; / 队尾指针队尾指针a1anfrontfront空队列空队列rearrearfront = rear表示表示12022-1-21栈和队列60typedef struct / 链队列类型链队列类型 QPtr front; / 队头指针队头指针 QPtr r

25、ear; / 队尾指针队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列表示表示22022-1-21栈和队列61 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QPtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK;2022-1-21栈和队列62 Status EnQueue (LinkQueue &Q, QEl

26、emType e) / 插入元素e为Q的新的队尾元素 p = (QPtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;2022-1-21栈和队列63 Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR if (Q.front = Q.rear) retu

27、rn ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;2022-1-21栈和队列64rearfrontfrontrear链队列2022-1-21栈和队列653.4.3 队列的顺序存储结构队列的顺序存储结构 顺序队列顺序队列数组表示数组表示 队列的顺序存储结构称为顺序队列。队列的顺序存储结构称为顺序队列。5432J31J20J1rearfront队首队首队尾队尾2022-1-21栈和队列661. 顺序队列顺序队列数组表

28、示数组表示初始化建空队列时令初始化建空队列时令543210rearfrontfront = rear = 02022-1-21栈和队列671. 顺序队列顺序队列数组表示数组表示入队时入队时: 加入结点加入结点; rear+1;543210rearfrontJ1rearrear2022-1-21栈和队列68rear1. 顺序队列顺序队列数组表示数组表示入队：入队：加加入结点入结点; 头指针头指针rear+1;543210rearfrontJ1rearJ2rearrearJ32022-1-21栈和队列691. 顺序队列顺序队列数组表示数组表示出队出队： 删除结点删除结点; 队头指针队头指针fron

29、t+1;543210frontJ1J2rearJ3J1frontfront在非空队列中，在非空队列中，头指针头指针front总是总是指向队头元素，指向队头元素，而尾指针而尾指针rear总是总是指向队尾元素的指向队尾元素的下一个位置下一个位置2022-1-21栈和队列70（1）入队操作）入队操作 enqueue (Q , x)if ( rear+1=MAX-1) printf (队满溢出队满溢出) else Qrear= x; rear +; return OK;2顺序队列的基本运算顺序队列的基本运算543J42J31J20J1rearfront2022-1-21栈和队列71 （2）出队操作）出

30、队操作 Dequeue (Q , e)if ( front=rear) return ERROR/队空队空 else e = Qfront; front +; return OK;543J42J31J20rearfront2022-1-21栈和队列7254J53J4210rearfront3. 循环队列循环队列if ( rear+1=MAX-1) 队满溢出队满溢出 在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，此时若有元素入列，就会发生“溢出”。在图中，虽然队尾指针已经指向最后一个位置，但事实上队列中还有空位置。也就是说，队列的存储空间并没有满，但队列却发生了溢出，我们称这种现象为假

31、溢出。2022-1-21栈和队列73解决的方法解决的方法:将队列看成是循环表将队列看成是循环表：MAXNUM-101rearfront循环队列示意54J53J4210frontrear2022-1-21栈和队列74但但当队满时当队满时rear=front：5J64J53J42J31J20J1frontrear2022-1-21栈和队列75但但当队满时当队满时rear=front当队空时当队空时rear=front：543210frontrear无法判断！无法判断！2022-1-21栈和队列76解决的方法解决的方法: :少用一的单元少用一的单元：54J53J42J31J20J1frontrear

32、队满条件队满条件(rear+1) mod max=front2022-1-21栈和队列77解决的方法解决的方法: :少用一的单元少用一的单元：543210frontrear队满条件队满条件(rear+1) mod max=front队空条件队空条件 front=rear2022-1-21栈和队列78入队入队Enqueue (Q, x) if (front = (rear+1) % max ) exit (over) else Qrear=x; rear= (rear+1) % max; return OK 2022-1-21栈和队列79出队出队Delqueue (Q, e) if (front = rear) exit (over) else e=Qfront; front = (front+1) % max; return OK 2022-