DS03-栈和队列

1、 第三章第三章 栈和队列栈和队列定义：定义：限定只能在表的限定只能在表的进行插进行插入和删除运算的线性表。入和删除运算的线性表。在在栈中栈中 通常将表中允许进行插入、删除操作的通常将表中允许进行插入、删除操作的一端称为一端称为栈顶栈顶(Top)，同时表的另一端被称为，同时表的另一端被称为栈底栈底(Bottom)。栈顶的当前位置是动态变化。栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指的，它由一个称为栈顶指针的位置指示器指示。当栈中没有元素时称为示。当栈中没有元素时称为空栈空栈。栈的插入栈的插入操作被形象地称为操作被形象地称为进栈进栈或入栈，删除操作称或入栈，删除操作称为出栈或为

2、出栈或退栈退栈。栈的示意图栈的示意图与线性表相同，仍为一对一与线性表相同，仍为一对一( 1:1)( 1:1)关系。关系。用用或或存储均可，但以顺序栈更常见存储均可，但以顺序栈更常见只能在只能在运算，且访问结点时依照运算，且访问结点时依照（LIFOLIFO）或）或（FILOFILO）的原则。）的原则。关键是编写关键是编写和和函数，具体实现依顺函数，具体实现依顺序栈或链栈的存储结构有别而不同。序栈或链栈的存储结构有别而不同。 存储结构存储结构 运算规则运算规则 实现方式实现方式 逻辑结构逻辑结构基本操作基本操作 建栈、判断栈满或栈空、入栈、出栈、建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等

3、。读栈顶元素值，等等。 表尾表尾(a(an n端端) )称为栈顶称为栈顶 /top; /top; 表表头头(a(a1 1端端) )称为栈底称为栈底/base/base例如：例如： 栈栈 = (a1 , a2 , a3 , .,an-1 , an )插入元素到栈顶的操作，称为插入元素到栈顶的操作，称为入入。从栈顶删除最后一个元素的操作，称为从栈顶删除最后一个元素的操作，称为出栈出栈。a an n称为栈称为栈顶元素顶元素a a1 1称为栈称为栈底元素底元素插入和删除都插入和删除都只能在表的一只能在表的一端（栈顶）进端（栈顶）进行！行！栈的物理表示法栈的物理表示法一、顺序栈的存储结构和操作的实现一、

4、顺序栈的存储结构和操作的实现 顺序栈顺序栈: :是利用一组地址连续的存储单元依次存放从栈底到是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。栈顶的数据元素。 a1 a2 an顺序栈顺序栈S ai0n栈底栈底栈顶栈顶压入压入( (SS+=a=a弹出弹出( ( - 栈的基本操作栈的基本操作 InitStackInitStack( )( )： 初始化，构造一个空栈初始化，构造一个空栈S S ClearStack(SClearStack(S) )：栈栈S S已经存在，清除栈已经存在，清除栈S S中的所有元素中的所有元素将将S S置成空栈置成空栈。 StackEmpty(SStackEmpt

5、y(S) )：判断栈判断栈S S是否为空，若为空，则返回是否为空，若为空，则返回 truetrue；否则返回；否则返回falsefalse GetTop(S)GetTop(S) ： 返回返回S S的栈顶元素，但不移动栈顶指针的栈顶元素，但不移动栈顶指针 也不改变栈顶元素的值也不改变栈顶元素的值 Push(S, x)Push(S, x) ：在在S的顶部插入的顶部插入(亦称压入亦称压入)元素元素x；若；若S栈未栈未满，将满，将x插入栈顶位置，若栈已满，则返回插入栈顶位置，若栈已满，则返回FALSE，表示，表示操作失败，否则返回操作失败，否则返回TRUE。 （入栈操作（入栈操作) ) Pop(S)P

6、op(S) ： 删除删除S S的栈顶元素并返回其值（出栈操作）的栈顶元素并返回其值（出栈操作）顺序栈存储结构的描述：顺序栈存储结构的描述：/*设顺序栈的最大长度为100*/structstruct datatypedatatype stackMaxsizestackMaxsize; intint top top； / /* *栈顶指针栈顶指针* */ /SeqStackSeqStack； / /* *顺序栈类型定义顺序栈类型定义* */ /SeqStack SeqStack * *s s； / /* *s s为顺序栈类型变量的指针为顺序栈类型变量的指针* */ /顺序栈的几种状态以及在这些状态

7、下栈顶指针顺序栈的几种状态以及在这些状态下栈顶指针toptop和栈和栈中结点的关系中结点的关系 栈为空的条件栈为空的条件 ： top = 0top = 0栈满的条件栈满的条件 ： top = top = MaxsizeMaxsize另一种顺另一种顺序栈的几种状态以及在这些状态下栈顶指针序栈的几种状态以及在这些状态下栈顶指针toptop和栈中结点的关系和栈中结点的关系 栈为空的条件栈为空的条件 ： top = -1top = -1栈满的条件栈满的条件 ： top = Maxsize-1top = Maxsize-1若入栈动作使地址向高端增长，称为若入栈动作使地址向高端增长，称为“向上生成向上生成

8、”的栈；的栈；若入栈动作使地址向低端增长，称为若入栈动作使地址向低端增长，称为“向下生成向下生成”的栈的栈； 对于向上生成的堆栈对于向上生成的堆栈: :栈指针指向待压入位置栈指针指向待压入位置入栈入栈：栈指针：栈指针top “top “先压后加先压后加” ” : S: Stop+top+=13;=13;出栈出栈：栈指针：栈指针top “top “先减后弹先减后弹” ” : e=S: e=S-top-top 顺序栈的基本操作顺序栈的基本操作Stop+=13;入栈入栈出栈出栈e=S-top若入栈动作使地址向高端增长，称为若入栈动作使地址向高端增长，称为“向上生成向上生成”的栈；的栈；若入栈动作使地

9、址向低端增长，称为若入栈动作使地址向低端增长，称为“向下生成向下生成”的栈的栈； 对于对于向下生向下生成的堆栈成的堆栈: :栈指针指向待压入位置栈指针指向待压入位置入栈入栈：栈指针：栈指针top “top “先压先压后减后减” : : SStoptop-=a=ai i出栈出栈：栈指针：栈指针top “top “先加后先加后弹弹” ” : e=: e=SS+top+top 顺序栈的基本操作顺序栈的基本操作构造一个空顺序栈构造一个空顺序栈 SeqStack * InitStack( ) SeqStack *S ;S=(SeqStack *)malloc(sizeof(SeqStack); if(!

10、S) /*空间申请失败空间申请失败*/ printf(“空间不足空间不足”)；return NULL; else S-top=0; return S; if(S=0)取顺序栈栈顶元素取顺序栈栈顶元素 datatype GetTop(SeqStack *S) if (S-top=0) printf(n栈是空的栈是空的!); return FALSE; else return S-stackS-top-1; 该函数返回一个该函数返回一个datatype类型的值类型的值判别空栈判别空栈int StackEmpty(SeqStack *S) if(S-top=0) return TRUE; else

11、return FALSE; 顺序栈的入栈顺序栈的入栈操作操作顺序栈入栈函数顺序栈入栈函数PUSHPUSH（）（）SeqStack*Push(SeqStack*S，datatype x) if(S-top=Maxsize) return NULL;else S-stackS-top=x; S-top+; return s; SeqStack*Push(SeqStack*S，datatype x) if(S-top=Maxsize) return NULL; S-stackS-top=x;S-top+;return s; 顺序栈的入栈操作顺序栈的入栈操作例如用堆栈存放（例如用堆栈存放（A A，B

12、B，C C，D D）AACBABAtop核心语句：核心语句：push (s,B);push (s,C);push (s,D);toptoptoptop低地址低地址Lpush (s,A);高地址高地址MBCD顺序栈入栈函数顺序栈入栈函数PUSHPUSH（）（）SeqStack*Push(SeqStack*S，datatype x) if(S-top=Maxsize) return NULL; S-stackS-top=x;S-top+;return s; 顺序栈出栈操作顺序栈出栈操作例如从栈中取出例如从栈中取出 DCBAtoptopDCABDCBAtopDCBAtop低地址低地址L高地址高地址M

13、D核心语句：核心语句：pop (ps);顺序栈出栈函顺序栈出栈函数数pop( )pop( )datatype pop( SeqStack *S) if(S-top=0) printf(nThe sequence stack is empty!); return FALSE; S-top-; return S-stackS-top; pop (ps);printf( pop (ps) );例例3.2.13.2.1利用顺序栈的运算，编写将任意一个十进制整数转利用顺序栈的运算，编写将任意一个十进制整数转换成二至九之间的任一进制数并输出换成二至九之间的任一进制数并输出 #include stdio.h

14、#include conio.h#define MAXSIZE 20#define TRUE 1#define FALSE 0typedef int datatype;typedef struct datatype arrayMAXSIZE; int top;SeqStack;SeqStack *InitSeqStack()SeqStack *p;p=(SeqStack *)malloc(sizeof(SeqStack);if(p=NULL)printf(顺序栈初始化失败);return FALSE;p-top=0;return p;datatepy push(SeqStack *h,int

15、item)if(h-top=MAXSIZE)return NULL;h-arrayh-top=item;h-top+;datatype pop(SeqStack *h) if(h-top=0) printf(nThe sequence stack is empty!); return FALSE; h-top-; return(h-arrayh-top);datetype StackEmpty(SeqStack *h)if(h-top=NULL)return TRUE;return FALSE;void conversion(int N, int r) int x=N,y=r; SeqStac

16、k *s; /*顺序栈*/ s=InitSeqStack( ); /*构造一个顺序栈*/ while(N!=0) push(s, N%r ); /*将N%r入栈*/ N=N/r ; printf(n十进制数%d所对应的%d进制数是:,x,y); while(!StackEmpty(s) /*栈非空时,出栈*/ printf(%d,pop(s); printf(n); main() int num,r; printf(输入被转化的十进制数num的值); scanf(%d,&num); printf(输入被转化成的进制r的值：); scanf(%d,&r); conversion(

17、num, r); getch();练习题：用练习题：用mainmain函数以及函数以及displaydisplay函数，调试上述各种栈的函数，调试上述各种栈的基本操作算法。基本操作算法。 #define Maxsize 50 typedef int datatype; typedef struct datatype stackMaxsize; int top； SeqStack；void display(SeqStack *s) /*显示栈中所有元素值显示栈中所有元素值*/ int t; t=s-top; if(s-top =0) /*栈为空栈为空*/ printf(the stack is

18、empty!n); else while(t!=0) t-; printf(%d-,s-stackt); main()int a6=3,7,4,12,31,15,i; SeqStack *p; p= InitStack(); for(i=0;itop=0; S-top=0; /*清空栈清空栈*/ else else /*c1是普通字符是普通字符*/ push(s,c1); /*入栈入栈*/ Scanf(“%c”,&c1); Scanf(“%c”,&c1); display(s); /*输出栈输出栈s的所有元素值的所有元素值*/ 链链 栈栈二、链栈的存储结构及操作的实现二、链栈的

19、存储结构及操作的实现 栈也可以用链式结构来表示，用链式结构栈也可以用链式结构来表示，用链式结构来表示的栈就是来表示的栈就是链栈链栈链栈的构造方式链栈的构造方式以头指针为栈顶，以头指针为栈顶，在头指针处在头指针处插入或删除插入或删除. .栈顶栈顶栈底栈底 a1 a2an-1 annextdata链栈中每个结点由两个域构成：链栈中每个结点由两个域构成：datadata域和域和nextnext域，其定义为：域，其定义为：Typedef struct node datatype data; struct node * next; LinkStack; LinkStack *top; 将将x x入栈，修

20、入栈，修改栈顶指针改栈顶指针: : p-next=top; p-next=top; top=p;top=p;链栈的入栈操作链栈的入栈操作LinkStack *Push(LinkStack *top，datatype x) LinkStack *p; p=(Linkstack*)malloc(sizeof(LinkStack); p-data=x; p-next=top; top=p; return top; 链栈入栈操作链栈入栈操作栈顶指针指向新申请结点的地址修改栈顶指针链栈的出栈操作链栈的出栈操作a an n出栈，使工作指针出栈，使工作指针q q指向要出栈结点，然指向要出栈结点，然后修改栈顶

21、指针后修改栈顶指针: :top=top-nexttop=top-next LinkStack *pop( LinkStack *top) LinkStack *q; if(!top) /*说明指针top指向NULL*/ printf(“n链栈是空的!”); return NULL; q=top; top=top-next; free(q); return top; 链栈出栈操作链栈出栈操作1、数制转换（十转数制转换（十转N N） 设计思路：用栈暂存低位值设计思路：用栈暂存低位值2、括号匹配问题括号匹配问题 设计思路：用栈暂存左括号设计思路：用栈暂存左括号3、子程序的调用子程序的调用 设计思路：

22、用栈暂存指令地址设计思路：用栈暂存指令地址4、逆置一个单链表逆置一个单链表 设计思路：用栈暂存每一结点设计思路：用栈暂存每一结点例例3.2 3.2 将十进制整数转换成二至九之间的任一将十进制整数转换成二至九之间的任一进制数输出进制数输出 将一个十进制数将一个十进制数43274327转换成八进制数转换成八进制数(10347)(10347)8 8：N是十进制数，要将是十进制数，要将N转换成转换成r进制数进制数1、当当N0N0，将，将N%rN%r压压入栈入栈s s中，即余数进栈；中，即余数进栈； 2、用用N/rN/r代替代替N N；3 3、若、若N N0 0，则重复上，则重复上两步；若两步；若N=0

23、N=0，则将栈，则将栈s s的内容依次出栈，所的内容依次出栈，所得的结果即为所求。得的结果即为所求。解题思路如下：解题思路如下：void conversion(int N, int r) int x=N,y=r;SeqStack *s; /*是顺序栈是顺序栈*/ s=initStack( ); /*构造一个顺序栈构造一个顺序栈*/ while(N!=0) push(s, N %r ); /*将将N%r入栈入栈*/ N=N/r ; printf(“n十进制数十进制数%d所对应的所对应的%d进制数进制数是是:”，x,y);while(!StackEmpty(s) /*栈非空时，出栈栈非空时，出栈*

24、/ printf(“%d”,pop(s); printf(“n”); 例例3.5 3.5 利用一个顺序栈将单链表（利用一个顺序栈将单链表（a a1 1, ,a a2 2, , ,a an n）（其）（其中中n=0n=0）逆置为（）逆置为（a an n, ,a an-1n-1, ,，a a1 1）1 1、建立一个、建立一个带头结点的带头结点的单链表单链表headhead；2 2、输出该单链表；、输出该单链表；3 3、建立一个空栈、建立一个空栈s s（顺序栈）（顺序栈）；4 4、依次将单链表的数据入栈；、依次将单链表的数据入栈；5 5、依次将单链表的数据出栈，、依次将单链表的数据出栈，并逐个将出栈

25、的数据存入单链并逐个将出栈的数据存入单链表的数据域（自前向后）表的数据域（自前向后）; ;6 6、再输出单链表。、再输出单链表。 解题思路如下：解题思路如下：linklist*backlinklist(linklist *head) /*利用顺序栈逆置单链表利用顺序栈逆置单链表head */linklist *p; /*工作指针工作指针*/ p=head-next; /*p指向单链表的第一个结点指向单链表的第一个结点*/ initstack( ); / /* *初始化一个顺序栈初始化一个顺序栈s,ss,s是结构体类型是结构体类型* */ / while(p) push(&s, p-da

26、ta); p=p-next ; p=head-next; while(!stackempty(s) /*将顺序表的数据出栈将顺序表的数据出栈*/ /*将出栈后的数据存入单链表将出栈后的数据存入单链表headhead中中*/ p-data=pop(&s); p=p-next; return (head); 两个栈的共享技术两个栈的共享技术： 它主要利用了栈它主要利用了栈“栈底位置不变，而栈底位置不变，而栈顶位置动态变化栈顶位置动态变化”的特性。首先为两个栈申请一个共享的的特性。首先为两个栈申请一个共享的一维数组空间一维数组空间SM，将两个栈的栈底分别放在一维数组，将两个栈的栈底分别放在一

27、维数组的两端，分别是的两端，分别是0， M-1。 由于两个栈顶动态变化，这样可由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享比两个栈分别申有关。由此可见，两栈共享比两个栈分别申请请M/2的空间利的空间利用率高。用率高。 两栈共享的数据结构定义如下：两栈共享的数据结构定义如下： define M 100typedef struct StackElementType StackM; int top2; /*top0和top1分别为两个栈顶指示器*/DqStack; 十月一前讲到此十月一前讲

28、到此（图） 共享栈 Stack:0M1top0top1(1) 初始化操作。初始化操作。 void InitStack(DqStack *S) S-top0= -1; S-top1= M; int Push(DqStack *S, StackElementType x, int i)/*把数据元素把数据元素x压入压入i号堆栈号堆栈*/ if(S-top0+1=S-top1) /*栈已满栈已满*/ return(FALSE); switch(i) case 0: S-top0+; S-StackS-top0=x; break; case 1: S-top1-; /*先移指针，后入栈先移指针，后入栈

29、*/ S-StackS-top1=x; break; default: /*参数错误参数错误*/ return(FALSE) return(TRUE); int pop(DqStack *S, StackElementType *x, int i)/* 从从i 号堆栈中弹出栈顶元素并送到号堆栈中弹出栈顶元素并送到x中中 */ switch(i) /* 先出栈，后移栈顶指针先出栈，后移栈顶指针 */ case 0: if(S-top0= = -1) return(FALSE); *x=S-StackS-top0; S-top0-; break; case 1: if(S-top1= =M) re

30、turn(FALSE); *x=S-StackS-top1; S-top1+; break; default: return(FALSE); return(TRUE); (3) 共共享享栈栈的的出出栈栈操操作作算算法。法。 队列队列 (Queue)是另一种限定性的是另一种限定性的线性表线性表，它只允许在表的一端插入元素，而在另一端它只允许在表的一端插入元素，而在另一端删除元素删除元素，所以队列具有先进先出先进先出(Fist In Fist Out， 缩写为FIFO)的特性。队列的定义队列的定义 在队列中，允许插入的一端叫做在队列中，允许插入的一端叫做队尾队尾(rear)，允许删除的一端则称为允

31、许删除的一端则称为队头队头(front)。 假设队列假设队列为为q=(a1，a2，an)，那么，那么a1就是队头元素，就是队头元素，an则是队尾元素。队列中的元素是按照则是队尾元素。队列中的元素是按照a1，a2，an的顺序进入的，的顺序进入的， 退出队列也必须按照同样的退出队列也必须按照同样的次序依次出队，也就是说，只有在次序依次出队，也就是说，只有在a1，a2，an-1都离开队列之后，都离开队列之后，an才能退出队列。才能退出队列。问：为什么要设计队列？它有什么独特用途？问：为什么要设计队列？它有什么独特用途？答：答： 1.1.离散事件的模拟（模拟事件发生的离散事件的模拟（模拟事件发生的先后

32、顺序先后顺序, ,例如例如 CPUCPU芯片中的指令译码队芯片中的指令译码队列）；列）； 2.2.操作系统中的作业调度（一个操作系统中的作业调度（一个CPUCPU执行多个作业）；执行多个作业）； 3.简化程序设计。简化程序设计。 与线性表相同，仍为一对一关系。与线性表相同，仍为一对一关系。顺序队顺序队或或链队链队，以，以循环顺序队循环顺序队更常见。更常见。只能在队首和队尾运算，且访问结点时依照只能在队首和队尾运算，且访问结点时依照先进先出（FIFOFIFO）的原则。的原则。关键是掌握关键是掌握入队入队和和出队出队操作，具体实现依顺操作，具体实现依顺序队或链队的不同而不同。序队或链队的不同而不同

33、。入队或出队，建空队列，判队空或队满等操作。入队或出队，建空队列，判队空或队满等操作。关键是掌握关键是掌握入队入队和和出队出队操作。操作。具体实现依具体实现依存储结构存储结构（链队链队或或顺序队顺序队）的不同而不同。）的不同而不同。（1 1）InitQueue ( )InitQueue ( )： 构造一个空队列构造一个空队列Q Q（2 2）QueueEmpty (Q)QueueEmpty (Q)： 判断队列是否为空判断队列是否为空 （3 3）QueueLength (Q)QueueLength (Q)： 求队列的长度求队列的长度 （4 4）GetHead (Q)GetHead (Q)： 返回返

34、回Q Q的队头元素，不改变队列状态的队头元素，不改变队列状态 （5 5）EnQueue(QEnQueue(Q， x )x )： 插入元素插入元素x x为为Q Q的新的队尾元素的新的队尾元素 （6 6）DeQueue(Q)DeQueue(Q)： 删除删除Q Q的队头元素的队头元素（7 7）ClearQueue(Q)ClearQueue(Q)：清除队列：清除队列Q Q中的所有元素中的所有元素 队列队列（QueueQueue）的逻辑表示的逻辑表示 假设队列为Q=(a1，a2，an)，那么a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，an的顺序进入的， 退出队列也必须按照同样的次序

35、依次出队，也就是说，只有在a1，a2，an-1都离开队列之后，an才能退出队列。例如：队列例如：队列 Q= (a1 , a2 , a3 , .,an-1 , an )队首队首队尾队尾链队列类型定义：链队列类型定义： typedef struct Qnode *front ; /*队头指针*/ Qnode *rear ; /*队尾指针*/ LinkQueue; 结点类型定义：结点类型定义： typedef Struct Qnode datatype data; /*数据域*/ Struct Qnode *next; /*指针域*/ Qnode; 队列队列（QueueQueue）的物理表示的物理表

36、示链队的几种状态示意图：链队的几种状态示意图： 空链队的特征？空链队的特征？front=rearfront=rear 链队会满吗？链队会满吗？一般不会，因为删除时有一般不会，因为删除时有freefree动作。除非内存不足！动作。除非内存不足！(b)元素x入队(d)元素x出队此时，front= =rear修改rear指针修改头结点的指针域入队（尾部插入）：入队（尾部插入）：rear-next=S; rear=S;rear-next=S; rear=S;出队（头部删除）：出队（头部删除）：front-next=S-next;front-next=S-next; 怎样实现链队的怎样实现链队的入队和出

37、队入队和出队操作？操作？ 若设若设S S所指结点为入队或出队结点所指结点为入队或出队结点LinkQueue *InitQueue( ) LinkQueue *q; Qnode *p; q=(LinkQueue*)malloc(sizeof(LinkQueue); p=(Qnode*)malloc(sizeof(Qnode); p-next=NULL; q-front =q-rear=p; return q;该函数返回一个指向队头的指针该函数返回一个指向队头的指针datatype GetHead(LinkQueue *Q) if(Q-front= =Q-rear) printf(“n链队列为空!

38、”); return FALSE; return Q-front-next-data； void EnQueue(LinkQueue *Q，datatype x) Qnode *p; p = (Qnode*)malloc(sizeof(Qnode)； p-data = y； p-next = NULL； Q-rear-next = p； Q-rear=p； datatype DeQueue(LinkQueue *Q) Qnode *p; datatype x; if (Q-front = = Q-rear) printf(队列为空！队列为空！); return FALSE; p = Q-fro

39、nt-next； x = p-data； Q-front-next = p-next； if(Q-rear = p) /*此时此时p出队出队,则队列为空则队列为空*/ Q-rear=Q-front； free(p)； return x; 2、顺序队列、顺序队列 顺序队列类型定义：顺序队列类型定义：#define MAXSIZE 100 / /* *最大队列长度最大队列长度* */ /typedef structtypedef structdatatype dataMAXSIZE； / /* * 存储队列的数据空间存储队列的数据空间* */ /int front； / /* *队头指针队头指针*

40、 */ /int rear； /*队尾指针队尾指针*/SeqQueue; 约定：约定：队头指针队头指针frontfront，若队列不空，则指向队头元素，若队列不空，则指向队头元素。 队尾指针队尾指针rearrear，若队列不空，则指向队尾元素的，若队列不空，则指向队尾元素的 下一个位置下一个位置。顺序队的几种状态示意图顺序队的几种状态示意图头指针始终指向队头元素，尾指针始终指向队尾元素的下一个元素头指针始终指向队头元素，尾指针始终指向队尾元素的下一个元素为了防止出现假溢出，即在假溢出时，还能进行入队操作，我们采为了防止出现假溢出，即在假溢出时，还能进行入队操作，我们采取循环队列。取循环队列。循

41、环队列示意图循环队列示意图在入队时：在入队时： 将数据区将数据区data0Maxsize-1看成是首尾相接的圆环看成是首尾相接的圆环,当当入队到入队到Maxsize-1时时,若队头元素的前面仍有空闲位置若队头元素的前面仍有空闲位置,下一个下一个地址就应翻转为地址就应翻转为0,使使data0接在接在dataMaxsize-1之后之后, 通过通过求余运算求余运算rear=(rear+1)%Maxsize来求得。来求得。在出队时：在出队时：队头指针也要采用front=(front+1)%Maxaize循环队列的几种状态循环队列的几种状态在循环队列中当采用在循环队列中当采用入队操作入队操作: : re

42、ar=(rear+1)%Maxsize出队操作出队操作: : front=(front+1)%Maxaize就会出现新问题：就会出现新问题：空队和队满时都有空队和队满时都有front=rear； 那么又如何判断队空和队满？那么又如何判断队空和队满？队空条件队空条件 : : front = = rearfront = = rear ( (初始化时：初始化时：front=rear)front=rear)队满条件队满条件： front=front=（rearrear)%N)%N (N=maxsize) (N=maxsize)J2 J3J1 J4 J5frontrear 解决方案解决方案-人为人为浪费

43、一个单元浪费一个单元： 即对大小为即对大小为MaxsizeMaxsize的数组，只允许存的数组，只允许存Maxsize-1Maxsize-1个结点个结点。为此我们约定：为此我们约定：front和和rear二者之一指向实元素，另一个指向二者之一指向实元素，另一个指向空闲元素空闲元素(假设假设front指向队头元素，指向队头元素，rear指向队尾元素的下一个指向队尾元素的下一个位置，位置，即即rear 所指的单元始终为空所指的单元始终为空）。）。 队列长度（即数据元素个数）：队列长度（即数据元素个数）：L=L=（N Nrearrearfrontfront）% N % N 循环队列的基本操作实现循环

44、队列的基本操作实现1 1）初始化一个空队列）初始化一个空队列算法要求：生成一空队列算法要求：生成一空队列算法操作：为队列分配基本容量空间算法操作：为队列分配基本容量空间 设置队列为设置队列为空队列空队列，其特征即：，其特征即： front=rear=0front=rear=0（frontfront和和rearrear也可为任意单元编号，如也可为任意单元编号，如1 1，2 2，甚至甚至-1-1）以建队、入队和出队三种基本操作为例以建队、入队和出队三种基本操作为例建循环队的完整算法建循环队的完整算法SeqQueue *initQueue( ) SeqQueue *q； q=(SeqQueue*)m

45、alloc(sizeof(SeqQueue)； /*开辟一个足够大的存储队列的空间*/ q-front = q-rear = 0；/*将队列头尾指针置为零*/ return q； /*返回队列的首地址*/ 顺序存储算法说明：向循环队列的队尾插入一个元素算法说明：向循环队列的队尾插入一个元素分析分析：(1) (1) 插入前应当先判断队列是否满？插入前应当先判断队列是否满？ if ( q -rear + 1 ) % Maxsize )=q-front)if ( q -rear + 1 ) % Maxsize )=q-front) return false; return false;(2(2）插入

46、元素值并修改尾指针）插入元素值并修改尾指针 q-data q-rear = x; q-data q-rear = x; q-rear = ( q -rear + 1 ) % Maxsize; q-rear = ( q -rear + 1 ) % Maxsize;循环队列入队操作循环队列入队操作队列尺寸队列尺寸int EnQueue(SeqQueue *q, datatype x)if(q-rear+1)MAXSIZE=q-front) printf(n循环队列满循环队列满!);return FALSE; q-dataq-rear = x； /*元素元素x入队入队*/ q-rear = (q-r

47、ear+1)%MAXSIZE; /*修改尾指针修改尾指针*/ return TRUE;循环队列入队操作循环队列入队操作循环队列的出队操作循环队列的出队操作算法说明：算法说明：删除队头元素删除队头元素, ,返回其值返回其值 x x并修改队头指针并修改队头指针 分分 析：析： （1 1） 在删除前应当判断队列是否空？在删除前应当判断队列是否空？ if (q-front = q-rear ) return false;if (q-front = q-rear ) return false; （2 2）删除动作分析；）删除动作分析； 前面约定指针前面约定指针frontfront指向队首元素的位置，故：

48、指向队首元素的位置，故： x= q-data q-front ; x= q-data q-front ; q-front = ( q-front + 1 ) % Maxsize; q-front = ( q-front + 1 ) % Maxsize; frontfront指针在元素出队后再加指针在元素出队后再加datatype DeQueue(SeqQueue *q) datatype x;if (q-front = = q-rear) printf(“n循环队列空！循环队列空！”); return FALSE; x = q-data q-front ；/ /* *出队出队* */ /q-f

49、ront = (q-front+1)MAXSIZE；/ /* *修改队头指针修改队头指针* */ / return x；循环队列出队操作循环队列出队操作3.4 队列的应用队列的应用2 2、迷宫问题：寻找一条从迷宫入口到出口、迷宫问题：寻找一条从迷宫入口到出口的最短路径的最短路径 3 3、键盘输入循环缓冲区问题键盘输入循环缓冲区问题 例例3.7 打印杨辉三角形。打印杨辉三角形。 此问题是一个初等数学问题。系数表中的第此问题是一个初等数学问题。系数表中的第i i行有行有i+1i+1个个数，除了第数，除了第1 1个和最后一个数为个和最后一个数为1 1外，其余的数则为上一行中外，其余的数则为上一行中位

50、于其左、右的两数之和。位于其左、右的两数之和。（a+b）n的系数的系数 如果要计算并输出二项系数表（即杨辉三角形）的如果要计算并输出二项系数表（即杨辉三角形）的前前n n行的值，则所设循环队列的最大空间应为行的值，则所设循环队列的最大空间应为n+2n+2。假。假设队列中已存有第设队列中已存有第i i行的值，为计算方便，在行的值，为计算方便，在两行之间两行之间均加一个均加一个“0”0”作为行间的分隔符，则在计算第作为行间的分隔符，则在计算第i+1i+1行行之前，头指针正指向第之前，头指针正指向第i i行的行的“0”0”，而尾元素为第，而尾元素为第i+1i+1行的行的“0”0”。由此，从左至右输出

51、第。由此，从左至右输出第i i行的值，并将计行的值，并将计算所得的第算所得的第i+1i+1行的值插入队列。行的值插入队列。如第四行为： 0 1 4 6 4 1 第五行为： 0 1 5 10 10 5 1 分析第分析第 i i 行元素与第行元素与第 i+1i+1行元素的关系如图所示行元素的关系如图所示 ：在在i=2时时,队列的头指针指向队列的头指针指向0，尾指针指向，尾指针指向1的下一位，我们看如何的下一位，我们看如何 由由第二行得到第三行的。第三行的第二行得到第三行的。第三行的0入队入队队头元素队头元素0出队并送入出队并送入s中中取队头元素取队头元素1并送入并送入t中中s+t的值的值1入队。入

52、队。这时队列的队头指针指向这时队列的队头指针指向1，队尾指针指向第三行的第一个，队尾指针指向第三行的第一个3的位置。重复三步就得到第的位置。重复三步就得到第三行；类推，我们由第三行又得到第四行；三行；类推，我们由第三行又得到第四行；frontrear从第从第 2行数据计算并存放第行数据计算并存放第 3 行数据行数据0在运算的任一时刻在运算的任一时刻,要产要产生下一个入队的元素生下一个入队的元素,均均是队头方向的两元素相是队头方向的两元素相加后入队加后入队.杨辉三角形元素入队顺序16152015611510105114641133112111116152015611510105114641133

53、1121111000000 假设假设n=4n=4，i=3i=3，则输出第，则输出第3 3行元素并求解第行元素并求解第4 4行行元素值的循环执行过程中队列的变化状态如图所元素值的循环执行过程中队列的变化状态如图所示示 ：完整算法请看教材完整算法请看教材void YangHui( int n )/*打印杨辉三角形的前打印杨辉三角形的前n行行*/ SeqQueue *q; int i, j,s,t; for(i=1;i=n;i+) printf( ); printf(1n); /*在中心位置输出杨辉三角最顶端的在中心位置输出杨辉三角最顶端的1*/ q=InitQueue(); /*设置容量为设置容量

54、为n+2的空队列的空队列*/ EnQueue(q,0); /*添加行分隔符，添加行分隔符，即即0入队入队*/ EnQueue(q,1);EnQueue(q,1); /*第一行的值入队第一行的值入队*/、出队并保存出队元素、出队并保存出队元素、取出、取出front所指元素并保存所指元素并保存、计算前两步得到的元素值之、计算前两步得到的元素值之和和并入队并入队重复这三步。（当由第重复这三步。（当由第i行求得第行求得第i+1行时，先入队行时，先入队）上图的操作过程是：for(j=1;jn;j+) /*利用循环队列输出前利用循环队列输出前n-1行的值行的值*/for(i=1;in-j;i+) /*在输

55、出第在输出第j行的首元素之间输出行的首元素之间输出n-j个空格个空格*/ printf( ); EnQueue(q,0); /*行分隔符行分隔符0入队入队*/ do /*输出第输出第j行并计算第行并计算第j+1行行*/ s=DeQueue(q); /*删除队头元素并赋给删除队头元素并赋给s*/ t=GetHead(q); /*取队头元素给取队头元素给t*/ if(t) printf(%5 d,t); /*若不到行分隔符若不到行分隔符0，则输出，则输出t，再输出一个空格，再输出一个空格*/ else printf(n); /*否则输出一个换行符否则输出一个换行符*/ EnQueue(q,s+t)

56、; /*将第将第j+1行的对应元素行的对应元素s+t入队入队*/ while(t!=0); DeQueue(q); /* 删除行分隔符删除行分隔符 */ printf(%3d,DeQueue(q); /* 输出第输出第n行的第一个元素行的第一个元素 */ while(!QueueEmpty(q) /* 输出第输出第n行的其余元素行的其余元素 */ t=DeQueue(q); printf(“%5 d,t); 队列不空，则出队队列不空，则出队输出杨辉三角形的最后一行（）第输出杨辉三角形的最后一行（）第n n行行2 2、迷宫问题、迷宫问题： 寻找一条从迷宫入口到出口的最短路径寻找一条从迷宫入口到出

57、口的最短路径 迷宫问题是实验心理学的一个经典问题，心理学家把迷宫问题是实验心理学的一个经典问题，心理学家把一只老鼠从一个无顶盖的迷宫入口处赶进迷宫，在迷宫的一只老鼠从一个无顶盖的迷宫入口处赶进迷宫，在迷宫的出口处设置了一块奶酪，吸引老鼠在迷宫中寻找通路以到出口处设置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到学入口到出口，而不走错一步。老鼠经多次实验终于得到学习走通迷宫的路线。习走通迷宫的路线。 算法分析算法分析 如果用计算机来处理：求出一条从入口到出

58、口的通路，或者得出如果用计算机来处理：求出一条从入口到出口的通路，或者得出没有通路的结论。通常采用一种称为没有通路的结论。通常采用一种称为回溯法回溯法的方法，即不断试探且及的方法，即不断试探且及时纠正错误的搜索方法，这需要借助时纠正错误的搜索方法，这需要借助“栈栈”来实现。此法在许多书中来实现。此法在许多书中都有介绍，在此不再赘述。都有介绍，在此不再赘述。 如果在一般走迷宫的方法上，更进一步要求不论试探方位为何，如果在一般走迷宫的方法上，更进一步要求不论试探方位为何，找出一条最短路径，那该如何解决呢？其算法的基本思想是：从迷宫找出一条最短路径，那该如何解决呢？其算法的基本思想是：从迷宫的入口的

59、入口1111出发，向四周搜索，记下所有一步能到达的坐标点；然出发，向四周搜索，记下所有一步能到达的坐标点；然后依次从每一点出发，向四周搜索，记下所有从入口点出发，经过两后依次从每一点出发，向四周搜索，记下所有从入口点出发，经过两步可以到达的坐标点步可以到达的坐标点依次进行下去，一直到达迷宫的出口处依次进行下去，一直到达迷宫的出口处mnmn。然后从出口处沿搜索路径回溯直到入口点，这样就找到了从入口到出然后从出口处沿搜索路径回溯直到入口点，这样就找到了从入口到出口的一条最短路径。口的一条最短路径。 0 1 1 1 0 1 1 11 0 1 0 1 0 1 00 1 0 0 1 1 1 10 1 1

60、 1 0 1 1 11 0 0 1 1 0 0 10 1 1 0 0 1 1 0入口出口迷宫1 1 1 1 1 1 1 1 1 11 0 1 1 1 0 1 1 1 11 1 0 1 0 1 0 1 0 11 0 1 0 0 1 1 1 1 11 0 1 1 1 0 1 1 1 11 1 0 0 1 1 0 0 1 11 0 1 1 0 0 1 1 0 11 1 1 1 1 1 1 1 1 1加哨兵后的迷宫 我们可以使用如下的数据结构：我们可以使用如下的数据结构：maze1.m,1.n表示表示迷宫，为了算法方便，在四周加上迷宫，为了算法方便，在四周加上“哨兵哨兵1”即变即变为数组为数组maze1.m+1,1.n+1，如右图所示。用结构数