循环队列

[TOC]

一 定义

1：循环队列简介

循环对列使用顺序表实现，与链式队列不同处在于，循环队列的空间是可以循环使用的。循环队列一般有固定的容量，在使用上遵循队列使用原则，队列的元素必须从队尾进入，从队首出列。为了使用方便，我们将创建一个长度为7 单位的循环队列存储空间，下面不同情况的循环队列在下图中进行表示。front 表示 队首位置 back 表示队尾位置。

注意：front 永远指向队首元素，back永远指向队尾空闲空间，那么当front 与back 指向同一个位置的时候（注定该位置为空），所以可以判断这个队列是空的队列！！！

---

满队列如下图所示，因为back永远指向空地址空间（为了判断是否是满队列），故实际可以使用的空间为最大申请空间 -1 长度。下图可用空间为7 -1 = 6个空间。

---

大概操作示意如下图所示：

---

2：循环队列结构定义

// 循环队列结构定义
typedef struct
{
	int* buf;                  // 缓存buf  同时默认当前存储类型为int
	int  fornt;                // 队头
	int  rear;                 // 队尾
	int max_size;              // 队列大小
}_queue_type;

二 循环队列 C 函数实现

1：初始化一个队列

// 初始化一个队列
// queue: 等待初始化的队列指针
// queue_sieze : 需要初始化的大小
void init_queue(_queue_type *queue,int queue_size)
{
	queue->buf = malloc(queue_size * sizeof(int));
	if (!queue->buf) { printf("队列内存分配错误\r\n"); return; }
	queue->fornt = queue->rear = 0;                           // 对头队尾指向起始0 空队列
	queue->max_size = queue_size;
}

2：入队操作

// 单个 元素入队
// 从队尾入队列
void in_queue(_queue_type* queue, int elem)
{
	if ((queue->rear + 1) % queue->max_size == queue->fornt) { printf("队列满了 \r\n"); return; };    // 队尾指针始终为空
	queue->buf[queue->rear] = elem;
	queue->rear = (queue->rear + 1) % queue->max_size;              // 队尾指向 下一个空闲空间 循环关键
}

3: 出队操作

// 单个元素出列
// 从队首 出列
void out_queue(_queue_type* queue, int* elem)
{
	if (queue->fornt == queue->rear) { printf("空队列\r\n"); return; }
	*elem = queue->buf[queue->fornt];
	queue->fornt = (queue->fornt + 1) % queue->max_size;            
}

4: 队列验证

// 循环队列测试
int main(void)
{
	int test = 0;
	_queue_type myqueue;
	init_queue(&myqueue,100);
	out_queue(&myqueue, &test);
	for (int ii = 0; ii < 10; ii++)
	{
		in_queue(&myqueue,ii + 1);
	}
	for (int a = 0; a < 10; a++)
	{
		out_queue(&myqueue, &test);
		printf("%d\r\n",test);
	}
	out_queue(&myqueue, &test);
	return 0;
}

赏

谢谢你请我吃糖果