【算法】循环队列

亦凉 2023-10-16 22:55 109阅读 0赞

## 说明 ##

循环队列是一种先进先出的，首尾相连的队列。

大致的结构如下图：

![Center][]

用数组来抽象的表示一下的话，如下图：

![Center 1][]

循环队列有两个指针指向数据，上图中的start和end就是那两个指针，它们指向相同的位置，表示的是空，即队列是空的。

随着数据的放入，队列一般有下面的两种形式：

![Center 2][]

![Center 3][]

需要注意第二种形式，从图上看end在start的前面了，但是因为循环关系，前后并不重要。

另外需要考虑的是队列满的情况：

![Center 4][]

但这种情况存在一个问题，即空队列和满队列没有办法区分了，end和start都指向了相同的位置。

为了解决这个问题，一个方法是空出一个位置不放数据，当end再加一个数据就等于start的时候就认为队列是满的：

![Center 5][]

这时实际的数据长度就会比分配的少1。

下面是队列中空和满的判断：

1. 队列为空时：end == start

2. 队列为满时：(end + 1) % size == start

这里的size是指分配的空间大小，而不是队列长度，队列的实际长度为(end - start + size) % size，最大长度是size-1

这也是因为要考虑循环的关系，所以要加上%size这个操作。

下面是示例代码：

1. 首先定义结构体：

//定义循环队列
    typedef struct _LoopQueue {
    	int data[8];		//存放数据
    	int start;		//头指针
    	int end;		//尾指针
    } LoopQueue;

2. 定义各种算法：

#define TRUE	1
    #define FALSE	0
    #define SIZE	8
    
    //初始化队列
    int init(LoopQueue *lq) {
    	lq->start = 0;
    	lq->end = 0;
    	return TRUE;
    }
    
    //判断队列是否为空
    int isEmpty(LoopQueue *lq) {
    	if (lq->start == lq->end) {
    		return TRUE;
    	}
    	return FALSE;
    }
    
    //判断队列是否为满
    int isFull(LoopQueue *lq) {
    	if ((lq->end + 1) % SIZE == lq->start) {
    		return TRUE;
    	}
    	return FALSE;
    }
    
    //获取队列的长度
    int getLength(LoopQueue *lq) {
    	return (lq->end - lq->start + SIZE) % SIZE;
    }
    
    //插入数据
    int pushQueue(LoopQueue *lq, int data) {
    	if(isFull(lq)) {
    		printf("Queue is full.\n");
    		return FALSE;
    	}
    	lq->data[lq->end] = data;
    	lq->end = (lq->end + 1) % SIZE;
    	return TRUE;
    }
    
    //弹出数据
    int popQueue(LoopQueue *lq, int *data) {
    	if (isEmpty(lq)) {
    		printf("Queue is empty.\n");
    		return FALSE;
    	}
    	*data = lq->data[lq->start];
    	lq->start = (lq->start + 1) % SIZE;
    	return TRUE;
    }
    
    //显示队列中的数据
    void printQueue(LoopQueue *lq) {
    	int index;
    	int count;
    	count = getLength(lq);
    	if (0 == count) {
    		printf("No data.\n");
    		return;
    	}
    	for (index = 0; index < count; index++) {
    		printf("%d ", lq->data[index]);
    	}
    	printf("\n");
    	return;
    }

3. 测试：

int main()
    {
    	int index;
    	int num;
    	//队列测试代码
    	LoopQueue *lq = (LoopQueue *)malloc(sizeof(LoopQueue));
    	init(lq);
    	printQueue(lq);
    	for (index = 0; index < SIZE; index ++) {	//注意这里要放8个数据，但是实际上只能放7个，所以最后一个会报错
    		pushQueue(lq, index);
    	}
    	printQueue(lq);
    	for (index = 0; index < SIZE; index ++) {	//同上，会打印一个错误
    		if (popQueue(lq, &num)) {
    			printf("%d\n", num);
    		}
    	}
    	printQueue(lq);
    	return 0;
    }

4. 最后的结果：

![Center 6][]

[Center]: https://img-blog.csdn.net/20160131164021743?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20160131164108697?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: https://img-blog.csdn.net/20160131164359341?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 3]: https://img-blog.csdn.net/20160131164410013?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 4]: https://img-blog.csdn.net/20160131164805458?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 5]: https://img-blog.csdn.net/20160131165006896?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 6]: https://img-blog.csdn.net/20160131173217741?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center