My Little World

循环队列

发表于

假溢出

queue9
循环队列的容量是固定的，并且它的对头和队尾指针都可以随着元素出入队列而发生改变，
这样循环队列逻辑上就好像是一个环形存储空间,但在实际内存中，是不可能有真正的环形存储区的，
我们只是用顺序表模拟逻辑上的循环
因此,为防止发生假溢出,当我们采用循环队列时,front和rear不断加1,即使超出了地址范围，
也会自动从头开始,判断溢出，可采用取模处理
(rear+1)%QueueSize
(front+1)%QueueSize
取模即取余数，取得的值永远不会大于除数

定义一个循环队列

queue12

1
2
3
4
5
6
# define MAXSIZE 100
typedef struct{
	ElemType *base;	##存放内存分配基地址，也可以用数组存放
	int front;
	int rear;
}

初始化一个循环队列

1
2
3
4
5
6
7
initQueue(cyclQueue *q){
	q->base = (ElemType *)malloc(MAXSIZE sizeof(ElemType));
	if(!q->base){
	exit(0);
	}
	q->front = q->rear = 0;
}

入队列操作

1
2
3
4
5
6
7
insertQueue(cyclQueue *q,ElemType e){
	if((q->rear+1)%MAXSIZE == q->front){
	return;	##队列已满
	}
	q->base[q->rear] = e;
	q->rear = (q->rear+1)%MAXSIZE;
}

出队列操作

1
2
3
4
5
6
7
DeleteQueue(cyclQueue *q,ElemType e){
	if(q->rear == q->front){
	return;	##队列为空
	}
	*e = q->base[q->front];
	q->front = (q->front+1)%MAXSIZE;
}