队列的顺序表示——用一维数组base[MAXQSIZE]
#define MAXQSIZE 100 //最大队列长度
Typedef struct{
QElemType *base;//初始化的动态分配存储空间
int front;//头指针
int rear;//尾指针
}SqQueue;
溢出:
当rear = MAXQSIZE时,发生溢出
(1)若front = 0
rear = MAXQSIZE时
再入队——真溢出
(2)若front ≠ 0
rear = MAXQSIZE时
再入队——假溢出
解决假上溢的方法:
(1)将队中元素依次向对头方向移动
缺点:浪费时间,每移动一次,队中元素就要移动
(2)将队空间设想成一个循环的表,即分配给队列的m个存储单元可以循环使用,当rear为maxqsize时,若向量的开始端空着,又可以从头使用空着的空间;当front为maxqsize时,也是一样
引入循环队列:
base[0]接在base[MAXQSIZE-1]之后,若rear+1==M,则令rear=0
实现方法:利用模(mod,C语言中:%)运算
插入元素:Q.base[Q.rear]=x
Q.rear=(Q.rear+1) % MAXQSIZE;
删除元素:x=Q.base[Q.front]
Q.front=(Q.front+1)%MAXQSIZE
循环队列:循环使用为队列分配的存储空间
循环队列的操作:
(1)队列的初始化:
Status InitQueue (SqQueue &Q){
Q.base = new QElemType[MAXQSIZE] //分配数组空间
if(!Q.base) exit(OVERFLOW) //存储分配失败
Q.front = Q.rear = 0; //头指针尾指针置为0,队列为空
return OK;
}
(2)求队列的长度:
int QueueLength(SqQueue Q){
return((Q.rear - Q.front +MAXSIZE) % MAXSIZE);
}
(3)循环队列入队
Status EnQueue(SqQueue &Q, QElemType e){
if ((Q.rear +1)%MAXQSIZE==Q.front) return ERROR;//队满
Q.base[Q.rear] =e;//新元素加入队尾
Q.rear = (Q.rear+1)%MAXQSIZE;//队尾指针+1
return OK;
}
(4)循环队列出列
Status DnQueue(SqQueue &Q, QElemType e){
if (Q.front==Q.rear) return ERROR;//队空
e = Q.base[Q.front];//保存队头元素
Q.front = (Q.front+1)%MAXQSIZE;//队头指针+1
return OK;
}
(5)取队头元素
SElemType GetHead(SqQueue Q){
if(Q.front != Q.rear) //队列不为空
return Q.base[Q.front]; //返回队头指针元素的值,队头指针不变
}
