第03章栈和队列B

《第03章栈和队列B》由会员分享，可在线阅读，更多相关《第03章栈和队列B（42页珍藏版）》请在金锄头文库上搜索。

1、3.2 队列（Queue） 第三章 栈和队列1. 基本概念 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式1第三章：栈和队列队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操 作的线性表。它是一种先进先出（）的线性表。在队尾插入元素称为入队入队问：为什么要设计队列？它有什么用途？离散事件的模拟（模拟事件发生的先后顺序 ） 操作系统中的作业调度（一个CPU执行多个作业）简化程序设计。23.2 队列队列的基本概念队列的基本概念队首队尾a1 , a2 , a3 , .,an-1 , an 。在队首删除元素称为出队出队队列的基本概念队列的基本概念与线性表相同，仍为一对一关系。

2、顺序队或链队，以循环顺序队更常见。只能在队首和队尾运算，且访问结点时依照 先进先出（FIFO）的原则。关键是掌握入队和出队操作，具体实现依顺 序队或链队的不同而不同。存储结构存储结构运算规则运算规则实现方式实现方式 逻辑结构逻辑结构只能在表的一端进行插入运算，在表的另一 端进行删除运算的线性表。基本基本操作操作 入队或出队，建空队列，判队空或队满等操作。队尾插入，队头删除队列定义队列定义33.2 队列InitQueue( /队首指针QueuePtr rear ; /队尾指针 LinkQueue;结点类型定义：typedef Struct QNodeQElemType data; /元素QNod

3、e *next; /指向下一结点的指针Qnode , * QueuePtr ;关于整个链队的 总体描述链队中任一 结点的结构链队列链队列队列的链式表示和实现队列的链式表示和实现63.2 队列链队列用链表实现的队列，需要两个分别指向队头的指针 （头指针）和指向对尾的指针（尾指针）。 空链队的特征？Q(队尾)(队首)front a1a2a3rear p 怎样实现链队的入队和出队操作？ 链队会满吗？frontrear front=rear一般不会，因为删除时有free动作。除非内存不足！出队（头部删除）：p=front-next; front-next=p-next; free(p);S D链队示意

4、图：73.2 队列入队（尾部插入）：rearnext=S; rear=S;Q.frontQ.frontQ.rearQ.rear空队列空队列Q.frontQ.frontQ.rearQ.rearQ.frontQ.frontQ.rearQ.rearQ.frontQ.frontQ.rearQ.rearX X Y Y X X Y Y X X 元素元素X X入队列入队列元素元素Y Y入队列入队列元素元素X X出队列出队列链队入队出队示意图：Status EnQueue ( LinkQueue if (!p) exit(ERROR); /存储分配失败p-data = e; p-next = NULL;Q.r

5、ear-next = p; Q.rear-next = p; Q.rear = p; Q.rear = p;return OK; a a1 1a an nQ.frontQ.frontQ.rearQ.reare ep p链队入队的实现 （教材p62）：Status DeQueue ( LinkQueue p = Q.front-next; p = Q.front-next; e = p-data;Q.front-next = p-next;Q.front-next = p-next;free (p); return OK; if ( Q.rear = p ) Q.rear = Q.front;i

6、f ( Q.rear = p ) Q.rear = Q.front;nullnull*q*qq.rearq.rearx xnullnullq.frontq.frontp p内存空间内存空间链队出队的实现 （教材p62）：采用动态分配空间的形式顺序队类型定义 (教材p64):建队核心语句：q . base=(QElemType *)malloc(sizeof (QElemType)* MAXQSIZE); /分配空间关于整个顺序 队的总体描述#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; /队列的基址int front;

7、/队首指针,若队列不为空，/ 指向队列头元素int rear; /队尾指针,若队列不为空，/ 指向队列尾元素的下一个位置 SqQueue113.2 队列循环队列循环队列队列的顺序表示和实现队列的顺序表示和实现Q(队尾)(队首)fronta1a2a3dataa40. . . .99rear 队列会满吗？ 极易装满！因为数组通 常有长度限制，而其前 端空间无法释放。 空队列的特征？约定：front=rear队尾后地址入队(尾部插入)： Qrear=e; rear+ ; 出队(头部删除)： e=Qfront; front+; 讨论：假溢出！假溢出！有 缺 陷 怎样实现入队和出队 操作？核心语句如下：

8、用base做数组名e顺序队示意图：123.2 队列基本操作的实现初始化空队：Q.front=Q.rear=0;Q.front=Q.rear=0; 入队：判断是否队满；非队满时，判断是否队满；非队满时，Q.rearQ.rear位置放新插入位置放新插入 的元素的元素, Q.rear+, Q.rear+出队：判断是否队空，非队空时，判断是否队空，非队空时，Q.frontQ.front位置为待删除位置为待删除 的元素的元素, Q.front+, Q.front+队空条件：Q.front = Q.rearQ.front = Q.rear队满条件：Q.rear = MAXQSIZEQ.rear = MAX

9、QSIZE问题：假上溢！Q.frontQ.front入队入队出队出队a a1 1a a2 2a a3 3 a an nQ.rearQ.rear顺序队操作示意图：front=0front=0 rear=0rear=01 12 23 34 45 50 0队空队空1 12 23 34 45 50 0front=0front=0J J1 1,J,J1 1,J,J3 3入队入队J J1 1J J2 2J J3 3rear=3rear=3rear =6rear =61 12 23 34 45 50 0J J4 4,J,J5 5,J,J6 6入队入队J J4 4J J5 5J J6 6设两个指针设两个指针f

10、ront,rear,front,rear,约定：约定： rearrear指示队尾元素前一位置；指示队尾元素前一位置； frontfront指示队头元素指示队头元素 初值初值front=rear=0front=rear=0空队列条件：空队列条件：front=rearfront=rear 入队列：入队列：sq+rear=x;sq+rear=x; 出队列：出队列：x=sq+front;x=sq+front;1 12 23 34 45 50 0J J1 1,J,J2 2,J,J3 3出队出队顺序队操作示意图：rear=3rear=3front=3front=3front=3front=3解决假溢出的途

11、径采用循环队列答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。问：什么叫“假溢出” ？如何解决？153.2 队列当J6 入队后, 队尾指针Q.rear越界,不可能 再插入新的队尾元素,但是另一方面,队列的 实际可用空间并未占满。一个巧妙的办法是, 将顺序队列设想为首尾相连的环状空间,当 Q.rear 值超出队列空间的最大位置时,令 Q.rear= 0,使队列空间能“循环”使用。这 种循环使用空间的队列称为循环队列。J6J6J4J4J5J5Q.rearQ.rearQ.frontQ.front3 13 12 24 04 05 5循环队列图示循

12、环队列图示5 54 43 32 21 10 0Q.rearQ.rearQ.frontQ.frontJ6J6 J5J5J4J4循环队列示意图：存在问题: 设数组维数为设数组维数为M M，则：则：队首固定，每次出队剩队首固定，每次出队剩余元素向下移动余元素向下移动浪费时间浪费时间 解决方案: 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后,若rear+1=M,则令rear=0;0 0M-1M-11 1frontfrontrearrear.实现：实现：利用利用“ “模模” ”运算运算入队：入队：rear=(rear+1)%M; sqrear=x;rear=(rear+1)%M; s

13、qrear=x; 出队：出队：front=(front+1)%M; x=sqfront;front=(front+1)%M; x=sqfront; 队满、队空判定条件队满、队空判定条件循环队列示意图：假上溢的解决办法 把顺序队列看成首尾相接的环把顺序队列看成首尾相接的环( (钟表钟表)- )-循环队列循环队列基本操作的实现l入队：Q.rear = ( Q.rear+1)%MAXQSIZEQ.rear = ( Q.rear+1)%MAXQSIZEl出队：Q.front = ( Q.front+1)%MAXQSIZE Q.front = ( Q.front+1)%MAXQSIZE l队空条件：Q.

14、front = Q.rearQ.front = Q.rear由于出队由于出队Q.frontQ.front追上了追上了Q.rear Q.rear l队满条件：Q.front = Q.rearQ.front = Q.rear 由于入队由于入队Q.rearQ.rear追上了追上了Q.frontQ.front问题：队空和队满的判断条件一样 循环队列示意图：a3a2a10123N-1rearfront循环队列（臆造）循环队列（臆造）新问题：在循环队列中，空队特征是front=rear；队满时也会有 front=rear；判决条件将出现二义性！ 解决方案有三： 使用一个计数器记录队列中元素个数（即队列长度

15、）； 加设标志位，删除时置1,插入时置0,则可识别当前front=rear属于何种情况 人为浪费一个单元，则队满特征可改为front=(rear+1)%N；顺序队列顺序队列a3a2a1frontrear0123.N-1193.2 队列队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1+1) % N (N=maxsize) 队列长度（即数据元素个数）：L=（Nrearfront）% N J2 J3J1 J4J5frontrear实际中常选用方案3（人为浪费一个单元）： 即front和rear二者之一指向实元素，另一个指向空闲元素。 问3： 在具有n个单元的循 环队列中，队满时共有多少 个元素？ N-1个6 问1：左图中队列maxsize N=？问2：左图中队列长度L=？5203.2 队列n 队列存放数组被当作首尾相接的表处理。n 队头、队尾指针加1时从maxSiz