循环队列的一些问题总结，入队、出队操作

在复习数据结构——队列这一节时遇到了一些问题，现总结如下，以便以后查阅：

在队列的顺序存储方式里，为了避免存储空间的“假溢出”，充分利用存储空间，我们用了一种实现方式，即循环队列。

循环队列的一些问题总结，入队、出队操作

(1). 图中有两个指针(只是两个整型变量，因为在这里有指示作用，所以理解为指针) front、rear，一个指示队头，一个指示队尾（这里注意：rear定义为指向队尾元素还是队尾元素的下一个空间）。

(2). rear和front互相追赶着，这个追赶过程就是队列添加和删除的过程，如果rear追到head说明队列满了，如果front追到rear说明队列为空。

如此一来，将出队的剩余的空间给予入队，满足了有限空间里的利用率要求。这些都是显而易见的。

第二点是由第一点那个rear指针发散的。实在是网上的博客资料太多，不同的书本里又说法不一。比如，老师上课说的是rear指针是指向队尾元素的，但我的一本书上却是指向队尾元素的下一个位置。我对照着写代码于是就出现了这样的问题：

两个乱码，分别出现在第一个入队元素和第一个出队元素上。当时看到就很烦，或许是当时大脑宕机，没有找出啥问题。第二天才发现是我rear指针的概念理解错了。贴一下改之前代码：

Status EnQueue(Queue *Q, ElemType e){  //入队操作
	if(!Q->space ||(Q->rear+1)%MAXSIZE == Q->head)
		return ERROR;
	Q->space[(Q->rear+1)%MAXSIZE]=e;  //Q->space[Q->rear] = e;
	Q->rear = (Q->rear+1)%MAXSIZE;
	return OK;
}

更改之后的代码（rear指针为指向队尾的下一个位置）：

	~~Q->space[(Q->rear+1)%MAXSIZE]=e;  //Q->space[Q->rear] = e;~~ 
	Q->space[Q->rear]=e;

同样的出队的代码：

Status DeQueue(Queue *Q,ElemType *e){  //出队操作
	if(!Q->space || Q->head == Q->rear)
		return ERROR;
	*e = Q->space[(Q->head+1)%MAXSIZE];  //同样的是这里
	Q->head = (Q->head+1)%MAXSIZE;
	return OK;
}

更改之后：

	~~*e = Q->space[(Q->head+1)%MAXSIZE];  //同样的是这里~~ 
	*e = Q->space[Q->head];

然后是我的输出操作（我将输出队列所有元素写成了一个函数）：

Status PrintQueue(Queue Q){
	if(Q.space == NULL)
		return ERROR;
	while(Q.head != Q.rear){
		printf("%d ",Q.space[Q.head]);  //这两步的顺序别错了
		Q.head = (Q.head+1)%MAXSIZE;  //这两步的顺序别错了
	}
	printf("\n");
	return OK;
}

到此为止这个bug算是解决了。

我再总结下循环队列的各个满足条件吧：（这里front表示头指针）

(1). 当队列添加元素到rear的下一个元素是head的时候，也就是转圈子要碰头了，我们就认为队列已满：(Q.rear+1)%MAXSIZE == Q.front

(2). 当队列删除元素到head=rear的时候，我们认为队列为空：Q.rear == Q.front

(3). 计算队列的长度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE

(4). 入队：Q->rear = (Q->rear+1)%MAXSIZE; //rear指针向后移一个位置

(5). 出队：Q->front = (Q->front+1)%MAXSIZE; //front指针向后移一个位置

.……暂且到这吧

以上如果有什么问题，欢迎大佬指出！也感谢各位百忙中偶然看到这个blog的好奇一览！

循环队列的一些问题总结，入队、出队操作

相关推荐