数据结构第3章b-12级

1、第3章 栈与队列 第三章第三章 栈与队列栈与队列 3.1 栈栈 3.2 栈的应用举例栈的应用举例 3.3 队列队列 3.4 队列的应用举例队列的应用举例 第3章 栈与队列 队列的定义及基本运算队列的定义及基本运算 1、定义、定义队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表 （1）允许删除的一端称为队头（队头（Front）。（2）允许插入的一端称为队尾（队尾（Rear）。（3）当队列中没有元素时称为空队列空队列。（4）队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表表。第3章 栈与队列 2、队列的基本逻辑运算、队列的基本逻辑运算 （

2、1）SETNULL(Q);置空队。构造一个空队列Q。（2）EMPTY(Q);判队空。若队列Q为空，则返回真值，否则返回假（3）FRONT(Q);若队列Q非空，则返回队头元素队头元素，但不改变队列Q的状态。（4）EnQueue（Q，x）若队列Q非满，则将元素x插入插入Q的队尾的队尾。此操作简称入队入队（5）DEQUEUE(Q);若队列Q非空，则删去删去Q的队头队头元素，并返回该元素。此操作简称出队出队。第3章 栈与队列 顺序队列顺序队列 1 1、顺序队列、顺序队列 （1）顺序队列的定义 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。（2） 顺序队列的表示和顺序表一样，顺序队列

3、用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，设置两个变量front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为-1。第3章 栈与队列 顺序队列的类型定义顺序队列的类型定义 typedef struct datatype datamaxsize; int front,rear; sequeue; sequeue *sq; sq-rear 尾指针尾指针 sq-front 头指针头指针 入队操作入队操作 sq-rear+; sq-datasq-rear=x;出队操作出队操作 sq-front+; sq-rearsq-front

4、012第3章 栈与队列 当前队列中元素个数（队列长度）是当前队列中元素个数（队列长度）是 （sq-rear） (sq-front) 队空队空的条件是的条件是 （sq- front ）=(sq- rear) 队满队满的条件是队列长度等于向量空间的大小的条件是队列长度等于向量空间的大小 （sq-rear）(sq-front)=maxsize第3章 栈与队列 第3章 栈与队列 (3)顺序队列中的溢出现象 “下溢下溢”现象现象当队列为空队列为空时，做出队做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。 “真上溢真上溢”现象现象当队列满队列满时，做入队入队运算产生空间溢出的现象。

5、“真上溢”是一种出错状态，应设法避免。 假上溢假上溢现象现象由于入队和出队操作中，头尾指针只增加不减小头尾指针只增加不减小，致使被删被删元素的空间永远无法重新利用元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。第3章 栈与队列 2、循环队列、循环队列为充分利用向量空间，克服假上溢现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列循环队列（CircularQueue）。第3章 栈与队列 （1）循环队列的基本操作循环队列中进行出队、入队操作时，

6、头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（指向向量上界（Maxsize-1）时）时，其加加1操作的结果是指向向量的下界操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： 入队入队时的队尾指针加1操作修改为： sq-rear=(sq-rear+1) % MAXSIZE; 出队出队时的队头指针加1操作修改为： sq-front=(sq-front+1) % MAXSIZE;第3章 栈与队列 front=4rear=8front=4rear=4front=8rear=8front=4rear=3(a)有4个元素(b)队满(c)队空(d)队满第3章 栈与队列 方法之一是

7、附设一个存储队中元素个数的变量如num，当num=0时队空，当num=MAXSIZE时为队满。 另一种方法是少用一个元素空间，把图（d）所示的情况就视为队满，此时的状态是队尾指针加队尾指针加1就会从后面赶上队头指针就会从后面赶上队头指针，这种情况下队满队满的条件是： (sq-rear+1) % MAXSIZE= sq- front Length=(m+ (sq- rear)(sq- front)%m第3章 栈与队列 （4）循环队列的基本运算 置队空置队空void SETNULL(sequeue *sq)sq-front=maxsize-1;sq-rear=maxsize-1;/*0的前一位置就

8、是的前一位置就是maxsize-1*/ 或者：或者： sq-front=sq-rear=1; 判队空判队空 int EMPTY(sequeue *sq)if(sq-rear= =sq-front)return 1;else return 0;第3章 栈与队列 取队头元素取队头元素datatypeFRONT(sequeue*sq)if(EMPTY(sq)printf(queueisempty);return0;elsereturnsq-data(sq-front+1)%maxsize;第3章 栈与队列 入队入队int ENQUEUE(sequeue *sq,datatype x) if(sq-f

9、ront=(sq-rear+1)%maxsize) printf(queue is full);return 0; else sq-rear=(sq-rear+1)%maxsize; sq-datasq-rear=x; return 1; 第3章 栈与队列 出队出队datatype DEQUEUE(sequeue *sq) if(EMPTY(sq) printf(queue is empty);return 0; else sq-front=(sq-front+1)%maxsize; return sq-datasq-front; 第3章 栈与队列 单链表结构回忆单链表结构回忆 线性表的单链存

10、储结构线性表的单链存储结构 typedef int datatype； typedef struct Node datatype data; struct Node*next; linklist; linklist*head,*p,*L;第3章 栈与队列 链队列链队列 1 1、 链队列的定义链队列的定义 队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作。2 2、 链队列的结构类型说明链队列的结构类型说明typedefstructlinklist*front,*rear;linkqueue;linkqueue*q;

11、 第3章 栈与队列 (a)非空队rearfronta1ana2qrearfrontqa1rearfrontq(b)空队(c)链队中只有一个元素结点图6头尾指针封装在一起的链队列第3章 栈与队列 3、 链队列的基本运算链队列的基本运算（1）置空队SETNULL(linkqueue*q)q-front=(linklist*)malloc(sizeof(linklist);q-front-next=null;q-rear=q-front;（2）判队空intEMPTY(linkqueue*q)if(q-rear=q-front)return1;elsereturn0;rearfrontq(b)空队re

12、arfrontqa1(c)链队中只有一个元素结点第3章 栈与队列 （3）取队头结点）取队头结点 datatype *FRONT(linkqueue *q)if(EMPTY(q)printf(quere is empty);return null;else return q-front-next-data;rearfrontqa1第3章 栈与队列 （4） 入队入队ENQUEUE(linkqueue *q,datatype x)q-rear-next=(linklist *)malloc(sizeof(linklist);q-rear=q-rear-next;q-rear-data=x;q-rea

13、r-next=null; rearfrontqa1x第3章 栈与队列 （5）出队(当长度大于1时)s=q-front-next;q-front-next=s-next;队长度大于1rearfronta1ana2qs第3章 栈与队列 注意：和链栈类似，无须考虑判队满的运算及上溢。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。rearfrontqa1第3章 栈与队列 改进的出队运算改进的出队运算/*将头结点删除，原队头结点变成头结点*/s=q-front;q-front=q-front-next;free(s);return(q-front-data);rearfronta1ana2qsrearfrontqa1s第3章 栈与队列 课堂练习课堂练习对于顺序循环队列QM，下标从0到M-1，头尾指针分别为F和R，入队时，队尾指针循环加1可表示为，出队