大学《数据结构》第三章：栈和队列-第三节-队列（一）

第三节队列(一)

一、队列的定义及其运算

1、队列的定义

队列(Oueue)是一种操作受限的线性表，它只允许在表的一端进

行元素插入，而在另一端进行元素删除。允许插入的一端称为队尾

(rear),允许删除的一端称为队头(front)。新插入的结点只能添

加到队尾，被删除的只能是排在队头的结点，因此，队列又称为先进

先出(FirstInFirstOut)的线性表，简称为FIFO表。

【真题选解】某队列初始为空，若它的输入序列为(a,b,c,

d),它的输出序列应为()。

A.a,b,c,dB.d,c,b,a

C.a,c,b,dD.d,a,c,b

隐藏答案

【答案】A

【解析】队列的出队序列一定与入队序列完全一样。

2、队列的基本运算

Q)置空队列InitQueue(Q),构造一个空队列。

(2)判队空QueueEmpty(Q)，若Q为空队列，则返回TRUE,否则

返回

FALSEO

(3)入队列En(jueue(Q,x),若队列不满，则将数据x插入到Q的

队尾。

(4)出队列DeQueue(Q),若队列不空，则删除队头元素，并返回

该元素。

(5)取队头GetFront(Q),若队列不空，则返回队头元素。

二、顺序循环队列

1、顺序队列的概念

队列的顺序存储结构称为顺序队列。队列的III页序存储结构是利用一

块连续的存储单元存放队列中的元素的，设置两个指针front和rear

分别指示队头和队尾元素在表中的位置。

【例】设有一111酹队列Q,容量为5,初始状态时

Q.front=Q.rear=0,画出做完下列操作后队列及其头尾指针的状态变

化情况，若不能入队，请简述其理。

(1)d,e,b入队

(2)d,e出队

(3)i,j入队

(4)b出队

(5)n,o,p入队

【解答】队列及其头尾指针的状态变化情况如图所示

Sq.rear

Sq.rearSq.front

Sq.front

(a)初态(b)d,e,b入队(c)d,e出队(d)i,j入队(e)b出队

第（5）步操作无法进行，因队列已满，再有元素入队，就会溢

出，发生假溢。

2、顺序循环队

为了解决III酹队的"假溢”问题采用循环队。约定循环队的队头指针

指向队头元素在数组中实际位置的前一个位置,队尾指针指示队尾元

素在数组中的实际位置。其次再约定队头指针指示的结点不用于存储

队列元素，只起标志作用。这样当队尾指针"绕一圈"后赶上队头指针

时视为队满。

【例】设Q是一个有11个元素存储空间的顺序循环队列，初始状

态Q.front=Q.rear=O,写出下列操作后头、尾指针的变化情况,

若不能入队，请说明理由。

d,e,b,g,h入队;d,e出队；

i,j,k,I,m入队；b出队；

n,o,p,q,r入队

【解答】

(1)初始状态

012345678910

IIIIIIIIII1~~

pear

front

(2)d,e,b,g,h入队

012345678910

debgh

p&ontrear

(3)d,e出队

012345678910

bgh

i4

frontrear

(4)b)9k,Lm入队

012345678910

bghijk1m

(5)b出队

012345678910

ghijk1m

frontrear

(5)n,o,p,q,r入队

012345678910

0Pghijk1mn

rearfront

注意：p入队以后，队列就满了，不能再入队了，此时队列中的元

素个数为10个(数组长度是11)

"rear-front(rearNfront)

-

总结：队中元素个数：IQueueSize-rear-front(rear<front)

两种情况合并为：(QueueSize+rear-front)%QueueSize;

【真题选解】

设循环队列的容量为50（序号从0到49）,现经过一系列的入队和

出队运算后，有①front=ll,rear=29;②front=29,rear=ll;在

这两种情况下，循环队列中的元素个数分别是____和O

隐藏答案

【解析】当front=ll,rear=29时,循环队列中的元素个数

=rear-front=29-ll=18;当front=29,rear=ll时，循环队列中的

元素个数

50-(front-rear)=50+rear-front=50+ll-29=32o

【答案】1832

3、循环队的顺序存储的类型定义

#defineQueLleSize100

typedefcharDataType;〃假设数据为字符型

typedefstruct

{DataTypedata[QueueSize];

intfront,rear;

}CirQueue;

4、循环队列基本运算的各算法

(1)置空队列

voidInitQueue(CirQueue*Q)

{Q->front=Q->rear=0;

)

(2)判队空

intQueueEmpty(CirQueue*Q)

returnQ->rear==Q->front;

)

(3)判队满

intQueueFull(CirQueue*Q)

(

return(Q->rear+l)%QueueSize==Q->front;

)

(4)入队列

voidEnQueue(CirQueue*Q,DataTypex)

{〃插入元素x为队列Q新的队尾元素

if(QueueFull(Q))

printf("Queueoverflow");

else

{Q->data[Q->rear]=x;

Q->ear=(Q->rear+l)%QueueSize;〃循环意义下的

加1

}

)

(5)取队头元素

DataTypeGetFront(CirQueue*Q)

{//获取Q的队头元素值

if(QueueEmpty(Q))

{printf("Queueempty")；

exit(O);)

else

returnQ->data[Q->frontjj

)

(6)出队列

DataTypeDeQueue(CirQueue*Q)

{〃删除Q的队头元素，并返回其值

DataTypex;

if(QueueEmpty(Q))

{printf("Queueempty");

exit(O);

)

else

{x=Q->data[Q->front];〃保存待删除

元素值

Q->front=(Q->front+l)%QueueSize;〃头指针加

1

returnx;〃返回删除元素值

)

)

【例】设栈S=(l,2,3,4,5,6,7),其中7为栈顶元素。请写

出调用函数Algo(S)后栈S的状态。其函数为：

voidAlgo(SeqStackS)

{inti=l;

CirQueueQ;SeqStackT;〃定义一个循环队列

和一个栈

InitQueue(&Q);Initstack(&T);〃初始化队列和栈

while(!StackEmpty(&S))

{if(i%2!=0)

Push(&T,Pop(&S));〃栈中序号为奇数的

元素入T栈中

〃7、5、3、1顺序入栈

To

else

EnQueue(&Q,Pop(&S));〃序号为偶数的元素

入队列Q中

〃6、4、2]1褥入队Q。

i++;

)

while(!QueueEmpty(&Q))

Push(&S,DeQueue(&Q));〃队Q中6、4、2

顺序出队并入栈S

while(!StackEmpty(&T))

Push(&S,Pop(&T));〃队栈T中按1、3、

5、7顺序出栈并入栈S

)

最后栈S中的元素为(6、4、2、1、3、5、7)。

三、链队

1、链队的定义

队列的链式存储结构称为链队列。它是一种限制在表头删除和表尾

插入操作的单链表。

2、链队的数据类型定义

typedefstructqnode

{DataTypedata;

structqnode*next;

}QueueNode;

typedefstruct

{QueueNode*front;〃队沿旨针

QueueNode*rear;〃队尾指针

}LinkQueue;

LinkQueueQ;

Q头结点队头结点队尾结点

Q.frontl——-\―Ta|T一Ta：|…&|八

Q.rear]

3、链队的基本运算实现

(1)构造空队列

Q->front

Q->reax

voidInitQueue(LinkQueue*Q)

Q->front=(QueueNode*)malloc(sizeof(QueueNode));

〃申请头结点

Q->rear=Q->front;//

尾指针也指向头结点

Q->rear->next=NULL;

)

(2)判队空

intQueueEmpty(LinkQueue*Q)

returnQ->rear==Q->front;〃头尾指针相等队列为空

)

(3)入队列

Q->front

Q->reax

voidEnQueue(LinkQueue*Q,DataTypex)

{〃将元素x插入链队列尾部

QueueNode*p=(QueueNode

*)malloc(Sizeof(QueueNode));〃申请新结点

p->data=x;

p->next=NULL;

Q->rear->next=p;//*p链到原队尾结点之后

Q->rear=p;〃队尾指针指向新的队尾结点

)

(4)取队头元素

DataTypeGetFront(LinkQueue*Q)

{//取链队列的队头元素值

if(QueueEmpty(Q))〃判队空

{printf("Queueunderflow");

exit(O);〃出错退出处理

)

else

returnQ->front->next->data;〃返回原队头元素值

)

(5)出队列

链队列的出队操作有两种不同情况要分别考虑。

①当队列的长度大于1时，则出队操作只需要修改头结点的指针域

即可，尾指针不变，类似于单链表删除首结点，操作步骤：

s=Q->front->next;

Q->fron->next=s->next;

x=s->data;

free(s);returnx;//释放队头结点，并返回其值

②若列队长度等于I,则出队时不仅要修改头结点指针域，而且还

需要修改尾指针。

Q头结点

Q->frontQ->front

Q->rearQ->reax

出队前出队后

s=Q->front->next;

Q->front->next=NULL;〃修队头指针

Q->rear=Q->front;〃修改尾指针

x=s->data;

free(s);returnx;//释放队头结点，并返回其值

为了方便，直接删除头结点，将原队头结点当头结点使，这样算法

就简单了。

Q头结点队头结点队尾结点

Q.front»a1|二--aa?-j»]：I.I人

Q.rear—J

链队列的出队算法描述

DataTypeDeQueue(LinkQueue*Q)

(〃删除链队列的头结点，并返回头结点的元素值

QueueNode*P;

if(QueueEmpty(Q))

{printf("Queueunderflow");

exit(O);〃出错退出处理

)

else

{p=Q->front;〃p指向头结点

Q->front=Q->front->next;//沿旨针指向原队头结点

free(p);〃删除释放原头结点

return(Q->front->data);〃返回原队头结点的数据值

)

}

【真题选解】算法f31的功能是清空带头结点的链队列Q.请在空缺

处填入合适的内容,使其成为一个完整的算法.

typedefstructnode

{DataTypedata;

structnode*next;

}QueueNode;

typedefstruct

{QueueNode*front;//队沿旨针

QueueNode*rear;〃队尾指针

JLinkQueue;

voidf31(LinkQueue*Q)

{QueueNode*p,*s;

p=(1);

while(p!=NULL)

{s=p;

p=p->next;

free(s);

)

⑵=NULL;

Q->rear=(3);

)

(1)___________________________________________

⑵___________________________________________

⑶___________________________________________

隐藏答案

【解析】算法f31的功能是清空带头结点的链队列Q,就是要删除

除了头结点以外的所有结点，指针p负责扫描整个队列，所以第(1)

空应该填Q->front->next。通过执行while循环，删除了除了头结

点以外的所有结点，最后要将头结点的指针域填上NULL,队尾指针

指向头结点。所以，第(2)空应该填Q->front->next，第(3)空

填

Q->fronto

【答案】(1)Q->front->next(2)Q->front->next(3)

Q->front

4、循环链队列

队头结点队尾结点

a；A•••

循环链队列的类型定义

typedefstructqueuenode

{DataTypedata;

structqueuenode*nex