循环队列的结构定义,循环队列是什么存储结构
为了充分利用向量空间,克服“假溢出”现象的方法是认为向量空间是一个首尾相连的圆环,并将该向量称为循环向量。 存储在其中的队列称为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