主要内容

队列的定义

循环队列的存储结构

循环队列的各项操作

初始化

入队

出队

取队头元素

求队列长度

?

队列的定义

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

队列（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;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!