C# · 12月 20, 2021

数据结构知识整理 – 循环队列

主要内容

队列的定义

循环队列的存储结构

循环队列的各项操作

初始化

入队

出队

取队头元素

求队列长度

 

队列的定义

栈和队列是两种重要的线性结构,与一般线性表不同,它们是操作受限的特殊线性表,主要用于辅助其他数据结构的操作和处理,基本不用于存储数据元素信息。

队列(Queue)是一种先进先出(First In First Out,FIFO)的线性表。它只允许在表的一端插入,而在表的另一端删除元素。这和日常生活中的排队一个道理。

在队列中,允许插入的一端叫队尾(rear),允许删除的一端则称为队头(front)。

循环队列的存储结构

循环队列是队列特殊的顺序存储结构。

附设指针rear指向队尾元素,指针front指向队头元素。

若将队列的指针rear对应栈的指针top,将队列的指针front对应栈的指针bottom。

初始时,空队状态,指针rear == 指针front;

一个元素A入队后,指针front指向队头(尾)元素A,但是指针rear不能继续指向A了,不然就会跟判断空队的条件冲突,所以指针rear只能 +1,如此类推,指针rear始终指向队尾元素的下一个位置。(从理解角度来看,可以说是指向上一个位置,建议画图)

若队列采用普通的顺序存储结构,队列长度为n,只有m(m<=n)个元素入队,之后不再有元素入队。等队列中的元素部分或全部出队后,必然有空间被闲置着,造成浪费,因为队列的指针front不像栈的指针bottom那样固定。

为了不造成空间的浪费,我们可以将队列的头尾“连接”起来,形成循环队列。

那应该如何实现“连接”呢?

取模。通过“模”运算,rear = (rear + 1) % n,得到指针rear的新指向。

在循环队列中队空和队满的条件(空出一个元素空间):

1)队空:rear == front;

2)队满:(rear + 1) % MAXSIZE == front;        /*循环意义上 rear+1 == front*/

需要注意的是,对比起顺序栈,循环队列若rear和front采用指针结构,则无法进行队满的判断(不能用%符号),所以rear和front以数组编号的形式作用。

#define MAXSIZE 100

typedef struct

{

Elemtype *base; /*循环队列存储空间的基地址*/

int rear; /*队尾指针*/

int front; /*队头指针*/

int queuesize;

} SqQueue;

循环队列的各项操作

队头删除元素,队尾插入元素。

初始化

为循环队列动态分配一个预定义大小(最大容量)的数组空间。

void InitQueue(SqQueue &Q)

{

Q.base = new Elemtype[MAXSIZE]; /*new为动态分配的标志*/

if(!Q.base) exit(-1); /*存储分配失败,用exit()函数退出程序*/

/*exit(0)表示程序正常退出,exit⑴/exit(-1)表示程序异常退出*/

Q.rear = Q.front = 0; /*rear、front初始为0,表示空队*/

Q.queuesize = MAXSIZE; /*设置队长*/

}

入队

队尾插入元素,指针rear在循环的意义上+1。

void EnQueue(SqQueue &Q,Elemtype e)

{

if((Q.rear + 1) % queuesize == Q.front) exit(1); /*栈满,程序异常退出*/

Q.base[Q.rear] = e;

Q.rear = (Q.rear + 1) % queuesize; /*指针rear在循环的意义上+1*/

}

出队

在队头返回出队元素,指针front在循环的意义上+1。

void DeQueue(SqQueue &Q,Elemtype &e)

{

if(Q.rear == Q.front) exit(-1); /*队头*/

e = Q.base[Q.front]; /*保存队头元素*/

Q.front = (Q.front + 1) % queuesize; /*指针front在循环的意义上+1*/

/*因为在程序中改变了e的引用,所以不需要返回任何值*/

}

取队头元素

Elemtype GetHead(SqQueue Q)

{

if(Q.rear != Q.front) /*队非空*/

return Q.base[Q.front];

}

求队列长度

对于非循环队列,尾指针-头指针便是队列长度,而对于循环队列,需要look代码。

int QueueLength(SqQueue Q)

{

return (Q.rear – Q.front + queuesize) % queuesize;

}