数据结构：第3章 栈和队列

1、第第3 3章章 栈和队列栈和队列 3.1 3.1 栈栈 3.2 3.2 队列队列 本章小结本章小结 3.1.1 3.1.1 栈的定义栈的定义 3.1.2 3.1.2 栈的顺序存储结构栈的顺序存储结构及其基本运算实现及其基本运算实现 3.1.3 3.1.3 栈的链式存储结构栈的链式存储结构及其基本运算的实现及其基本运算的实现3.1.4 3.1.4 栈的应用例子栈的应用例子3.1 3.1 栈栈 栈是一种只能在一端进行插入或删除操作的栈是一种只能在一端进行插入或删除操作的线性表线性表。表中允许进行插入、删除操作的一端称。表中允许进行插入、删除操作的一端称为为栈顶栈顶。 栈顶的当前位置是动态的栈顶的当

2、前位置是动态的,栈顶的当前位置由栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一一个称为栈顶指针的位置指示器指示。表的另一端称为端称为栈底栈底。 当栈中没有数据元素时当栈中没有数据元素时,称为称为空栈空栈。 栈的插入操作通常称为栈的插入操作通常称为进栈或入栈进栈或入栈,栈的删除栈的删除操作通常称为操作通常称为退栈或出栈退栈或出栈。3.1.1 3.1.1 栈的定义栈的定义 A6A5A4A3A2A1栈顶栈顶栈底栈底出栈出栈进栈进栈栈示意图栈示意图 例例 设有设有4个元素个元素a、b、c、d进栈进栈,给出它给出它们所有可能的出栈次序。们所有可能的出栈次序。 答答:所有可能的出栈次序如下所有

3、可能的出栈次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba 例例 设一个栈的输入序列为设一个栈的输入序列为A,B,C,D,则借助则借助一个栈所得到的输出序列不可能是一个栈所得到的输出序列不可能是 。(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C 答答:可以简单地推算可以简单地推算,得容易得出得容易得出D,A,B,C是是不可能的不可能的,因为因为D先出来先出来,说明说明A,B,C,D均在栈中均在栈中,按按照入栈顺序照入栈顺序,在栈中顺序应为在栈中顺序应

4、为D,C,B,A,出栈的顺序出栈的顺序只能是只能是D,C,B,A。所以本题答案为。所以本题答案为D。 例例 设设n个元素进栈序列是个元素进栈序列是1,2,3,n, 其输出序其输出序列是列是p1,p2,pn,若若p1=3,则则p2的值的值 。(A) 一定是一定是2(B) 一定是一定是1(C) 不可能是不可能是1 (D) 以上都不对以上都不对 答答:当当p1=3时时,说明说明1,2,3先进栈先进栈,立即出栈立即出栈3,然然后可能出栈后可能出栈,即为即为2,也可能也可能4或后面的元素进栈或后面的元素进栈,再出再出栈。因此栈。因此,p2可能是可能是2,也可能是也可能是4,n,但一定不能但一定不能是是1

5、。所以本题答案为。所以本题答案为C。ADT Stack 数据对象数据对象: D= a1, a2, a3, , an n0, 每个每个ai是是ElemType类型类型 数据关系数据关系: R=, , , 基本运算基本运算: InitStack(&s); 初始化一个栈初始化一个栈: 构造一个空栈构造一个空栈s ClearStack(&s); 销毁栈销毁栈: 释放栈占用的存储空间释放栈占用的存储空间 StackLength(s); 求栈求栈s的长度的长度 StackEmpty(s); 判断栈是否为空栈判断栈是否为空栈 Push(&s, e); 进栈进栈: 将新元素将新元素e入栈入栈,成为新栈顶元素成

6、为新栈顶元素 Pop( &s, &e) ; 出栈出栈: 从栈从栈s中退出栈顶元素中退出栈顶元素, 赋给赋给e GetTop(s, &e); 取栈顶元素取栈顶元素: 从从s中取得栈顶元素中取得栈顶元素, 赋给赋给e DispStack(s); 从栈顶到栈底顺序显示栈中所有元素。从栈顶到栈底顺序显示栈中所有元素。3.1.2 3.1.2 栈的顺序存储结构及其基本运算实现栈的顺序存储结构及其基本运算实现 假设栈的元素个数最大不超过正整数假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型所有的元素都具有同一数据类型ElemType, 则可则可用下列方式来定义栈类型用下列方式来定

7、义栈类型SqStack: typedef struct ElemType dataMaxSize； int top；/*栈顶位置栈顶位置*/ SqStack；例如：例如：S=(23,75,41,38,54,62,17)顺序栈内存示意图顺序栈内存示意图 ：SqStack S;栈顶元素：栈顶元素：S.data6 或写成或写成 S.data S.top 栈底元素：栈底元素：S.data0栈长：栈长： S.top+123 75 41 38 54 62 17data0top data99data66S顺序栈进栈和出栈示意图顺序栈进栈和出栈示意图在顺序栈中实现栈的基本运算算法在顺序栈中实现栈的基本运算算法

8、:(1)初始化栈初始化栈initStack(&s) 建立一个新的空栈建立一个新的空栈s,s,实际上是将栈顶指针指向实际上是将栈顶指针指向-1-1即可。对应算法如下即可。对应算法如下: : void InitStack(SqStack *&s) s=(SqStack*)malloc(sizeof(SqStack); /或或 s= new SqStack; s-top= -1; (2)销毁栈销毁栈ClearStack(&s) 释放栈释放栈s占用的存储空间。对应算法如下占用的存储空间。对应算法如下: void ClearStack(SqStack *&s) free(s); (3)求栈的长度求栈的长

9、度StackLength(s) 返回栈返回栈s中的元素个数中的元素个数,即栈指针加即栈指针加1的结果。对的结果。对应算法如下应算法如下: int StackLength(SqStack *s) return(s-top+1); (4)判断栈是否为空判断栈是否为空StackEmpty(s) 栈栈S为空的条件是为空的条件是s-top= -1。对应算法。对应算法如下如下: int StackEmpty(SqStack *s) return(s-top= -1); (5)进栈进栈Push(&s,e) 在栈不满的条件下在栈不满的条件下,先将栈指针增先将栈指针增1,然后在该位然后在该位置上插入元素置上插入

10、元素e。对应算法如下。对应算法如下: int Push(SqStack *&s, ElemType e) if (s-top=MaxSize-1) return 0;/*栈满的情况栈满的情况,即栈上溢出即栈上溢出*/s-top+; s-datas-top=e;return 1; (6)出栈出栈Pop(&s,&e) 在栈不为空的条件下在栈不为空的条件下,先将栈顶元素赋给先将栈顶元素赋给e,然后然后将栈指针减将栈指针减1。对应算法如下。对应算法如下: int Pop(SqStack *&s, ElemType &e) if (s-top= -1) return 0; /*栈为空的情况栈为空的情况,

11、即栈下溢出即栈下溢出*/e=s-datas-top;s-top-;return 1; (7)取栈顶元素取栈顶元素GetTop(s) 在栈不为空的条件下在栈不为空的条件下,将栈顶元素赋给将栈顶元素赋给e。对。对应算法如下应算法如下: int GetTop(SqStack *s , ElemType &e) if (s-top=-1) return 0; /*栈为空的情况栈为空的情况,即栈下溢出即栈下溢出*/e=s-datas-top;return 1; (8)显示栈中元素显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中所有元素。对应从栈顶到栈底顺序显示栈中所有元素。对应算法如下算法

12、如下: void DispStack(SqStack *s) int i;for (i=s-top; i=0; i-) coutdatai;coutnext=NULL; (2)销毁栈销毁栈ClearStack(&s) 释放栈释放栈s s占用的全部存储空间。对应算法如下占用的全部存储空间。对应算法如下: : void ClearStack(LiStack *&s) LiStack *p=s-next;while (p!=NULL)free(s);s=p;p=p-next; free(s); ( (3)求栈的长度求栈的长度StackLength(s) 从第一个数据结点开始扫描单链表从第一个数据结点

13、开始扫描单链表,用用i记录访问的记录访问的数据结点个数数据结点个数,最后返回最后返回i值。对应算法如下值。对应算法如下: int StackLength(LiStack *s) int i=0;LiStack *p;p=s-next;while (p!=NULL) i+;p=p-next; return(i); (4)判断栈是否为空判断栈是否为空StackEmpty(s) 栈栈S为空的条件是为空的条件是s-next=NULL,即单链即单链表中没有数据结点。对应算法如下表中没有数据结点。对应算法如下: int StackEmpty(LiStack *s) return(s-next=NULL);

14、 (5)进栈进栈Push(&s,e) 将新数据结点插入到头结点之后。对应算法如下将新数据结点插入到头结点之后。对应算法如下: void Push(LiStack *&s, ElemType e ) LiStack *p;p=new LiStack;p-data=e;p-next=s-next; /*插入插入*p结点作为第一个数据结点结点作为第一个数据结点*/s-next=p; (6)出栈出栈Pop(&s,&e) 在栈不为空的条件下在栈不为空的条件下,将头结点后继数据结点的数据将头结点后继数据结点的数据域赋给域赋给e,然后将其删除。对应算法如下然后将其删除。对应算法如下: int Pop(LiS

15、tack *&s, ElemType &e) LiStack *p;if (s-next=NULL) return 0; /*栈空的栈空的情况情况*/p=s-next;/*p指向第一个数据结点指向第一个数据结点*/e=p-data;s-next=p-next;free(p);return 1; (7)取栈顶元素取栈顶元素GetTop(s) 在栈不为空的条件下在栈不为空的条件下,将头结点后继数据结点的数据将头结点后继数据结点的数据域赋给域赋给e。对应算法如下。对应算法如下: int GetTop(LiStack *s, ElemType &e) if (s-next=NULL) return 0

16、; /*栈空的情况栈空的情况*/e=s-next-data;return 1; (8)显示栈中元素显示栈中元素DispStack(s) 从第一个数据结点开始扫描单链表从第一个数据结点开始扫描单链表,并输出当前访并输出当前访问结点的数据域值。对应算法如下问结点的数据域值。对应算法如下: void DispStack(LiStack *s) LiStack *p=s-next;while (p!=NULL)coutdata;p=p-next;printf(n); 例例3.5 编写算法判断输入的表达式中括号是否编写算法判断输入的表达式中括号是否配对（假设表达式中只含圆括号）。配对（假设表达式中只含圆

17、括号）。解解: 设置一个括号栈设置一个括号栈, 扫描表达式：遇到左括扫描表达式：遇到左括号时进栈号时进栈, 遇到右括号时遇到右括号时,若栈是相匹配的左括若栈是相匹配的左括号号, 则出栈则出栈, 否则否则, 返回返回0。 若表达式扫描结束若表达式扫描结束,栈为空栈为空,返回返回1表示括号表示括号正确匹配正确匹配,否则返回否则返回0。int Match( char exp , int n ) int i=0; char e; LiStack *st; InitStack(st); while ( in) if ( expi=( ) Push(st, expi ); else if ( expi=)

18、 ) if (!StackEmpty(st) ) Pop(st, e); else return 0; i+; if (Stackempty(st)=1) return 1; else return 0;例例(课本习题课本习题3) 假设表达式中允许包含三种括假设表达式中允许包含三种括号号:圆括号、方括号和大括号。编写一个算法判圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。断表达式中的括号是否正确配对。解解: 设置一个括号栈设置一个括号栈, 扫描表达式：遇到左括扫描表达式：遇到左括号号( 包括包括(、和和 )时进栈时进栈, 遇到右括号时遇到右括号时,若若栈是相匹配的左括号栈

19、是相匹配的左括号, 则出栈则出栈, 否则否则, 返回返回0。 若表达式扫描结束若表达式扫描结束,栈为空栈为空,返回返回1表示括号表示括号正确匹配正确匹配,否则返回否则返回0。 int correct(char exp , int n) char stMaxSize; int top=-1, i=0, tag=1; while (i-1) tag=0; /*若栈不空若栈不空,则不配对则不配对*/ return(tag); 3.1.4 3.1.4 栈的应用例子栈的应用例子1. 表达式求值表达式求值 这里限定的表达式求值问题是这里限定的表达式求值问题是:用户输入一个包用户输入一个包含含“+”、“-”

20、、“*”、“/”、正整数和圆括号的、正整数和圆括号的合法数学表达式合法数学表达式,计算该表达式的运算结果。计算该表达式的运算结果。 在程序语言中在程序语言中,运算符位于两个操作数中间的运算符位于两个操作数中间的表达式称为表达式称为中缀表达式中缀表达式。例如：。例如： 1+2*3 就是一个中缀表达式就是一个中缀表达式,中缀表达式是最常用的一中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循种表达式方式。对中缀表达式的运算一般遵循“先先乘除乘除, 后加减后加减, 从左到右计算从左到右计算, 先括号内先括号内, 后括号外后括号外”的规则。因此的规则。因此,中缀表达式不仅要依赖运算符优先级

21、中缀表达式不仅要依赖运算符优先级,而且还要处理括号。而且还要处理括号。 所谓所谓后缀表达式后缀表达式, 就是运算符在操作数的后面就是运算符在操作数的后面,如如1+2*3的后缀表达式为的后缀表达式为123*+。在后缀表达式中。在后缀表达式中已考虑了运算符的优先级已考虑了运算符的优先级, 没有括号没有括号,只有操作数和运只有操作数和运算符。算符。 中缀表达式中缀表达式 后缀表达式后缀表达式 a+b ab+ a*(b+c) abc+* (a+b)*(c-d) ab+cd-* a+b*(c/d-e) abcd/e-*+对后缀表达式求值过程是对后缀表达式求值过程是: 从左到右读入后缀表达式从左到右读入后

22、缀表达式, 若读入的是一个操作数若读入的是一个操作数, 就将它入数值栈就将它入数值栈, 若读入的若读入的是一个运算符是一个运算符op, 就从数值栈中连续出栈两个元素就从数值栈中连续出栈两个元素(两个操作数两个操作数), 假设为假设为x和和y, 计算计算x op y之值之值, 并将并将计算结果入数值栈；对整个后缀表达式读入结束时计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果。栈顶元素就是计算结果。计算计算 ab + cd - *a入栈：入栈： ab入栈：入栈： ab+: b,a出栈出栈 t1=ab+ 入栈：入栈： t1c,d 入栈：入栈： t1 c d- -: d,c出栈出栈

23、 t1 t2=cd - 入栈：入栈： t2 t1*: t1 t2 出栈：出栈：t3=t1 t2 * 入栈：入栈：t3计算计算 ab + cd - * 算术表达式求值过程是算术表达式求值过程是: 先将算术表达式转换成先将算术表达式转换成后缀表达式后缀表达式,然后对该后缀表达式求值。然后对该后缀表达式求值。 假设算术表达式中的符号以字符形式由键盘输假设算术表达式中的符号以字符形式由键盘输入入,并存放在字符型数组并存放在字符型数组exp中中,其后缀表达式存放在其后缀表达式存放在字符型数组字符型数组postexp中中,在将算术表达式转换成后缀在将算术表达式转换成后缀表达式的过程中用一个字符型数组表达式

24、的过程中用一个字符型数组op作为栈。将算作为栈。将算术表达式转换成后缀表示的方法如下术表达式转换成后缀表示的方法如下: 初始化运算符栈初始化运算符栈op;将将=入栈入栈op;从从exp读取一个字符到读取一个字符到ch；while (ch!=0) if (ch不是运算符）不是运算符） 将后续的所有数字均依次存放到将后续的所有数字均依次存放到postexp中中,并以字符并以字符# 标志数值串结束。标志数值串结束。 else switch ( Precede( op的栈顶元素的栈顶元素, ch ) ) case -1: / 此时的此时的op的栈顶元素优先级小于的栈顶元素优先级小于ch优先级优先级 将

25、将ch进栈进栈op; 从从exp读取下个字符到读取下个字符到ch; break; case 0: / 此时栈顶元素为此时栈顶元素为 (, ch为为 ) 退栈退栈op； 从从exp读取下个字符到读取下个字符到ch; break； case 1: / 此时栈顶元素优先级大于此时栈顶元素优先级大于ch的优先级的优先级 退栈退栈op； 退栈的运算符存到退栈的运算符存到postexp中；中； break； 运算符（运算符（+，-，*，/，（，），（，） ）优先级：）优先级：在表达式中的两个相邻的运算符进行优先级比较时，处于左边的运算符叫在表达式中的两个相邻的运算符进行优先级比较时，处于左边的运算符叫“左

26、运算左运算符符”，处于右边的运算符叫，处于右边的运算符叫“右运算符右运算符”。如：表达式：如：表达式：123+456*78 +是左运算符，是左运算符，*是右运算符是右运算符 此时，此时，+ +定义运算符的优先级：定义运算符的优先级：=（+-*/)左运算符左运算符0133556右运算符右运算符0622441 对于表达式对于表达式“(56-20)/(4+2)”,其转换成后其转换成后缀表达式的过程缀表达式的过程 如下：如下：exp操作过程操作过程op栈栈postexp初始化栈初始化栈op, 将将=入栈入栈op=(56-20)/(4+2)遇到遇到ch为为“(”, = ( , 将此括将此括号进栈号进栈o

27、p。=( 56-20)/(4+2)遇 到遇 到 c h 为 数 字为 数 字 , 将将 5 6 存 入存 入postexp中中,并插入一个字符并插入一个字符“#”。=(56#-20)/(4+2)遇到遇到ch为为“-”, ( ) , 则将栈则将栈op中中“-” 出栈并存入出栈并存入postexp中中.=(56#20# -)/(4+2)遇到遇到ch为为“)”, ( = ) , 则将栈则将栈op中中“(” 出栈出栈.=56#20# -/(4+2)遇到遇到ch为为“/”, = / , 将将ch进栈进栈op中。中。=/56#20# -(4+2)遇到遇到ch为为“(”, / ( , 将此括号将此括号进栈进

28、栈op中。中。=/(56#20# -4+2)遇到遇到ch为数字为数字,将将4#存入数组存入数组postexp中。中。=/(56#20#-4#exp操作过程操作过程oppostexp+2)遇到遇到ch为为“+”, ( ) , 将栈将栈op中中“+” 出栈并存放到出栈并存放到postexp中中.=/(56#20#-4#2#+)遇到遇到ch为为“)”, ( = ) , 将栈将栈op中中“(” 出栈出栈.=/56#20#-4#2#+ str扫描完毕扫描完毕,则将栈则将栈op中中=之前之前的所有运算符依次弹出并存放到的所有运算符依次弹出并存放到postexp中中,得到后缀表达式。得到后缀表达式。= 56

29、#20#-4#2#+/根据上述原理得到的根据上述原理得到的trans( )算法如下算法如下: struct char ch; int pri; lpri =, 0, (, 1, *, 5, /, 5, +, 3, -, 3, ), 6, rpri =, 0, (, 6, *, 4, /, 4, +, 2, -, 2, ), 1;int leftpri( char op) / 求左运算符求左运算符op的优先级的优先级 int i; for ( i=0; i7; i+) if (lprii.ch=op) return lprii.pri;int rightpri( char op) / 求右运算符

30、求右运算符op的优先级的优先级 int i; for ( i=0; i7; i+) if (rprii.ch=op) return rprii.pri;Int InOp(char ch) if (ch=( | ch=) | ch=+ | ch=- | ch=* | ch=/ ) return 1; else return 0;int Precede(char op1, char op2) / 比较比较op1和和op2优先级优先级 if (leftpri(op1)=rightpri(op2) return 0; / 左运算符左运算符op1与右运算符与右运算符op2优先级相同优先级相同 if (l

31、eftpri(op1)rightpri(op2) return -1; / 左运算符左运算符op1优先级优先级右运算符右运算符op2优先级优先级trans( )算法算法:将中缀表达式将中缀表达式exp转换为后缀表达式转换为后缀表达式postexp void trans(char *exp, char *postexp ) /*将算术表达式将算术表达式exp转换成后缀表达式转换成后缀表达式postexp*/ structchar dataMaxSize;/*存放运算符存放运算符*/int top;/*栈指针栈指针*/ op;/*定义运算符栈定义运算符栈*/int i=0;/* i作为作为post

32、exp的下标的下标*/op.top=-1; / 将将op栈置为空栈栈置为空栈op.top+; op.data op.top = =; / 将将=入栈入栈 while ( *exp !=0)/*exp表达式未扫描完时循环表达式未扫描完时循环*/ if ( ! InOp( *exp) ) / 如果字符如果字符*exp 是数字符时是数字符时 while (*exp=0 & *exp=0 & *postexp=9) d=10*d+*postexp-0; postexp+; st.top+; st.datast.top=d; postexp+; / 继续下个字符的处理继续下个字符的处理return st

33、.datast.top; 设计求解程序设计求解程序int main( ) char expMaxSize, postexpMaxSize; coutexp; trans(exp, postexp); cout“表达式的值：表达式的值：”comvalue(postexp)(xe,ye) int i, j, di, find, k; top+; /*初始方块进栈初始方块进栈*/ sttop.i=xi; sttop.j=yi; sttop.di=-1;mgxiyi=-1; while (top-1) /*栈不空时循环栈不空时循环*/ i=sttop.i; j=sttop.j; di=sttop.di

34、; if (i=xe & j=ye)/*找到了出口找到了出口,输出路径输出路径*/ printf(迷宫路径如下迷宫路径如下:n); for (k=0;k=top;k+) printf(t(%d,%d), stk.i, stk.j); if (k+1)%5=0) printf(n); printf(n); return 1; find=0; while (di4 & find=0) /*找下一个可走方块找下一个可走方块*/ di+; switch(di) case 0: i=sttop.i-1; j=sttop.j; break; case 1: i=sttop.i; j=sttop.j+1;

35、break; case 2: i=sttop.i+1; j=sttop.j; break; case 3: i=sttop.i, j=sttop.j-1; break; if (mgij=0) find=1; if (find=1) /*找到了下一个可走方块找到了下一个可走方块*/ sttop.di=di; /*修改原栈顶元素的修改原栈顶元素的di值值*/ top+; /*下一个可走方块进栈下一个可走方块进栈*/ sttop.i=i; sttop.j=j; sttop.di=-1; mgij=-1;/*避免重复走到该方块避免重复走到该方块*/ else /*没有路径可走没有路径可走,则退栈则退

36、栈*/ mgsttop.isttop.j=0; / 改为改为=-2更好更好 /*让该位置变为其他路径可走方块让该位置变为其他路径可走方块*/ top-; printf(没有可走路径没有可走路径!n); return 0; int main( ) mgpath(1, 1, 9, 9); return 0;3.2 3.2 队列队列 3.2.1 3.2.1 队列的定义队列的定义 返回返回 3.2.2 3.2.2 队列的顺序存储结构及队列的顺序存储结构及其基本运算的实现其基本运算的实现 3.2.3 3.2.3 队列的链式存储结构及队列的链式存储结构及其基本运算的实现其基本运算的实现3.2.4 3.2.

37、4 队列的应用例子队列的应用例子 队列简称队队列简称队,它也是一种运算受限的线性表它也是一种运算受限的线性表,其限其限制制仅允许在表的一端进行插入仅允许在表的一端进行插入,而在表的另一端进行而在表的另一端进行删除删除。 我们把进行插入的一端称做我们把进行插入的一端称做队尾队尾(rear),进行删进行删除的一端称做除的一端称做队首队首(front)。 向队列中插入新元素称为向队列中插入新元素称为进队或入队进队或入队,新元素进新元素进队后就成为新的队后就成为新的队尾元素队尾元素；从队列中删除元素称为；从队列中删除元素称为出出队或离队队或离队,元素出队后元素出队后,其后继元素就成为队首元素。其后继元

38、素就成为队首元素。 3.2.1 3.2.1 队列的定义队列的定义 队列的入队和出队操作示意图队列的入队和出队操作示意图ADT Queue 数据对象数据对象: D= a1, a2, a3, , an n0, 每个每个ai是是ElemType类型类型 数据关系数据关系: R=, , , 基本运算基本运算: InitQueue(&q); 初始化一个队列初始化一个队列: 构造一个空队列构造一个空队列q ClearQueue(&q); 销毁队列销毁队列: 释放队列占用的存储空间释放队列占用的存储空间 QueueEmpty(q); 判断队列判断队列q是否为空队列是否为空队列 enQueue(&q, e);

39、 入队列入队列: 将新元素将新元素e入队列入队列q deQueue(&q, &e); 出队列出队列: 出队列一个元素，赋给出队列一个元素，赋给e 3.2.2 3.2.2 队列的顺序存储结构及其基本运算的实现队列的顺序存储结构及其基本运算的实现 假 设 队 列 的 元 素 个 数 最 大 不 超 过 整 数假 设 队 列 的 元 素 个 数 最 大 不 超 过 整 数MaxSize,所有的元素都具有同一数据类型所有的元素都具有同一数据类型ElemType,则顺序队列类型则顺序队列类型SqQueue定义如下定义如下: typedef struct ElemType dataMaxSize； int

40、 front, rear；/*队首和队尾指示器队首和队尾指示器*/ SqQueue 从前图中看到从前图中看到,图图(a)为队列的初始状态为队列的初始状态,有有front=rear成立成立,该条件可以作为队列空的条件。该条件可以作为队列空的条件。 那么能不能用那么能不能用rear=MaxSize-1作为队满的作为队满的条件呢？显然不能条件呢？显然不能,在图在图(d)中中,队列为空队列为空,但仍满足该但仍满足该条件。这时入队时出现条件。这时入队时出现“上溢出上溢出”,这种溢出并不是真这种溢出并不是真正的溢出正的溢出,在在data数组中存在可以存放元素的空位置数组中存在可以存放元素的空位置,所以这是

41、一种假溢出。所以这是一种假溢出。 为了能够充分地使用数组中的存储空间为了能够充分地使用数组中的存储空间,把数组把数组的前端和后端连接起来的前端和后端连接起来,形成一个环形的顺序表形成一个环形的顺序表,即把即把存储队列元素的表从逻辑上看成一个环存储队列元素的表从逻辑上看成一个环,称为称为环形队列，环形队列，也称也称 循环队列循环队列。 循环队列首尾相连循环队列首尾相连,当队首当队首front指针满足指针满足 front=MaxSize-1后后,再前进一个位置就自动到再前进一个位置就自动到0,这可以利用除法取余的运算这可以利用除法取余的运算()来实现来实现: 队首指针进队首指针进1: front=

42、(front+1)MaxSize 队 尾 指 针 进队 尾 指 针 进 1: rear=(rear+1)MaxSize 循环队列的除头指针和队尾指针初始化时都置循环队列的除头指针和队尾指针初始化时都置0: front=rear=0。在入队元素和出队元素时。在入队元素和出队元素时,指指针都按逆时针方向进针都按逆时针方向进1。 怎样区分这两者之间的差别呢怎样区分这两者之间的差别呢? 在入队时少用一个在入队时少用一个数据元素空间数据元素空间,以队尾指针加以队尾指针加1等于队首指针判断队满等于队首指针判断队满,即队满条件为即队满条件为: (q-rear+1) % MaxSize=q-front队空条件

43、仍为队空条件仍为: q-rear=q-front rear rear 0 1 2 3 4 front (a)空队空队 (b)a,b,c 入队入队 rear 0 1 2 3 4 front a b c 0 1 2 3 4 a b c d front (c)d 入队入队,队满队满 rear 0 1 2 3 4 c d front (d)出队出队 2 次次 rear 0 1 2 3 4 front (e)出队出队 2 次次,队空队空 循环队的入队和出队操作示意图循环队的入队和出队操作示意图 在循环队列中在循环队列中,实现队列的基本运算算法如下实现队列的基本运算算法如下: (1)初始化队列初始化队列I

44、nitQueue(&q) 构造一个空队列构造一个空队列q。将。将front和和rear指针均设置指针均设置成初始状态即成初始状态即0值。对应算法如下值。对应算法如下: void InitQueue(SqQueue *&q) q=(SqQueue *)malloc (sizeof(SqQueue); / 或或 new SqQueue;q-front=q-rear=0; (2)销毁队列销毁队列ClearQueue(&q) 释放队列释放队列q占用的存储空间。对应算法如下占用的存储空间。对应算法如下: void ClearQueue(SqQueue *&q) free(q); q=NULL; (3)判

45、断队列是否为空判断队列是否为空QueueEmpty(q) 若队列若队列q满足满足q-front=q-rear条件条件,则则返回返回1；否则返回；否则返回0。对应算法如下。对应算法如下: int QueueEmpty(SqQueue *q) return(q-front=q-rear); (4)入队列入队列enQueue(q,e) 在队列不满的条件下在队列不满的条件下,先将队尾指针先将队尾指针rear循环增循环增1,然后将元素添加到该位置。对应算法如下然后将元素添加到该位置。对应算法如下: int enQueue(SqQueue *&q, ElemType e) if (q-rear+1)%Ma

46、xSize=q-front) /*队满队满*/return 0;q-rear=(q-rear+1)%MaxSize;q-dataq-rear=e;return 1 1; (5)出队列出队列deQueue(q,e) 在队列在队列q不为空的条件下不为空的条件下,将队首指针将队首指针front循环增循环增1,并将该位置的元素值赋给并将该位置的元素值赋给e。对应算法如下。对应算法如下: int deQueue( SqQueue *&q, ElemType &e) if (q-front=q-rear) /*队空队空*/return 0;q-front=(q-front+1)%MaxSize;e=q-d

47、ataq-front;return 1; 例例 对于顺序队列来说对于顺序队列来说,如果知道如果知道队首元素的位队首元素的位置和队列中元素个数置和队列中元素个数,则队尾元素所在位置显然是可则队尾元素所在位置显然是可以计算的。也就是说以计算的。也就是说,可以用队列中元素个数代替队可以用队列中元素个数代替队尾指针。编写出这种循环顺序队列的初始化、入队、尾指针。编写出这种循环顺序队列的初始化、入队、出队和判空算法。出队和判空算法。 解解: 当已知队首元素的位置当已知队首元素的位置front和队列中元素个和队列中元素个数数count后后:队空的条件为队空的条件为: count=0队满的条件为队满的条件为

48、: count=MaxSize计算队尾位置计算队尾位置rear: rear=(front+count+MaxSize)%MaxSize 队列类型定义如下队列类型定义如下: typedef struct ElemType dataMaxSize;int front; /*队首指针，指着队首元素的前个位置队首指针，指着队首元素的前个位置*/int count; /*队列中元素个数队列中元素个数*/ QuType; /*队列类型队列类型*/ void InitQu(QuType *&q) /*队列队列q初始化初始化*/ q=(QuType *)malloc(sizeof(QuType);q-fron

49、t=0;q-count=0; int EnQu(QuType *&q, ElemType x) /*进队进队*/ int rear;if (q-count=MaxSize) return 0; /*队满上溢出队满上溢出*/else rear=(q-front+q-count+MaxSize)%MaxSize; /*求队尾位置求队尾位置*/ rear=(rear+1)%MaxSize; /*队尾位置进队尾位置进1*/ q-datarear=x; q-count+; return 1; int DeQu(QuType *&q,ElemType &x)/*出队出队*/if (q-count=0)/*

50、队空下溢出队空下溢出*/ return 0;else q-front=(q-front+1)%MaxSize; x=q-dataq-front; q-count-; return 1;int QuEmpty(QuType *q)/*判空判空*/ return(q-count=0); 链队组成链队组成: (1) 存储队列元素的单链表存储队列元素的单链表 (2) 指向队头和队尾指针的链队头结点指向队头和队尾指针的链队头结点 3.2.3 3.2.3 队列的链式存储结构及其基本运算的实现队列的链式存储结构及其基本运算的实现 front rear q (a)(a)链队初态链队初态 front rear

51、q (b)(b)入队入队 3 3 个元素个元素 a b c front rear q (c)(c)出队出队 1 1 个元素个元素 b c 链列的入队和出队操作示意图链列的入队和出队操作示意图数据结点类型数据结点类型QNode定义如下定义如下: struct qnode ElemType data;/*数据元素数据元素*/struct qnode *next; QNode;链队中头结点类型链队中头结点类型LiQueue定义如下定义如下:typedef struct QNode *front;/*指向单链表队头结点指向单链表队头结点*/ QNode *rear; /*指向单链表队尾结点指向单链表队

52、尾结点*/ LiQueue; 在链队存储中在链队存储中,队列的基本运算算法如下队列的基本运算算法如下: (1)初始化队列初始化队列InitQueue(q) 构造一个空队列构造一个空队列,即只创建一个链队头结点即只创建一个链队头结点,其其front和和rear域均置为域均置为NULL,不创建数据元素结不创建数据元素结点。对应算法如下点。对应算法如下: void InitQueue(LiQueue *&q) q=(LiQueue *)malloc(sizeof(LiQueue); q-front=q-rear=NULL; (2)销毁队列销毁队列ClearQueue(q) 释放队列占用的存储空间释放

53、队列占用的存储空间,包括链队头结点和所包括链队头结点和所有数据结点的存储空间。对应算法如下有数据结点的存储空间。对应算法如下: void ClearQueue(LiQueue *&q) QNode *p=q-front, *r;if (p!=NULL)/*释放数据结点占用空间释放数据结点占用空间*/ r=p-next; while (r!=NULL) free(p); p=r; r=p-next; /*p和和r指针同步后移指针同步后移*/ free(p);free(q);/*释放链队结点占用空间释放链队结点占用空间*/ (3)判断队列是否为空判断队列是否为空QueueEmpty(q) 若链队结

54、点的若链队结点的rear域值为域值为NULL,表示队列为表示队列为空空,返回返回1；否则返回；否则返回0。对应算法如下。对应算法如下: int QueueEmpty(LiQueue *q) if (q-rear=NULL) return 1;else return 0; (4)入队列入队列enQueue(q,e) 创建创建data域为域为e的数据结点的数据结点*s。若原队列。若原队列为空为空,则将链队结点的两个域均指向则将链队结点的两个域均指向*s结点结点,否则否则,将将*s链到单链表的末尾链到单链表的末尾,并让链队结点的并让链队结点的rear域域指向它。对应算法如下指向它。对应算法如下: v

55、oid enQueue(LiQueue *&q, ElemType e) QNode *s; s=(QNode *)malloc(sizeof(QNode);s-data=e;s-next=NULL; if (q-rear=NULL) /*若原链队为空若原链队为空,新结点是队首结点又是队尾结点新结点是队首结点又是队尾结点*/ q-front=q-rear=s;else q-rear-next=s; /*将将*s结点链到队尾结点链到队尾,rear指向它指向它*/ q-rear=s; (5)出队列出队列deQueue(q,e) 若原队列不为空若原队列不为空,则将第一个数据结点的则将第一个数据结点的

56、data域值赋给域值赋给e,并删除之。若出队之前队列中只并删除之。若出队之前队列中只有一个结点有一个结点,则需将链队结点的两个域均置为则需将链队结点的两个域均置为NULL,表示队列已为空。对应的算法如下表示队列已为空。对应的算法如下: int deQueue(LiQueue *&q,ElemType &e) QNode *t;if (q-rear=NULL) return 0; /*队列为空队列为空*/t=q-front;/*t指向第一个数据结点指向第一个数据结点*/if (q-front=q-rear) /*原链队中只有一个结点时原链队中只有一个结点时*/ q-front=q-rear=NU

57、LL;else/*原链队中有多个结点时原链队中有多个结点时*/ q-front=q-front-next;e=t-data; free(t);return 1; 3.2.4 3.2.4 队列的应用例子队列的应用例子1. 求解报数问题求解报数问题 设有设有n个人站成一排，从左到右的编号为个人站成一排，从左到右的编号为1至至n，现从左到右报数现从左到右报数“1，2，1，2，”，数到，数到1的人出的人出列，数到列，数到2的人立即排到队伍的最右端。报数过程反的人立即排到队伍的最右端。报数过程反复进行，直到复进行，直到n个人都出列为止。求他们的出列顺序。个人都出列为止。求他们的出列顺序。如：如：n=8时

58、，初始序列：时，初始序列：1 2 3 4 5 6 7 8 出列顺序：出列顺序：1 3 5 7 2 6 4 8先将先将n个人的编号入队列，然后逐个人报数出队列，个人的编号入队列，然后逐个人报数出队列，报数报数1的人输出编号，报数的人输出编号，报数2的人重新入队列。的人重新入队列。void number(int n)void number(int n) int i; int i; SqQueue q; SqQueue q; q.front=q.rear=0; / q.front=q.rear=0; / 初始化顺序队列初始化顺序队列q q for (i=1; i=n; i+) / n for (i=1; i=n; i+) / n个人入队列个人入队列 q.rear=(q.rear+1) % MaxSize; q.rear=(q.rear+1) % MaxSize; q.dataq.rear=i; q.dataq.rea