栈和队列(续)

1、第三章 栈和队列（续）1.队列的概念队列是限定只能在一端进队,在另一端出队的特殊线性表.从这个定义中应当理解到以下几点:队列属于加了限制条件的线性结构队列是先进先出的线性表进队只能从称为队尾（rear）的一端进行,出队只能从队的另一端,称为队头(front)的端点进行.不能从队列的中间进入或删除元素.队列中的元素个数可以为0,此时是空队列.队列中的元素的个数是可以变化的,可以是多个,但不能是无穷多个.同一个队列中的所有元素的类型相同.队列的存储方式有顺序存储方式(顺序队列)和链式存储方式(链式队列).在顺序队列中,使用一个数组存放队列的元素,并用一个队列指针(front)指向队头元素,一个队列

2、指针(rear)指向队尾元素;在链式队列中,用一个单链表存储队列的的元素,链表的第一个节点定义为队头节点,链表的最后一个节点定义为队尾节点.顺序队列又分为循环队列和非循环队列,循环队列解决了假溢出的问题.本章只介绍顺序循环队列上的算法实现.2.顺序队顺序队列的节点的类型定义如下:#define maxlen 20typedef char elemtype;typedef struct sqqueueelemtype datamaxlen;int front,rear; squeue,*sq;p64类型定义：#define maxqsize 100typedef struct qelemtype

3、 *base; int front; int rear;sqqueue;解决了假溢出的问题,需要将数组想象为首尾相接的圆环.称这种数组为“循环数组”，存储在其中的队列称为“循环队列”。解决队空、队满的判断问题，可以有3种方法：（1）设置一个布尔变量以区别队空还是队满。（2）使用计数器记录元素个数，即队列长度。（3）浪费一个元素的空间，以区别队空还是队满。在使用中，通常采用最后一种方法。通常约定队首指针指示队首元素，队尾指针指示队尾元素的下一个位置，因此在循环队列中:初始时:sq->front=sq->rear=0入队：队未满时，sq->datasq->rear=x;sq

4、->rear=(sq->rear+1)%maxlen出队：对非空时，sq->front=(sq->front+1)%maxlen队空条件:sq->rear=sq->front队满条件:(sq->rear+1)%maxlen=sq->front队列长度：(sq->rear+maxlen-sq->front)%maxlen顺序队列操作演示（1） 设队列的大小为7，开始为空队列，front=-1,rear=-1;队空条件：front=rear（2） 插入数据A,front=-1,rear=0;（3） 插入数据B,C, front=-1,re

5、ar=2;（4） 删除A, front=0,rear=2;（5） 删除B, front=1,rear=2;（6） 插入D,E,F,G, front=1,rear=6;（7） 插入H. front=1,rear=7;溢出，假溢出。将数据往前挪，（front=-1,rear=5）（8） 插入G. front=-1,rear=6.队满条件：rear-front=maxlen例62循环队列操作演示1说明循环队列的工作过程，包括初始化、进队、出队操作和队空、队满条件。（10'）（南师题）答：p64(1)循环队列-队列的顺序存储结构#define MAXQSIZE 100typedef struc

6、t QElemType *base; int front; int rear;SqQueue;(2)/-循环队列的基本操作的算法描述-/说明：书上算法中队列的front指示头元素的位置，rear指示队尾元素的下一个位置。初始化建空队列时Q.front=Q.rear=0（图1）,一个元素入队rear指针后移一个位置（图2，图3），一个元素出队front指针后移一个位置（图4）。图1 图2图3 图4 /Status InitQueue (SqQueue &Q)/构造一个空队列 Q.base=(ElemType *)malloc(MAXQSIZE*sizeof(ElemType); /C+:

7、 new ElemTypeMAXQSIZE; if (!Q.base)exit (OVERFLOW); Q.front=Q.rear=0; return OK;/Status EnQueue (SqQueue &Q,QElemType e)/插入元素e为Q 的新的队尾元素 if (Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/队列满 Q.baseQ.rear=e; Q.rear=(Q.rear+1) %MAXQSIZE; return OK;/Status EnQueue (SqQueue &Q,QElemType &e)/ if (

8、Q.rear =Q.front)return ERROR;/队列空 e = Q.baseQ. front ; Q. front =(Q. front +1) %MAXQSIZE; return OK;(3)队空条件Q.rear =Q.front、队满条件(Q.rear+1)%MAXQSIZE=Q.front例63链表式循环队列例题解析4以数组Q0.m存放循环队列中的元素，变量rear和qulen分别指示循环队列中的队尾元素的实际位置和当前队列中元素的个数，则队列第一个元素的实际位置是_。（rear-qulen+m+1）mod(m+1)（南师题） 4以数组Q0.m存放循环队列中的元素，变量rea

9、r和front分别指示循环队列中的队尾元素的实际位置和第一个元素的前一个位置，则当前队列中元素的个数是_。（rear-front+m+1）mod(m+1)（南师题） 5判断循环队列是否“满”，有那两种方法？请写出判断表达式。解：p63方法一：另设一个标志位以区别队列是“空”还是“满”；方法二：少用一个元素的空间，约定以“队列头指针在队列尾指针的下一个位置（环状的下一个位置）上”作为对列呈“满”状态的标志。队满判断表达式:(Q.rear+1)mod n =Q.front请同学根据以下循环队列的一系列的变化判断队满的条件： 此时队满的条件是？ 此时队满的条件又是？队空的条件呢？队列的运算void

10、initqueue(squeue &sq)/初始化队列sq. sq=(squeue *)malloc(sizeof(squeue); sq->rear=sq->front=0;int enqueue(squeue *sq,elemtype x)/在队列sq中入队一个元素x. if(sq->rear+1)%maxlen=sq->front) return 0; sq->datasq->rear=x; sq->rear=(sq->rear+1)%maxlen; return 1;int Outqueue(squeue *sq,elemtype

11、 &x)/在队列sq中出队一个元素,并将其值赋给x. if(sq->rear=sq->front) return 0; x=sq->datasq->front;sq->front=(sq->front+1)%maxlen;return 1;int Gethead(squeue *sq,elemtype &x)/将队列sq的队头元素赋给x,但不移动队头指针. if(sq->rear=sq->front) return 0; x=sq->datasq->front; return 1;int Emptyq(squeue *

12、sq)/判断队列sq是否为空队.若为空,返回1;否则返回0. if(sq->rear=sq->front) return 1; else return 0;3.链队类型定义如下：typedef struct qnode elemtype data; struct qnode *next;qtype;typedef struct qtype *front,*rear;lqueue;lqueue *lq;队首指针lq->front, 队尾指针lq->rear, 队首元素的引用为lq->front->data, 队尾元素的引用为lq->rear->data.p61类型定义typedef struct qnode elemtype data; struct qnode *next;qnode, *queueptr;typedef struct queuep