首页天道酬勤循环队列的结构定义,循环队列是什么存储结构

循环队列的结构定义,循环队列是什么存储结构

张世龙 05-06 11:33 36次浏览

为了充分利用向量空间,克服“假溢出”现象的方法是认为向量空间是一个首尾相连的圆环,并将该向量称为循环向量。 存储在其中的队列称为Circular Queue。 循环队列将顺序队列成功地连接起来,并将存储队列元素的表在逻辑上视为一个循环,作为循环队列。

中文名称

循环队列

外语名称

Circular队列

如何实现域

术语

特长

尺寸固定

循环队列概述

编辑

语音

循环队列是将队列存储空间中的最后一个位置旋转到第一个位置,以形成逻辑循环空间,队列可以重用。 在循环队列结构中,使用存储空间的最后一个位置,在进入队列操作时,如果存储空间的第一个位置为空,则可以将第一个位置(即存储空间的第一个位置)添加到队列的最后一个元素。 [1]

循环队列可以更容易地防止伪溢出的发生,但队列的大小是固定的。

在循环队列中,如果队列为空,则有front=rear;如果所有队列空间都已满,则有front=rear。 为了区分这两种情况,规定循环队列最多只能有MaxSize-1一个队列元素,如果循环队列中只有一个空存储单元,则队列已满。 因此,队列为空的条件是front=rear,队列满的条件是front=(rear 1) %MaxSize。 [2]

循环队列的基本操作

编辑

语音

//队列顺序存储结构(循环队列) )

#defineMAX_QSIZE5//最大队列长度1

类型定义结构{

int*base; //初始化的动态分配存储空间

intfront; //开头指针,如果队列不空,则指向队列的开头要素

intrear; //末尾指针,如果队列不空,则指向队列末尾元素的下一个位置

} sq队列;

//创建空队列q

SqQueue*Q_Init (

sqqueue*q=(sqqueue* ) malloc ) sizeof ) sqqueue );

//存储分配失败

if (! q ) {

溢出;

}

q-base=(int* ) malloc ) max_qsize*sizeof ) int );

//存储分配失败

if (! 问题库

溢出;

}

Q-front=Q-rear=0;

returnQ;

}

//放弃队列q,q不再存在

voidq_destroy(sqqueue*q ) {

是if (知识库)

自由(q-base );

q-base=空;

Q-front=Q-rear=0;

free(q;

}

//Q为空队列

voidq_clear(sqqueue*q ) {

Q-front=Q-rear=0;

}

//如果队列q为空队列,则返回1; 否则返回-1

intq_empty(squeueq ) {

if(q.front==q.rear )//队列为空的标志

返回1;

else

返回- 1;

}

返回//q的元素数,即队列长度

intq_length(squeueq ) {

return(q.rear-q.frontmax_qsize ) %MAX_QSIZE;

}

//如果队列不空,用e返回q的团队领导要素,返回OK; 否则返回错误

intq_gethead(squeueq,inte ) {

if(q.front==q.rear )//队列为空

返回- 1;

e=Q.base[Q.front];

返回1;

}

//打印队列内容

voidq_print(squeueq ) {

intp=Q.front;

while(q.rear!=p (

出局了

p=(p1 ) %MAX_QSIZE;

}

}

//元素e插入q的新队列端元素

intq_put(sqqueue*q,inte ) )

if () q-rear1) %MAX_Q

SIZE == Q->front) // 队列满

return -1;

Q->base[Q->rear] = e;

Q->rear = (Q->rear + 1) % MAX_QSIZE;

return 1;

}

// 若队列不空,则删除Q的队头元素,用e返回其值,并返回1;否则返回-1

int Q_Poll(SqQueue *Q, int &e) {

if (Q->front == Q->rear) // 队列空

return -1;

e = Q->base[Q->front];

Q->front = (Q->front + 1) % MAX_QSIZE;

return 1;

}

循环队列条件处理

编辑

语音

循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。

解决这个问题的方法至少有两种:

① 另设一布尔变量以区别队列的空和满;

②另一种方式就是数据结构常用的: 队满时:(rear+1)%n==front,n为队列长度(所用数组大小),由于rear,front均为所用空间的指针,循环只是逻辑上的循环,所以需要求余运算。如图1所示情况,队已满,但是rear(5)+1=6!=front(0),对空间长度求余,作用就在此6%6=0=front(0)。

图1

类型定义采用环状模型来实现队列,各数据成员的意义如下:

front指定队首位置,删除一个元素就将front顺时针移动一位;

rear指向元素要插入的位置,插入一个元素就将rear顺时针移动一位;

count存放队列中元素的个数,当count等于MaxQSize时,不可再向队列中插入元素。

循环队列队列

编辑

语音

数据结构分为线性结构和非线性结构,队列和线性表都是线性结构。线性表是由n 个数据元素组成的有限序列,该序列有惟一的“第一个”和惟一的“最后一个”数据元素;除了 “第一个”和“最后一个”之外,队列中的每个数据元素都只有一个直接前驱和一个直接后继。线性表的插入和删除操作可以在表中任意位置进行。队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。

词条图册

更多图册

参考资料

1.

杨非.C语言程序设计应试辅导: 二级:清华大学出版社,2006

c语言数据结构链式队列,c语言实现循环队列