第3章 栈与队列 2次2

第3章栈与队列1回顾线性表及操作特殊的线性表——栈栈的操作原则栈的顺序存储和链式存储结构栈的操作2第3章栈与队列学习目的要求:栈的基本概念和栈的基本运算。栈在计算机中的应用。队列的基本概念和队列的基本运算。队列在计算机中的应用。33.2队列3.2.1队列的定义队列（queue）也是一种特殊的线性表。特殊性：它仅允许在表的一端进行插入，在表的另一端进行删除。4a1a2a3a4a5a6rearrearrearrearrearrearfrontfrontfrontfrontfrontfrontrear3.2队列3.2.1队列的定义队列的操作： a1,a2,a3入队，

a1,a2出队，a4,a5,a6入队，

a3,a4,a5,a6出队。 由于每个元素必然按照进入的次序离队，所以又把队列称为“先进先出”表（FirstInFirstOut，简称FIFO表）53.2队列3.2.1队列的定义队尾：允许进行插入操作的一端，由队尾指针rear指示队空：当队列中没有元素时称为队空队首：允许进行删除操作的一端，由队首指针front指示出队：队的删除操作,又称离队入队：队列的插入操作，又称进队6队列的基本操作可以归纳为以下几种:

（1）InitQueue（）;初始化一个空队列Q；（2）GetFront（&Q，&y）;取队列Q的队头元素，y返回其值，但队列Q状态不变；（3）EnQuene（&Q，x）;若队列Q还有空间，将元素x插入到队尾；（4）DelQueue（&Q，&y）;若队列Q不为空，删除队列Q的队头元素，y返回其值；（5）Empty（&Q）;判断队列Q是否为空，若为空返回一个真值，否则返回一个假值。3.2队列7队列的存储结构：顺序存储——顺序队列链式存储——链队列3.2队列83.2.2队列的顺序存储结构及其运算1.顺序队列队列顺序存储结构称为顺序队列（sequentialqueue）。顺序队列与顺序表一样，用一个一维数组来存放数据元素。在内存中，用一组连续的存储单元顺序存放队列中各元素。3.2队列93.2.2队列的顺序存储结构及其运算1.顺序队列#defineMAXLEN10typedef

int

elementtype;typedef

struct

/*队列的顺序存储结构定义*/{

int

element[MAXLEN];/*存放队列元素的数组*/

intfront,rear; /*队首指针,队尾指针*/}SeQueue;3.2队列1043210front=rear=-1(1)初始空队(2)元素a入队(3)元素b,c,d入队(4)元素a出队43210rearafront=-1rear=043210reardcbafront=-1rear=343210reardcbfront=0rear=3front总结：（1）在队列为空的初始状态时，front=rear=-1。（2）每当向队列插入一个元素，尾指针rear向后移动一位，rear=rear+1。（3）当rear=MAXLEN-1时，表示队满;（4）每从队列中删除一个元素时，队首指针也向后移动一位，front=front+1。（5）入队的所有元素都出队后，队列为空，此时front=rear;11说明：（1）指针的位置：队尾指针指向队尾元素（尾元素下标），队首指针指向队首元素的前一个位置；（2）溢出：当队列满时（rear=MAXLEN-1）再做入队运算必定产生空间溢出，简称“上溢”；当队列空时（front=rear）再做出队运算也将产生溢出，简称“下溢”3.2队列3.2.2队列的顺序存储结构及其运算12a1a2a3a4a5a6rearrearrearrearrearrearfrontfrontfrontfrontfrontfrontrear入队、出队操作：3.2队列3.2.2队列的顺序存储结构及其运算012345入队：(1)判满; (2)移动队尾指针rear++；

(3)新元素入队尾element[rear]=x;出队：(1)判空; (2)移动队首指针front++; (3)返回删除元素x=element[front]；elementfront=rear=-113（1）入队int

Enqueue_sq(SeQueue*q,elementtypex){

if(q->rear==MAXLEN-1)return(0);/*队列满返回0*/q->rear++;q->element[q->rear]=x;return(1);}3.2队列3.2.2队列的顺序存储结构及其运算14（2）出队int

Delqueue_sq(SeQueue*q,elementtype*x){

if(q->front==q->rear)return(0);/*队列空返回0*/else{q->front++;*x=q->element[q->front];return(1);}}3.2队列3.2.2队列的顺序存储结构及其运算15队列的存储结构：顺序存储——顺序队列链式存储——链队列3.2队列163.2.3队列的链式存储结构及其运算队列的链式存储结构称为链队列（linkedqueue）。3.2队列用带头结点的单链表表示如下：173.2.3队列的链式存储结构及其运算链队列的结构定义：typedef

structnode /*定义链队列结点*/{

intdata; /*以整型数据为例*/

structnode*next; /*存放下一个结点地址*/}NODE;3.2队列183.2.3队列的链式存储结构及其运算链队列的操作：（1）链队列为空条件：front=rear;均指向头结点。（2）链队列不存在满的情况，除非内存已满。（3）入队操作：向队尾插入新结点。（4）出对操作：删除队首结点。3.2队列193.2.3队列的链式存储结构及其运算3.2队列链队列入队操作：xfront①生成新结点并由指针p指向新结点，数据域赋值为x，指针域为NULL；bc∧③修改队尾指针rear=t;parear②向队尾插入结点完成入队,rear->next=t；∧20（1）入队NODE*pushqueue(NODE*rear,intx)/*入队操作*/{NODE*p;p=(NODE*)malloc(sizeof(NODE));p->data=x;/*将要插入的数据x存储到结点p的数据域中*/p->next=NULL;rear->next=p;/*将p插入链队列尾部*/rear=p; /*修改队尾指针rear*/

return(rear);}3.2队列213.2.3队列的链式存储结构及其运算3.2队列链队列出队操作：①队列不为空的情况下，指针p指向队列的首元素③返回删除结点的数据p->data，释放结点free(p);rear②删除队首结点，完成出队,front->next=p->next；pfrontbc∧a22（2）出队NODE*popqueue(NODE*front,NODE*rear,int*x)/*出队操作*/{NODE*p;

if(front!=rear)/*判断链队列空,若链队列不空*/{p=front->next; /*p指向链队列第一个元素*/front->next=p->next; /*将p元素出队*/

if(p->next==NULL) /*表示原链队列中只有一个元素*/rear=front;/*出队后,队空,修改rear指针*/*x=p->data; /*保存出队后的元素值*/

free(p);

return(rear);/*返回rear*/}}3.2队列23总结队列的定义队列的操作特点队列的存储结构顺序队列判空、判满条件队列的入队、出队操作242.循环队列3.2队列a1a2a3a4a5a6rearrearrearrearrearrearfrontfrontfrontfront012345顺序队列操作的过程中可能会出现这样情况，尾指针指向一维数组最后，但前面有元素已经出队，这时要插入元素，仍然发生溢出，而实际上队列并未满。这种溢出称为“假溢出”。为了解决这个问题，下面讨论循环队列。252.循环队列循环队列是将存储队列的存储区看成是一个首尾相连的环，即将表示队列的数组元素element［0］与element［MAXLEN-1］连接起来，形成一个环形表。3.2队列当队列的第MaxSize-1个位置被占用以后，只要队列的前端还有可用空间，则把新的数据元素加入队列的第0号位置。26

540312front=rear=-1rearfeadbc

540312front=-1;rear=52)a,b,c,d,e,f入队fedc

540312rearrear=5front=1front3)a,b出队1)初始空队入队操作：rear=(rear+1)%MAXLEN;element[rear]=x;元素出队：front=(front+1)%MAXLEN;解决：通过rear=(rear+1)%MAXLEN，让rear归零。问题：当rear=MAXLEN-1时，再执行rear++，数组下标越界。27fegdhc

540312rearfront=rear=1front4)g,h入队，队满

540312rearfront=rear=1front5)c,d,e,f,g,h出队，队空问题：当队满和队空时条件都是front=rear此时：front=rear是循环队列空的标志；（rear+1）%MAXLEN=front是循环队列满的标志。解决方法:(1)设标志位；(2)少用一个元素空间283.2队列2.循环队列队空条件：rear=front队满条件：(rear+1)%MAXLEN=front入队操作：rear=(rear+1)%MAXLEN;element[rear]=x;出队操作：front=(front+1)%MAXLEN;x=element[front];总结：29（1）入队int

EnCqueue(CQueue*cq,elementtypex){

if((cq->rear+1)%MAXLEN==cq->front)return(0);/*循环队列满返回0*/else{

cq->rear=(cq->rear+1)%MAXLEN;

cq->element[cq->rear]=x;return(1);}}3.2队列30（2）出队int

DelCqueue(CQueue*cq,elementtype*x){

if(cq->rear==cq->front)return(0);/*循环队列空返回0*/else{

cq->front=(cq->front+1)%MAXLEN;*x=cq->element[cq->front];return(1);}}3.2队列313.2.4队列的应用例3.6打印数据缓冲区问题。在打印机打印的时候，主机输出数据的速度比打印机打印的速度要快得多。由于速度不匹配，大大影响了主机的工作效率。为了解决这个问题，通常是在内存中设置一个打印数据缓冲区。缓冲区是一块连续的存储空间，把它设计成循环队列结构，主机把要打印的数据依次写入到这个缓冲区中，写满后就暂停输出，主机此时可以进行其他工作。打印机就从缓冲区按