数据结构队列.ppt

《数据结构队列.ppt》由会员分享，可在线阅读，更多相关《数据结构队列.ppt（40页珍藏版）》请在优知文库上搜索。

1、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.4 队列的应用例子队列的应用例子 队列简称队队列简称队,它也是一种运算受限的线性表它也是一种运算受限的线性表,其限其限制仅允许在表的一端进行插入制仅允许在表的一端进行插入,而在表的另一端进行而在表的另一端进行删除。删除。 我们把进行插入的一端称做我们把进行插入的一端称做队尾队尾(rear),进行删除进行

2、删除的一端称做的一端称做队首队首(front)。 向队列中插入新元素称为向队列中插入新元素称为进队进队或或入队入队,新元素进队新元素进队后就成为新的队尾元素；从队列中删除元素称为后就成为新的队尾元素；从队列中删除元素称为出队出队或或离队离队,元素出队后元素出队后,其后继元素就成为队首元素。其后继元素就成为队首元素。 3.2.1 3.2.1 队列的定义队列的定义 队列的入队和出队操作示意图队列的入队和出队操作示意图 3.2.2 3.2.2 队列的顺序存储结构及其基本运算的实现队列的顺序存储结构及其基本运算的实现 假设队列的元素个数最大不超过整数假设队列的元素个数最大不超过整数MaxSize,所有

3、的元素都具有同一数据类型所有的元素都具有同一数据类型ElemType,则顺序则顺序队列类型队列类型SqQueue定义如下定义如下: typedef struct ElemType dataMaxSize； int front,rear；/*队首和队尾指针队首和队尾指针*/ SqQueue 从 前 图 中 看 到从 前 图 中 看 到 , 图图 ( a ) 为 队 列 的 初 始 状 态为 队 列 的 初 始 状 态 , 有有front=rear成立成立,该条件可以作为队列空的条件。该条件可以作为队列空的条件。 那么能不能用那么能不能用rear=MaxSize-1作为队满的条件呢？作为队满的条件

4、呢？显然不能显然不能,在图在图(d)中中,队列为空队列为空,但仍满足该条件。这时但仍满足该条件。这时入队时出现入队时出现“上溢出上溢出”,这种溢出并不是真正的溢出这种溢出并不是真正的溢出,在在elem数组中存在可以存放元素的空位置数组中存在可以存放元素的空位置,所以这是一种所以这是一种假溢出。假溢出。 为了能够充分地使用数组中的存储空间为了能够充分地使用数组中的存储空间,把数组的把数组的前端和后端连接起来前端和后端连接起来,形成一个环形的顺序表形成一个环形的顺序表,即把存储即把存储队列元素的表从逻辑上看成一个环队列元素的表从逻辑上看成一个环,称为循环队列。称为循环队列。 循环队列首尾相连循环队

5、列首尾相连,当队首当队首front指针满足指针满足 front=MaxSize-1后后,再前进一个位置就自动到再前进一个位置就自动到0,这可这可以利用除法取余的运算以利用除法取余的运算()来实现来实现: 队首指针进队首指针进1:front=(front+1)MaxSize 队尾指针进队尾指针进1:rear=(rear+1)MaxSize 循环队列的除头指针和队尾指针初始化时都置循环队列的除头指针和队尾指针初始化时都置0:front=rear=0。在入队元素和出队元素时。在入队元素和出队元素时,指针都按指针都按逆时针方向进逆时针方向进1。 怎样区分这两者之间的差别呢怎样区分这两者之间的差别呢?在

6、入队时少用一个在入队时少用一个数据元素空间数据元素空间,以队尾指针加以队尾指针加1等于队首指针判断队满等于队首指针判断队满,即队满条件为即队满条件为: (q-rear+1) % MaxSize=q-front队空条件仍为队空条件仍为: 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

7、front (e)出队出队 2 次次,队空队空 循环队的入队和出队操作示意图循环队的入队和出队操作示意图 在循环队列中在循环队列中,实现队列的基本运算算法如下实现队列的基本运算算法如下: (1) 初始化队列初始化队列InitQueue(&q) 构造一个空队列构造一个空队列q。将。将front和和rear指针均设置成初指针均设置成初始状态即始状态即0值。对应算法如下值。对应算法如下: void InitQueue(SqQueue *&q) q=(SqQueue *)malloc (sizeof(SqQueue);q-front=q-rear=0; (2) 销毁队列销毁队列ClearQueue(&

8、q) 释放队列释放队列q占用的存储空间。对应算法如下占用的存储空间。对应算法如下: void ClearQueue(SqQueue *&q) free(q); (3) 判断队列是否为空判断队列是否为空QueueEmpty(q) 若队列若队列q满足满足q-front=q-rear条件条件,则返回则返回1；否则返回否则返回0。对应算法如下。对应算法如下: int QueueEmpty(SqQueue *q) return(q-front=q-rear); (4) 入队列入队列enQueue(q,e) 在队列不满的条件下在队列不满的条件下,先将队尾指针先将队尾指针rear循环增循环增1,然后将元素添

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

10、emType &e) if (q-front=q-rear) /*队空队空*/return 0;q-front=(q-front+1)%MaxSize;e=q-dataq-front;return 1; 例例3.6 什么是队列的上溢现象和假溢出现象？解决什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？它们有哪些方法？ 答答: 在队列的顺序存储结构中在队列的顺序存储结构中,设头指针为设头指针为front,队队尾指针尾指针rear,队的容量队的容量(存储空间的大小存储空间的大小)为为MaxSize。当有元素加入到队列时当有元素加入到队列时,若若 rear=MaxSize(初始时初始时rear

11、=0)则发生队列的上溢现象则发生队列的上溢现象,该元素不能加入队列。该元素不能加入队列。 特别要注意的是队列的假溢出现象特别要注意的是队列的假溢出现象:队列中还有剩队列中还有剩余空间但元素却不能进入队列余空间但元素却不能进入队列,造成这种现象的原因造成这种现象的原因是由于队列的操作方法所致。是由于队列的操作方法所致。 解决队列上溢的方法有以下几种解决队列上溢的方法有以下几种: (1) 建立一个足够大的存储空间建立一个足够大的存储空间,但这样做会造成空但这样做会造成空间的使用效率降低。间的使用效率降低。 (2) 当出现假溢出时可采用以下几种方法当出现假溢出时可采用以下几种方法: 采用平移元素的方

12、法采用平移元素的方法:每当队列中加入一个元素时每当队列中加入一个元素时,队列中已有的元素向队头移动一个位置队列中已有的元素向队头移动一个位置(当然要有空闲当然要有空闲的空间可供移动的空间可供移动)； 每当删除一个队头元素时每当删除一个队头元素时,则依次移动队中的则依次移动队中的元素元素,始终使始终使front指针指向队列中的第一个位置；指针指向队列中的第一个位置； 采用循环队列方式采用循环队列方式:把队列看成一个首尾相接把队列看成一个首尾相接的循环队列的循环队列,在循环队列上进行插入或删除运算时仍在循环队列上进行插入或删除运算时仍然遵循然遵循“先进先出先进先出”的原则的原则。 例例3.7 对于

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

14、ear: rear=(front+count)%MaxSize 对应的算法如下对应的算法如下: typedef struct ElemType dataMaxSize;int front;/*队首指针队首指针*/int count;/*队列中元素个数队列中元素个数*/ QuType;/*队列类型队列类型*/ void InitQu(QuType *&q) /*队列队列q初始化初始化*/ q=(QuType *)malloc(sizeof(QuType);q-front=0;q-count=0; int EnQu(QuType *&q,ElemType x)/*进队进队*/ int rear;i

15、f (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)/*队空下溢出队空下溢出*/ return 0;else q-front=(q-front+1)%MaxSize; x=q-dataq-f

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